Advertisement
Guest User

algo

a guest
May 27th, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4. using namespace std;
  5.  
  6. struct node{
  7. int val;
  8. node *next;
  9. };
  10.  
  11. void add(node *&H, int value)
  12. {
  13. node *p = new node;
  14. p->val = value;
  15. p->next=H;
  16. H=p;
  17.  
  18. }
  19.  
  20. void addToEnd(node *&H, int value){
  21.  
  22. if(H==NULL){
  23. add(H, value);
  24. }else{
  25.  
  26. node *p = H;
  27.  
  28. while(p->next!=NULL){
  29. p=p->next;
  30. }
  31.  
  32. node *p2 = new node;
  33. p2->val = value;
  34. p->next=p2;
  35. p2->next=NULL;
  36.  
  37. }
  38. }
  39.  
  40. void show(node *&H){
  41.  
  42. node *p = H;
  43.  
  44. cout << "H->";
  45. while(p != NULL){
  46. cout << p->val << "->";
  47. p=p->next;
  48. }
  49. cout << "NULL" << endl;
  50.  
  51.  
  52.  
  53. }
  54.  
  55. void del(node *&H){
  56.  
  57. node *p = H;
  58. H = p->next;
  59. delete p;
  60.  
  61.  
  62. }
  63.  
  64.  
  65.  
  66.  
  67. void copyRevert(node *&H){
  68.  
  69. node *p = H;
  70. node *H2 = NULL;
  71. node *pointer = NULL;
  72.  
  73. while(p !=NULL){
  74. add(H2, p->val);
  75. if(p->next == NULL)
  76. pointer = p;
  77.  
  78.  
  79. p=p->next;
  80. }
  81.  
  82. pointer->next = H2;
  83. H2=NULL;
  84. }
  85.  
  86. void copyInOrder(node *&H){
  87.  
  88. node *p = H;
  89. node *H2 = NULL;
  90. node *pointer = NULL;
  91.  
  92. while(p !=NULL){
  93. add(H2, p->val);
  94. if(p->next == NULL)
  95. pointer = p;
  96.  
  97.  
  98. p=p->next;
  99. }
  100.  
  101. show(H2);
  102.  
  103. p=H2;
  104. while(H2 != NULL){
  105.  
  106. if(H2->next==NULL){
  107. pointer->next=H2;
  108. p->next=NULL;
  109. pointer = pointer->next;
  110. H2=NULL;
  111.  
  112.  
  113. }
  114. else if(H2->next->next == NULL){
  115. p=p->next;
  116. pointer->next=p;
  117. p->next = NULL;
  118. H2->next=NULL;
  119. pointer=pointer->next;
  120. p=H2;
  121.  
  122.  
  123. }
  124. else{
  125.  
  126. while(p->next->next != NULL){
  127. p=p->next;
  128. }
  129. pointer->next=p->next;
  130. p->next=NULL;
  131. pointer = pointer->next;
  132. p=H2;
  133.  
  134.  
  135.  
  136. }
  137. }
  138.  
  139. }
  140.  
  141.  
  142.  
  143. void delValue(node *&H, int value)
  144. {
  145. node *p = H;
  146.  
  147. if(H != NULL)
  148. {
  149. if(H->val==value)
  150. {
  151. del(H);
  152. } else {
  153.  
  154. while(p->next != NULL){
  155. if(p->next->val == value)
  156. {
  157. node *temp = p;
  158. p->next=p->next->next;
  159. delete temp;
  160. } else {
  161. p=p->next;
  162. }
  163.  
  164. }
  165. }
  166. } else {
  167. cout << "Lista jest pusta (delValue)"<< endl;
  168. }
  169.  
  170. }
  171.  
  172. void swapWithNext(node *&H, int valToSwap)
  173. {
  174. node *x = H;
  175. node *y = H;
  176. node *z = H;
  177.  
  178. if(H->next->next == NULL)
  179. {
  180. cout << "Lista ma mniej niz 2 elementy" << endl;
  181. } else {
  182.  
  183. if(H->val == valToSwap)
  184. {
  185. {
  186.  
  187.  
  188. cout << "H " << H->val << endl;
  189. cout << "y " << y->val << endl;
  190. cout << "z " << z->val << endl;
  191.  
  192.  
  193. node *x = H-> next;
  194.  
  195. H->next = x -> next;
  196. x->next = H;
  197. H=x;
  198.  
  199.  
  200.  
  201. }
  202.  
  203. } else {
  204.  
  205. while (x->next != NULL) {
  206. if(x->next->val == valToSwap)
  207. {
  208. if (x->next->next == NULL)
  209. {
  210. cout << "Probujesz zamienic ostatni element" << endl;
  211. break;
  212. } else {
  213. y = x-> next;
  214. z = y-> next;
  215.  
  216. y->next = z->next;
  217. z->next = x->next;
  218. x->next = z;
  219.  
  220. break;}
  221.  
  222. }
  223. else {
  224. x = x-> next;
  225. }
  226. }
  227. }
  228. }
  229. }
  230.  
  231.  
  232. void ssort(node *H){
  233. node *H2 = NULL;
  234.  
  235. node *prev_max = NULL;
  236. node *p = H;
  237. node *max = H;
  238.  
  239.  
  240. while(H != NULL){
  241.  
  242.  
  243. prev_max = NULL;
  244. p=H;
  245. max = H;
  246.  
  247. while(p->next != NULL){
  248.  
  249. if(p->next->val > max->val)
  250. {
  251. prev_max = p;
  252. max = p->next;
  253. cout << "Max: " << max->val << endl;
  254. }
  255. p=p->next;
  256. }
  257. if(prev_max == NULL)
  258. {
  259. H=H->next;
  260. max->next = H2;
  261. H2 = max;
  262. }else{
  263.  
  264. prev_max->next = max->next;
  265. max->next=H2;
  266. H2=max;
  267. }
  268.  
  269.  
  270. }
  271.  
  272. H = H2;
  273. H2 = NULL;
  274.  
  275.  
  276. }
  277.  
  278.  
  279. void wiekszeNaKoniec(node *&H){
  280.  
  281. double wartosc = 0;
  282.  
  283. int liczbaElementow = 0;
  284.  
  285.  
  286. node *p = H;
  287.  
  288. while(p!=NULL){
  289. wartosc += p->val;
  290. liczbaElementow++;
  291. p=p->next;
  292.  
  293. }
  294.  
  295. double srednia = wartosc/liczbaElementow;
  296.  
  297. cout << "wartosc " << wartosc << endl;
  298. cout << "srednia " << srednia << endl;
  299. cout << "liczba " << liczbaElementow << endl;
  300.  
  301. node *H2 = NULL;
  302.  
  303. p=H;
  304.  
  305. node *tail = NULL;
  306.  
  307. while(p!=NULL){
  308. if (p->val>srednia) {
  309. addToEnd(H2, p->val);
  310. }
  311. if(p->next==NULL){
  312. tail=p;
  313. }
  314. p=p->next;
  315. }
  316.  
  317. tail->next=H2;
  318. H2=NULL;
  319.  
  320. }
  321.  
  322. void usunCoDrugie(node *&H){
  323.  
  324. node *p = H;
  325. node *d = NULL;
  326.  
  327. if(H!=NULL){
  328.  
  329. while(p->next!=NULL){
  330.  
  331.  
  332. d = p->next;
  333. p->next=p->next->next;
  334. p=p->next;
  335. delete d;
  336.  
  337.  
  338. }
  339. }
  340. }
  341.  
  342. void usunParzystePary(node *H){
  343. node *p = H->next;
  344. node *d = NULL;
  345.  
  346. if(H!=NULL){
  347.  
  348. while(p->next->next != NULL && p->next->next->next!=NULL){
  349.  
  350. if((p->next->val + p->next->next->val) %2 == 0){
  351.  
  352. d = p->next;
  353. p->next = p->next->next->next;
  354. delete d->next;
  355. delete d;
  356.  
  357. }else{
  358. p=p->next->next;
  359. }
  360.  
  361. }
  362. if(p->next->next->next == NULL){
  363. if((p->next->val + p->next->next->val)%2 == 0){
  364.  
  365. delete p->next->next;
  366. delete p->next;
  367. p->next = NULL;
  368.  
  369. }
  370. }else if(p->next->next == NULL){
  371. if((p->val + p->next->val)%2 == 0){
  372. delete p->next;
  373. p=NULL;
  374. }
  375. }
  376.  
  377. }
  378. }
  379.  
  380. //void swapBubble(node *&H, node *&p){
  381. //
  382. //
  383. //
  384. // if(p == NULL)
  385. // {
  386. // node *temp = H;
  387. // H=H->next;
  388. // temp->next = H->next;
  389. // H->next = temp;
  390. // }else{
  391. //
  392. // node *d = p->next->next;
  393. // p->next->next = d->next;
  394. // d->next = p->next;
  395. // p->next = d;
  396. // }
  397. //
  398. //}
  399. //
  400. //void bubbleSort(node *&H){
  401. //
  402. // bool flag = 1; //ustawiam flage ktora sprawdza czy zamieniono jakikolwiek element przy przejsciu
  403. // node *p = H;
  404. //
  405. // while(flag == 1){
  406. // flag = 0;
  407. //
  408. // if(H->val > H->next->val){
  409. // swapBubble(H, p=NULL);
  410. // flag = 1;
  411. //
  412. // }else{
  413. //
  414. // p=H;
  415. // while (p->next->next != NULL) {
  416. //
  417. // if(p->next->val > p->next->next->val){
  418. // swapBubble(H, p);
  419. // flag = 1;
  420. // }
  421. // p=p->next;
  422. // }
  423. // }
  424. // }
  425. //}
  426.  
  427.  
  428. void swapBubble(node *&H, node *&p){
  429.  
  430.  
  431.  
  432. if(p==NULL){
  433. node *temp = H;
  434. H=H->next;
  435. temp->next = H->next;
  436. H->next=temp;
  437. }else{
  438. node *temp = p->next->next;
  439. p->next->next = temp ->next;
  440. temp->next = p->next;
  441. p->next=temp;
  442. }
  443.  
  444.  
  445. }
  446.  
  447. void bubbleSort(node *&H){
  448.  
  449. node *p = H;
  450. int flag = 1;
  451.  
  452. while(flag == 1){
  453. flag = 0;
  454. //if(H->next != NULL && H!=NULL)
  455. {
  456. if(H->val > H->next->val){
  457. swapBubble(H, p=NULL);
  458. flag = 1;
  459. }else{
  460. p=H;
  461. while(p->next->next != NULL){
  462.  
  463.  
  464. if(p->next->val>p->next->next->val){
  465. swapBubble(H, p);
  466. flag = 1;
  467. }
  468. p=p->next;
  469.  
  470. }
  471. }}
  472.  
  473. }
  474.  
  475. }
  476.  
  477.  
  478. void splitList(node *&H, node *&H1, node *&H2){ //Przerobic to na funkcje zewnetrzna, wywolywanie dla kazdego elementu w petli while
  479.  
  480. if(H!=NULL){
  481.  
  482. node *p = NULL;
  483. node *t1 = NULL;
  484. node *t2 = NULL;
  485.  
  486. while(H!=NULL){
  487.  
  488. p=H;
  489. H=H->next;
  490. if(t1==NULL){
  491. t1 = p;
  492. H1=p;
  493. p->next = NULL;}
  494. else{
  495. t1->next = p;
  496. t1 = p;
  497. t1->next = NULL;
  498. }
  499. if(H!=NULL){
  500. p=H;
  501. H=H->next;
  502. if(t2==NULL){
  503. t2 = p;
  504. H2=p;
  505. p->next = NULL;}
  506. else{
  507. t2->next = p;
  508. t2 = p;
  509. t2->next = NULL;
  510. }
  511.  
  512. }
  513.  
  514. }
  515.  
  516. }
  517.  
  518. }
  519.  
  520. void usunWiekszeOdSredniej(node *&H){
  521.  
  522. double wartosc = 0;
  523.  
  524. double liczbaElementow = 0;
  525.  
  526.  
  527. node *p = H;
  528.  
  529. while(p!=NULL){
  530. wartosc += p->val;
  531. liczbaElementow++;
  532. p=p->next;
  533.  
  534. }
  535.  
  536. double srednia = wartosc/liczbaElementow;
  537.  
  538. p=H;
  539.  
  540. while(p->next != NULL){
  541.  
  542. if(H->val > srednia){
  543. node *temp = H;
  544. H=H->next;
  545. delete temp;
  546. }
  547. if(p->next->val > srednia){
  548. node *temp = p->next;
  549. p->next=p->next->next;
  550. delete temp;
  551. }
  552. p=p->next;
  553.  
  554.  
  555. }
  556.  
  557. }
  558.  
  559. void insertToSortedList(node *&H, int x){
  560.  
  561. node *p = H;
  562.  
  563. if(H==NULL){
  564. add(H, x);
  565. }
  566. if (x < p->val) {
  567. add(H, x);
  568. }else{
  569. while (p->next->val < x) {
  570. p=p->next;
  571. }
  572. add(p->next, x);
  573. }
  574. }
  575.  
  576. void showDB(node **DB, int size){
  577.  
  578. for(int i = 0; i<size; i++)
  579. {
  580. cout << DB[i]->val << endl;
  581. }
  582.  
  583. }
  584.  
  585. void database(node *&H, int size){
  586.  
  587. node **DB = new node*[size/100];
  588.  
  589.  
  590. for(int i = 0; i<size/100; i++){
  591. DB[i]=NULL;
  592. }
  593.  
  594.  
  595. cout << "kubelkowe start" << endl;
  596.  
  597. std::chrono::time_point<std::chrono::system_clock> start, end;
  598. start = std::chrono::system_clock::now();
  599. srand( time( NULL ) );
  600. for(int i=0; i<size; i++){
  601. int temp = (( rand() % 50000 ) + 1 );
  602. add(DB[temp/100],temp);
  603. add(H, temp);
  604.  
  605. }
  606.  
  607. for(int i = 0; i < size/100; i++){
  608. if (DB[i]!=NULL && DB[i]->next != NULL) {
  609. bubbleSort(DB[i]);
  610.  
  611. }
  612. }
  613.  
  614. node *HF = DB[0];
  615. node *p = HF;
  616. for(int i = 1; i<size/100; i++){
  617. if(HF!=NULL){
  618. while (p->next != NULL) {
  619. p=p->next;}
  620. }
  621. p->next = DB[i];
  622.  
  623.  
  624. }
  625. end = std::chrono::system_clock::now();
  626.  
  627. std::chrono::duration<double> elapsed_seconds = end-start;
  628. std::time_t end_time = std::chrono::system_clock::to_time_t(end);
  629.  
  630. std::cout << "finished computation at " << std::ctime(&end_time)
  631. << "elapsed time: " << elapsed_seconds.count() << "s\n";
  632.  
  633. cout << "babelkowe koniec" << endl;
  634. cout << "kubelkowe koniec" << endl;
  635. cout << "babelkowe start" << endl;
  636.  
  637.  
  638. start = std::chrono::system_clock::now();
  639. bubbleSort(H);
  640. //std::cout << "f(42) = " << fibonacci(42) << '\n';
  641. end = std::chrono::system_clock::now();
  642.  
  643. elapsed_seconds = end-start;
  644. end_time = std::chrono::system_clock::to_time_t(end);
  645.  
  646. std::cout << "finished computation at " << std::ctime(&end_time)
  647. << "elapsed time: " << elapsed_seconds.count() << "s\n";
  648.  
  649. cout << "babelkowe koniec" << endl;
  650.  
  651.  
  652.  
  653. }
  654.  
  655. int main() {
  656.  
  657. node *H = NULL;
  658.  
  659. database(H, 50000);
  660.  
  661.  
  662. return 0;
  663. }
  664.  
  665. // node *H1 = NULL;
  666. // node *H2 = NULL;
  667.  
  668. //add(H, 2);
  669. //add(H, 18);
  670. //add(H, 2);
  671. //add(H, 6);
  672. //add(H, 33);
  673. //add(H, 8);
  674. //add(H, 1);
  675. //
  676. //show(H);
  677. //bubbleSort(H);
  678. //show(H);
  679. //insertToSortedList(H, 22);
  680. //show(H);
  681. //insertToSortedList(H, 4);
  682. //show(H);
  683. //insertToSortedList(H, -9);
  684. //show(H);
  685. //add(H, 6);
  686. //add(H, 14);
  687. //add(H, 1);
  688. //add(H, 12);
  689. //add(H, 17);
  690. //add(H, 65);
  691. //add(H, 157);
  692. //add(H, 13);
  693. // usunCoDrugie(H);
  694. // addToEnd(H, 666);
  695. // wiekszeNaKoniec(H);
  696. // copyRevert(H);
  697. // copyInOrder(H);
  698. // usunParzystePary(H);
  699.  
  700. // splitList(H, H1, H2);
  701. // usunWiekszeOdSredniej(H);
  702.  
  703.  
  704. //if(H->next->next == NULL || H->next == NULL || H == NULL)
  705. //{
  706. // cout << "Tu tego nie zrobisz" << endl;
  707. //}else
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement