API tools faq
paste
szmelu

listy 2

szmelu
May 7th, 2017
60
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.04 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <ctime>
  3. #include <stdlib.h>
  4. using namespace std;
  5.  
  6. struct node{
  7. node * next;
  8. int value;
  9. };
  10.  
  11.  
  12. void DELL(node *& H){
  13. if(H!=NULL){
  14. node * temp=new node;
  15. temp = H;
  16. H=temp->next;
  17. delete temp;
  18. }
  19. }
  20.  
  21. void ADD( node *& H, int val){
  22. node * temp = new node;
  23. temp->next=H;
  24. temp->value=val;
  25. H=temp;
  26. }
  27.  
  28.  
  29. void show(node * H){
  30. cout <<"H->";
  31. node *temp=H;
  32. while(temp!=NULL){
  33. cout << temp->value<<"->";
  34. temp=temp->next;
  35. }
  36. cout << "NULL"<<endl;
  37. }
  38.  
  39. void usunpomax(node *&H)
  40. {
  41. int x=0;
  42.  
  43. if(H!=NULL)
  44. {
  45. node *temp = new node;
  46. temp=H;
  47. while(temp!=NULL)
  48. {
  49. if(temp->value>x)
  50. {
  51. x=temp->value;
  52. temp=temp->next;
  53. }
  54. else
  55. temp=temp->next;
  56. }
  57. }
  58.  
  59. if(H!=NULL)
  60. {
  61. node *tmp= new node;
  62. tmp=H;
  63. while(tmp!=NULL)
  64. {
  65. if(tmp->value==x)
  66. {
  67. tmp->next=tmp->next->next;
  68. break;
  69.  
  70. }
  71. else
  72. tmp=tmp->next;
  73. }
  74.  
  75. }
  76.  
  77. }
  78. void przed(node *&H)
  79. {
  80. int x=0;
  81. if(H!=NULL)
  82. {
  83. node *temp= new node;
  84. temp=H;
  85. while(temp!=NULL)
  86. {
  87. if(temp->next->next==NULL)
  88. {
  89. x=temp->next->value;
  90. temp->next=temp->next->next;
  91. break;
  92. }
  93. else
  94. temp=temp->next;
  95. }
  96. }
  97. ADD(H,x);
  98. }
  99. /*void lacz(node *&H, node *&D)
  100. {
  101. int i=1;
  102. node *temp=new node;
  103. node *tmp=new node;
  104. temp=H;
  105. tmp=D;
  106. temp->next=tmp;
  107.  
  108. while(temp!=NULL && tmp!=NULL)
  109. {
  110. temp->next=tmp;
  111. tmp->next=temp->next;
  112. }
  113.  
  114.  
  115.  
  116.  
  117. }*/
  118. void zamien(node *&H, int x)
  119. {
  120. if(H!=NULL)
  121. {
  122. node *temp = new node;
  123. temp=H;
  124. while(temp->next!=NULL)
  125. {
  126.  
  127. if(x==temp->next->value)
  128. {
  129. if(temp->next->next==NULL)
  130. {
  131. cout<<"nastepnikiem jest NULL"<<endl;
  132. break;
  133. }
  134. node *tmp=new node;
  135. tmp=temp->next;
  136. node *tmp2=new node;
  137. tmp2=temp->next->next;
  138. tmp->next=tmp2->next;
  139. temp->next=tmp2;
  140. temp->next->next=tmp;
  141. break;
  142.  
  143. }
  144. else
  145. temp=temp->next;
  146. }
  147. }
  148. }
  149. void zamprzed(node *&H, int x)
  150. {
  151. if(H!=NULL)
  152. {
  153. node *temp=new node;
  154. temp=H;
  155. while(temp->next!=NULL)
  156. {
  157. if(x==H->value)
  158. {
  159. cout<<"Nie ma poprzednika"<<endl;
  160. break;
  161. }
  162. if(x==temp->next->next->value)
  163. {
  164.  
  165. node *tmp= new node;
  166. tmp=temp->next;
  167. node *tmp2=new node;
  168. tmp2=temp->next->next;
  169. tmp->next=tmp2->next;
  170. temp->next=tmp2;
  171. temp->next->next=tmp;
  172. break;
  173. }
  174. else
  175. temp=temp->next;
  176. }
  177. }
  178. }
  179. void kasn(node *&H, int x, int n)
  180. {
  181. if(H!=NULL)
  182. {
  183. node *temp=new node;
  184. temp=H;
  185. while(temp->next!=NULL)
  186. {
  187. if(temp->value==x)
  188. break;
  189. else
  190. temp=temp->next;
  191. }
  192. for(int i=0;i<n;i++)
  193. temp->next=temp->next->next;
  194. }
  195. }
  196. void odwroc(node *&H)
  197. {
  198. if(H!=NULL)
  199. {
  200. node *temp = H;
  201. node *tmp=NULL;
  202. while(temp->next!=NULL)
  203. {
  204. tmp=temp->next;
  205. temp->next=temp->next->next;
  206. tmp->next=H;
  207. H=tmp;
  208. }
  209.  
  210.  
  211. }
  212. }
  213.  
  214. void co2(node *&H)
  215. {
  216. if(H!=NULL)
  217. {
  218. node *temp= new node;
  219. temp=H;
  220. H=H->next;
  221. delete temp;
  222. temp=H;
  223.  
  224. while(temp->next!=NULL )
  225. {
  226. if(temp->next!=NULL && temp->next->next==NULL)
  227. {
  228. temp->next=NULL;
  229. break;
  230. }
  231. temp->next=temp->next->next;
  232. temp=temp->next;
  233. }
  234. }
  235. }
  236.  
  237. void parz(node *&H)
  238. {
  239. node *tmp = H;
  240. node *wsk1 = H;
  241. node *wsk2 = H;
  242.  
  243. while (H->next != NULL && H->value % 2 == 0)
  244. {
  245. H = H->next;
  246. delete tmp;
  247. tmp = H;
  248. }
  249.  
  250. wsk2 = H;
  251. wsk1 = H;
  252.  
  253. while (tmp->next != NULL)
  254. {
  255. if (tmp->value % 2 == 0)
  256. {
  257. wsk1 = tmp;
  258. tmp = tmp->next;
  259. wsk2->next = tmp;
  260. delete wsk1;
  261. }
  262. else
  263. {
  264. wsk2 = tmp;
  265. tmp = tmp->next;
  266. }
  267. }
  268. }
  269. //ZADANIE NR1
  270.  
  271. void srednia(node*&H)
  272. {
  273. if (H != NULL)
  274. {
  275. node *temp = H;
  276. node *tmp = NULL;
  277. node *tmp2 = NULL;
  278. float x = 0, i = 0;
  279. float srednia = 0;
  280. while (temp != NULL)
  281. {
  282. if (temp->next == NULL)
  283. tmp = temp;
  284. x = x + temp->value;
  285. i++;
  286. temp = temp->next;
  287. }
  288. int z = 0;
  289. srednia = x / i;
  290. delete temp;
  291. temp = H;
  292. cout<<"srednia: " << srednia << endl;
  293. while(z < i)
  294. {
  295. z++;
  296. if(H->value > srednia)
  297. {
  298. tmp->next=temp;
  299. tmp=tmp->next;
  300. H=H->next;
  301. temp=H;
  302. }
  303. else
  304. {
  305. if(temp->value > srednia)
  306. {
  307. tmp->next=temp;
  308. tmp=tmp->next;
  309. temp=tmp2;
  310. temp->next=temp->next->next;
  311. temp=temp->next;
  312. }
  313. else
  314. {
  315. tmp2=temp;
  316. temp=temp->next;
  317. }
  318. }
  319. }
  320. tmp->next=NULL;
  321. }
  322. }
  323. void mnoz(node*&H)
  324. {
  325. if(H!=NULL)
  326. {
  327. node *temp=H;
  328. node *tmp=NULL;
  329. while(temp!=NULL)
  330. {
  331. for(int i=1;i<temp->value;i++)
  332. {
  333. tmp=new node;
  334. tmp->value=temp->value;
  335. tmp->next=temp->next;
  336. temp->next=tmp;
  337. temp=temp->next;
  338. }
  339. temp=temp->next;
  340. }
  341. }
  342. }
  343. void zderzaki(node*&H, int x, int y)
  344. {
  345. if(H!=NULL)
  346. {
  347. node *temp=H;
  348. node *tmp=NULL;
  349. node *tmp2=NULL;
  350. node *tmp3=NULL;
  351.  
  352. int licz=0;
  353. while(temp->value!=x)
  354. {
  355. temp=temp->next;
  356. tmp3=temp;
  357. }
  358. while(temp->value!=y)
  359. {
  360. licz++;
  361. temp=temp->next;
  362. }
  363. for(int i=2;i<licz;licz--)
  364. {
  365. temp=tmp3;
  366. while(i<licz)
  367. {
  368. i++;
  369. tmp=temp->next->next;
  370. tmp2=temp->next;
  371. tmp2->next=tmp->next;
  372. tmp->next=tmp2;
  373. temp->next=tmp;
  374. temp=temp->next;
  375. }
  376. i=2;
  377. }
  378. }
  379. }
  380. void copy(node *&H, node *&D)
  381. {
  382. if(H!=NULL)
  383. {
  384. node *tmp = H;
  385. node *tmp2 = D;
  386. while(tmp->next !=NULL)
  387. tmp=tmp->next;
  388. tmp->next=tmp2;
  389.  
  390. }
  391. }
  392. void bubblesort(node*&H)
  393. {
  394. if(H!=NULL)
  395. {
  396. int i=0;
  397. node *temp=H, *tmp=NULL, *tmp2=NULL, *tmp3=NULL;
  398. while(temp->next->next!=NULL)
  399. {
  400. i=0;
  401. if(H->value>H->next->value)
  402. {
  403. i++;
  404. tmp=H;
  405. tmp2=H->next;
  406. tmp3=H->next->next;
  407. tmp->next=tmp3;
  408. tmp2->next=tmp;
  409. H=tmp2;
  410. temp=H;
  411. }
  412.  
  413. while(temp->next->next!=NULL)
  414. {
  415. if(temp->next->value>temp->next->next->value)
  416. {
  417. i++;
  418. tmp=temp->next;
  419. tmp2=temp->next->next;
  420. tmp3=temp->next->next->next;
  421. tmp->next=tmp3;
  422. tmp2->next=tmp;
  423. temp->next=tmp2;
  424. temp=temp->next;
  425. }
  426. else
  427. temp=temp->next;
  428. }
  429. if(i!=0)
  430. temp=H;
  431.  
  432. }
  433. }
  434. }
  435. int main()
  436. {
  437. node * H = NULL;
  438. ADD(H, 13);
  439. ADD(H, 8);
  440. ADD(H, 5);
  441. ADD(H,14);
  442. ADD(H,2);
  443. ADD(H,12);
  444. ADD(H,22);
  445. ADD(H,1);
  446. ADD(H,11);
  447. show(H);
  448. //srednia(H);
  449. //show(H);
  450. //mnoz(H);
  451. //show(H);
  452. //odwroc(H);
  453. //zderzaki(H, 22, 8);
  454. copy(H, H);
  455. show(H);
  456.  
  457. system("pause");
  458. }
  459. void sort(node *&H, node**&tab)
  460. {
  461. if (H != NULL)
  462. {
  463. node *temp = H;
  464. for (int i = 0; i < N / 100; i++)
  465. {
  466. while (temp->next != NULL)
  467. {
  468. if (temp->value <= (i + 1) * 100 && temp->value>i*100)
  469. {
  470. ADD(tab[i], temp->value);
  471. temp = temp->next;
  472. }
  473. else
  474. temp = temp->next;
  475. }
  476. temp = H;
  477.  
  478. }
  479. }
  480. }
  481. void bubblesort(node*&H)
  482. {
  483. if (H != NULL)
  484. {
  485. int i = 0;
  486. node *temp = H, *tmp = NULL, *tmp2 = NULL, *tmp3 = NULL;
  487. while (temp->next->next != NULL)
  488. {
  489. i = 0;
  490. if (H->value>H->next->value)
  491. {
  492. i++;
  493. tmp = H;
  494. tmp2 = H->next;
  495. tmp3 = H->next->next;
  496. tmp->next = tmp3;
  497. tmp2->next = tmp;
  498. H = tmp2;
  499. temp = H;
  500. }
  501.  
  502. while (temp->next->next != NULL)
  503. {
  504. if (temp->next->value>temp->next->next->value)
  505. {
  506. i++;
  507. tmp = temp->next;
  508. tmp2 = temp->next->next;
  509. tmp3 = temp->next->next->next;
  510. tmp->next = tmp3;
  511. tmp2->next = tmp;
  512. temp->next = tmp2;
  513. temp = temp->next;
  514. }
  515. else
  516. temp = temp->next;
  517. }
  518. if (i != 0)
  519. temp = H;
  520.  
  521. }
  522. }
  523. }
  524. void lacz(node *&p, node **&tab)
  525. {
  526. node* temp = NULL;
  527. temp = tab[0];
  528. for (int i = 0; i < N / 100; i++)
  529. {
  530.  
  531.  
  532. while (temp->next != NULL)
  533. {
  534. temp = temp->next;
  535. }
  536. temp->next = tab[i + 1];
  537. if (i == (N / 100) - 1)
  538. temp->next = NULL;
  539.  
  540.  
  541. }
  542. p = tab[0];
  543. }
  544.  
  545. int main()
  546. {
  547. clock_t s, f;
  548. double czas=0.0, czas2=0.0;
  549. node *p = NULL;
  550. int x = N / 100;
  551. node **tab = new node*[x];
  552. for (int i = 0; i < x; i++)
  553. {
  554. tab[i] = NULL;
  555.  
  556. }
  557. srand(time(NULL));
  558. node * H = NULL, *H2=NULL;
  559. for (int i = 0; i < N; i++)
  560. {
  561. ADD(H, rand() % 10000);
  562. ADD(H2, rand() % 10000);
  563. }
  564.  
  565.  
  566. //show(H);
  567. sort(H, tab);
  568. s = clock();
  569. for (int i = 0; i < x; i++)
  570. {
  571. bubblesort(tab[i]);
  572. //cout << "DB[" << i << "]->";
  573. //show(tab[i]);
  574.  
  575. }
  576. lacz(p, tab);
  577. f = clock();
  578.  
  579. czas += (double)(f - s) / CLOCKS_PER_SEC;
  580. s = clock();
  581. bubblesort(H2);
  582. f = clock();
  583. czas2 += (double)(f - s) / CLOCKS_PER_SEC;
  584.  
  585.  
  586. //show(p);
  587. cout << czas << endl;
  588. cout << czas2 << endl;
  589.  
  590.  
  591.  
  592.  
  593.  
  594. system("pause");
  595. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!