API tools faq
paste
Guest User

Untitled

a guest
Jul 18th, 2018
67
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 18.99 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5.  
  6. struct node { //宣告singly linked list結構
  7. int data;
  8. struct node *next;
  9. };
  10.  
  11. struct nodeDLL { //宣告doubly linked list結構
  12. int data;
  13. struct nodeDLL *prev, *next;
  14. };
  15.  
  16. struct node *first = NULL; //宣告指向首端的結構指標
  17. struct nodeDLL *firstDLL = NULL, *tailDLL = NULL; //宣告指向首端及尾端的結構指標
  18.  
  19. void build_a_list(struct node **first, int n); //宣告singly linked list函數群
  20. void print_list(struct node *first);
  21. void clean_list(struct node *first);
  22. void insert_to_list(struct node **first);
  23. void search_list();
  24. void delete_from_list();
  25. void count_list();
  26. void reverse_list();
  27. void merge_list(int n);
  28. void split_list();
  29.  
  30. void build_a_DLL(struct nodeDLL **firstDLL, struct nodeDLL **tailDLL, int n); //宣告doubly linked list函數群
  31. void prePrint_DLL(struct nodeDLL *firstDLL);
  32. void postPrint_DLL(struct nodeDLL *firstDLL);
  33. void clean_DLL(struct nodeDLL *firstDLL);
  34. void insert_to_DLL(struct nodeDLL **firstDLL, struct nodeDLL **tailDLL);
  35. void search_DLL();
  36. void delete_from_DLL();
  37. void count_DLL();
  38. void reverse_DLL();
  39. void merge_DLL(int n);
  40. void split_DLL();
  41.  
  42. int main(void)
  43. {
  44. int DS, n; //DS讀入資料結構型態
  45. char F; //F讀入執行函數類型
  46.  
  47. printf("Please select the data structure or exit: ");
  48. scanf("%d", &DS);
  49. srand(time(NULL));
  50. n = rand() % 10 + 3; //先創造一隨機長度的linked list
  51. if (DS == 1) {
  52. printf("Please enter %d numbers to create a initial list: ", n);
  53. build_a_list(&first, n);
  54. print_list(first);
  55. }
  56. else if (DS == 2) {
  57. printf("Please enter %d numbers to create a initial list: ", n);
  58. build_a_DLL(&firstDLL, &tailDLL, n);
  59. prePrint_DLL(firstDLL);
  60. }
  61. else
  62. return 0;
  63.  
  64. while (1) {
  65. getchar(); //吸收多input的Enter
  66. printf("Please select the function: ");
  67. scanf("%c", &F);
  68. if (DS == 1) { //若選擇singly linked list則執行此選單
  69. switch (F) {
  70. case 'a': printf("Enter the number you want to insert: ");
  71. insert_to_list(&first);
  72. break;
  73. case 'b': delete_from_list();
  74. break;
  75. case 'c': search_list();
  76. break;
  77. case 'd': count_list();
  78. break;
  79. case 'e': reverse_list();
  80. break;
  81. case 'f': merge_list(n);
  82. break;
  83. case 'g': split_list();
  84. break;
  85. case 'h': print_list(first);
  86. break;
  87. case 'x': clean_list(first);
  88. return 0;
  89. }
  90. }
  91. else { //若選擇doubly linked list則執行此選單
  92. switch (F) {
  93. case 'a': printf("Enter the number you want to insert: ");
  94. insert_to_DLL(&firstDLL, &tailDLL);
  95. break;
  96. case 'b': delete_from_DLL();
  97. break;
  98. case 'c': search_DLL();
  99. break;
  100. case 'd': count_DLL();
  101. break;
  102. case 'e': reverse_DLL();
  103. break;
  104. case 'f': merge_DLL(n);
  105. break;
  106. case 'g': split_DLL();
  107. break;
  108. case 'h': prePrint_DLL(firstDLL);
  109. break;
  110. case 'i': postPrint_DLL(tailDLL);
  111. break;
  112. case 'x': clean_DLL(firstDLL);
  113. return 0;
  114. }
  115. }
  116. }
  117. }
  118.  
  119. void build_a_list(struct node **first, int n) //創造一隨機長度的linked list
  120. {
  121. int i;
  122. struct node *new_node, *prev = NULL, *cur;
  123.  
  124. new_node = malloc(sizeof(struct node)); //創造第一個節點空間
  125. if (new_node == NULL) { //若創造失敗則印出錯誤
  126. printf("Error: malloc failed.\n");
  127. return;
  128. }
  129. new_node->next = *first; //first指向第一個節點
  130. *first = new_node;
  131. for (i = 0; i < n; i++) {
  132. cur = *first;
  133. scanf("%d", &new_node->data); //讀入數字到節點
  134. while (cur->data < new_node->data && cur->next != NULL) { //由小到大排列節點
  135. prev = cur;
  136. cur = cur->next;
  137. }
  138. if (cur->data < new_node->data && cur->next == NULL) { //若原始list內沒有節點的數字比欲插入之節點大，則節點放到尾端
  139. cur->next = new_node;
  140. new_node->next = NULL;
  141. }
  142. else if (prev == NULL) { //若首端節點數字即比欲插入節點大，則將first指向欲插入之節點，並將節點與原list連結
  143. if (new_node->next == NULL) //若list內無任何節點，則不需做連結
  144. ;
  145. else {
  146. *first = new_node;
  147. }
  148. }
  149. else { //若為其他狀況則將前一個節點和欲插入之節點連結，欲插入之節點和後一個節點連結
  150. prev->next = new_node;
  151. new_node->next = cur;
  152. }
  153. new_node = malloc(sizeof(struct node)); //再創一個新節點空間
  154. if (new_node == NULL) { //若創造失敗則印出錯誤
  155. printf("Error: malloc failed.\n");
  156. return;
  157. }
  158. if (i == n - 1) //若為最後一次跑for loop，則釋放剛創的節點空間
  159. free(new_node);
  160. }
  161. }
  162.  
  163. void print_list(struct node *first) //印出linked list
  164. {
  165. if (first == NULL) { //若無list，則印出訊息
  166. printf("There is no list.\n");
  167. return;
  168. }
  169. struct node *cur;
  170.  
  171. for (cur = first; cur != NULL; cur = cur->next) //從第一個節點開始循序印出數字
  172. printf("%d ", cur->data);
  173. printf("\n");
  174. }
  175.  
  176. void clean_list(struct node *first) //清除linked list
  177. {
  178. struct node *prev, *cur;
  179.  
  180. for (cur = first; cur != NULL;) {
  181. prev = cur;
  182. cur = cur->next;
  183. first = cur;
  184. free(prev);
  185. }
  186. first = NULL;
  187. }
  188.  
  189. void insert_to_list(struct node **first) //插入一個新節點
  190. {
  191. struct node *new_node, *prev = NULL, *cur;
  192.  
  193. new_node = malloc(sizeof(struct node)); //創造新節點空間
  194. if (new_node == NULL) { //若創造失敗則印出訊息
  195. printf("Error: malloc failed.\n");
  196. return;
  197. }
  198. scanf("%d", &new_node->data); //讀入數字
  199. if (*first == NULL) { //若無list可插入新節點則印出訊息
  200. printf("There is no list to insert a new node.\n");
  201. free(new_node);
  202. return;
  203. }
  204. for (cur = *first; cur->data < new_node->data && cur->next != NULL;) { //確定新節點位置
  205. prev = cur;
  206. cur = cur->next;
  207. }
  208. if (prev == NULL) { //若為第一個則first指向新節點，並將新節點與原list連結
  209. new_node->next = *first;
  210. *first = new_node;
  211. }
  212. else {
  213. if (cur->next == NULL) { //若為最後一個則原list尾端節點與之連結
  214. cur->next = new_node;
  215. new_node->next = NULL;
  216. }
  217. else { //其他狀況則前一個和後一個與之連結
  218. prev->next = new_node;
  219. new_node->next = cur;
  220. }
  221. }
  222. }
  223.  
  224. void delete_from_list() //從list中刪除一個節點
  225. {
  226. int n;
  227. struct node *cur, *prev = NULL;
  228.  
  229. if (first == NULL) { //若無list則印出訊息
  230. printf("Nothing to delete.\n");
  231. return;
  232. }
  233. printf("Enter the number you want to delete: "); //印出要求
  234. scanf("%d", &n); //讀入數字
  235. for (cur = first; cur != NULL && cur->data != n; prev = cur, cur = cur->next) //定位
  236. ;
  237. if (cur == NULL) { //若找不到欲刪除之節點則印出訊息
  238. printf("The number doesn't exist in the list.\n");
  239. return;
  240. }
  241. else if (prev == NULL) //若為首端節點則將first指向下一個節點
  242. first = cur->next;
  243. else //其他狀況則前一個與後一個連結
  244. prev->next = cur->next;
  245. free(cur); //釋放節點空間
  246. printf("The node has been deleted.\n"); //印出訊息
  247. }
  248.  
  249. void search_list() //搜尋節點
  250. {
  251. int n, num_node = 1;
  252. struct node *cur;
  253.  
  254. cur = first;
  255. printf("Enter the number you want to search: "); //印出要求
  256. scanf("%d", &n); //讀入數字
  257. for (; cur != NULL; cur = cur->next, num_node++) //搜尋是否存在
  258. if (cur->data == n) {
  259. printf("The number is in no.%d list.\n", num_node); //存在則印出訊息
  260. return;
  261. }
  262. printf("The number doesn't exist in the list.\n"); //不存在則印出訊息
  263. }
  264.  
  265. void count_list() //計算節點數
  266. {
  267. int num_nodes = 0;
  268. struct node *cur;
  269.  
  270. for (cur = first; cur != NULL; cur = cur->next) //計算節點數後印出結果
  271. num_nodes++;
  272. printf("There are %d nodes in the list.\n", num_nodes);
  273. }
  274.  
  275. void reverse_list() //反轉list
  276. {
  277. struct node *prev, *cur;
  278.  
  279. cur = first;
  280. first = NULL;
  281. while (cur != NULL) { //反轉各節點間的連結並改變first指向
  282. prev = cur;
  283. cur = cur->next;
  284. prev->next = first;
  285. first = prev;
  286. }
  287. printf("The list has been reversed.\n"); //印出訊息
  288. }
  289.  
  290. void merge_list(int n) //合併兩條linked list
  291. {
  292. int i;
  293. struct node *head = NULL;
  294.  
  295. srand(time(NULL));
  296. n = rand() % 10 + 1;
  297. printf("Please enter %d numbers for the first list: ", n); //輸入第一條list並創建
  298. build_a_list(&head, n);
  299. n = rand() % 10 + 1;
  300. printf("Please enter %d numbers for the second list: ", n); //輸入第二條list並插入第一條list中
  301. for (i = 0; i < n; i++)
  302. insert_to_list(&head);
  303. printf("The merged list:\n");
  304. print_list(head);
  305. printf("But the initial list won't change.\n"); //並不會改變最初創建的initial list
  306. clean_list(head);
  307. }
  308.  
  309. void split_list() //將list分成奇數及偶數並印出
  310. {
  311. struct node *cur, *even = NULL, *odd = NULL;
  312.  
  313. for (cur = first; cur->data % 2 != 0 && cur->next != NULL; cur = cur->next) //找存偶數的第一個節點
  314. ;
  315. if (cur->data % 2 != 0 && cur->next == NULL) {
  316. printf("There is no even number in the list.");
  317. return;
  318. }
  319. else
  320. even = cur;
  321. for (cur = first; cur->data % 2 == 0 && cur->next != NULL; cur = cur->next) //找存奇數的第一個節點
  322. ;
  323. if (cur->data % 2 == 0 && cur->next == NULL) {
  324. printf("There is no odd number in the list.");
  325. return;
  326. }
  327. else
  328. odd = cur;
  329. cur = even;
  330. printf("The even list:\n%d ", cur->data); //依序找出存偶數的節點並印出
  331. while (cur->next != NULL) {
  332. cur = cur->next;
  333. while (cur->data % 2 != 0 && cur->next != NULL)
  334. cur = cur->next;
  335. if (cur->data % 2 == 0)
  336. printf("%d ", cur->data);
  337. else
  338. break;
  339. }
  340. printf("\n");
  341. cur = odd;
  342. printf("The odd list:\n%d ", cur->data); //依序找出存奇數的節點並印出
  343. while (cur->next != NULL) {
  344. cur = cur->next;
  345. while (cur->data % 2 == 0 && cur->next != NULL)
  346. cur = cur->next;
  347. if (cur->data % 2 != 0)
  348. printf("%d ", cur->data);
  349. else
  350. break;
  351. }
  352. printf("\n");
  353. }
  354.  
  355. void build_a_DLL(struct nodeDLL **firstDLL, struct nodeDLL **tailDLL, int n) //創造一個doubly linked list
  356. {
  357. int i;
  358. struct nodeDLL *new_node, *prev = NULL, *cur;
  359.  
  360. new_node = malloc(sizeof(struct nodeDLL)); //宣告第一個節點空間
  361. if (new_node == NULL) {
  362. printf("Error: malloc failed.\n");
  363. return;
  364. }
  365. new_node->next = *firstDLL; //將first指向第一個節點
  366. *firstDLL = new_node;
  367. for (i = 0; i < n; i++) {
  368. cur = *firstDLL;
  369. scanf("%d", &new_node->data); //讀入數字
  370. printf("yeah\n");
  371. while (cur->data < new_node->data && cur->next != NULL) { //定位
  372. prev = cur;
  373. cur = cur->next;
  374. }
  375. if (cur->data < new_node->data && cur->next == NULL) { //若無節點內數字比新節點大，則新節點置於最後一個，並改變tailDLL指向
  376. cur->next = new_node;
  377. new_node->next = NULL;
  378. new_node->prev = cur;
  379. *tailDLL = new_node;
  380. }
  381. else if (prev == NULL) { //若為最小節點
  382. if (new_node->next == NULL) //若為第一個節點，則tailDLL指向它
  383. *tailDLL = new_node;
  384. else { //否則只消改變first指向
  385. new_node->next = *firstDLL;
  386. *firstDLL = new_node;
  387. }
  388. new_node->prev = NULL;
  389. }
  390. else { //其他狀況則改變前一個、後一個及新節點的連結
  391. prev->next = new_node;
  392. new_node->next = cur;
  393. cur->prev = new_node;
  394. new_node->prev = prev;
  395. }
  396. new_node = malloc(sizeof(struct nodeDLL)); //再創另一個節點空間
  397. if (new_node == NULL) {
  398. printf("Error: malloc failed.\n");
  399. return;
  400. }
  401. if (i == n - 1) //若為最後一次執行for loop，則釋放新節點空間
  402. free(new_node);
  403. }
  404. printf("yeah\n");
  405. }
  406.  
  407. void prePrint_DLL(struct nodeDLL *firstDLL) //正向印出doubly linked list
  408. {
  409. if (firstDLL == NULL) {
  410. printf("There is no list.\n");
  411. return;
  412. }
  413. struct nodeDLL *cur;
  414.  
  415. for (cur = firstDLL; cur != NULL; cur = cur->next)
  416. printf("%d ", cur->data);
  417. printf("\n");
  418. }
  419.  
  420. void postPrint_DLL(struct nodeDLL *tailDLL) //反向印出doubly linked list
  421. {
  422. if (tailDLL == NULL) {
  423. printf("There is no list.\n");
  424. return;
  425. }
  426. struct nodeDLL *cur;
  427.  
  428. for (cur = tailDLL; cur != NULL; cur = cur->prev)
  429. printf("%d ", cur->data);
  430. printf("\n");
  431. }
  432.  
  433. void clean_DLL(struct nodeDLL *firstDLL) //清除doubly linked list
  434. {
  435. struct nodeDLL *prev, *cur;
  436.  
  437. tailDLL = NULL;
  438. for (cur = firstDLL; cur != NULL;) {
  439. prev = cur;
  440. cur = cur->next;
  441. firstDLL = cur;
  442. free(prev);
  443. }
  444. firstDLL = NULL;
  445. }
  446.  
  447. void insert_to_DLL(struct nodeDLL **firstDLL, struct nodeDLL **tailDLL) //插入一新節點至doubly linked list
  448. {
  449. struct nodeDLL *new_node, *prev = NULL, *cur;
  450.  
  451. new_node = malloc(sizeof(struct nodeDLL)); //創造新節點空間
  452. if (new_node == NULL) {
  453. printf("Error: malloc failed.\n");
  454. return;
  455. }
  456. scanf("%d", &new_node->data); //讀入數字
  457. for (cur = *firstDLL; cur->data < new_node->data && cur->next != NULL;) { //定位
  458. prev = cur;
  459. cur = cur->next;
  460. }
  461. if (cur->data < new_node->data && cur->next == NULL) { //若原list無節點比新節點大，則新節點與最後一個節點連結，並改變tailDLL指向
  462. cur->next = new_node;
  463. new_node->next = NULL;
  464. new_node->prev = cur;
  465. *tailDLL = new_node;
  466. }
  467. else if (prev == NULL) { //若為最小節點
  468. if (cur->next == NULL) //若為第一個節點，則tailDLL指向它
  469. *tailDLL = new_node;
  470. else { //否則與首端節點連結，並改變first指向
  471. new_node->next = *firstDLL;
  472. cur->prev = new_node;
  473. *firstDLL = new_node;
  474. }
  475. new_node->prev = NULL;
  476. }
  477. else { //其他狀況則改變前一個、後一個及新節點的連結
  478. prev->next = new_node;
  479. new_node->next = cur;
  480. cur->prev = new_node;
  481. new_node->prev = prev;
  482. }
  483. }
  484.  
  485. void delete_from_DLL() //從list中刪除一個節點
  486. {
  487. int n;
  488. struct nodeDLL *cur, *prev = NULL;
  489.  
  490. if (firstDLL == NULL) { //若無list，則印出訊息
  491. printf("Nothing to delete.\n");
  492. return;
  493. }
  494. printf("Enter the number you want to delete: "); //印出要求
  495. scanf("%d", &n); //讀入欲刪除數字
  496. for (cur = firstDLL; cur != NULL && cur->data != n; prev = cur, cur = cur->next) //找節點
  497. ;
  498. if (cur == NULL) { //找不到則印出訊息
  499. printf("The number doesn't exist in the list.\n");
  500. return;
  501. }
  502. else if (prev == NULL) { //若為第一個節點則改變first指向
  503. firstDLL = cur->next;
  504. if (cur->next == NULL) //若list中只有一個節點則不動作
  505. ;
  506. else
  507. cur->next->prev = NULL; //否則第二個節點變為首端節點
  508. }
  509. else { //其他狀況則前一個節點與後一個節點連結
  510. prev->next = cur->next;
  511. if (cur->next == NULL) //若欲刪除最後一個節點，則tailDLL指向前一個節點
  512. tailDLL = prev;
  513. else
  514. cur->next->prev = prev;
  515. }
  516. free(cur); //釋放節點空間
  517. printf("The node has been deleted.\n"); //印出訊息
  518. }
  519.  
  520. void search_DLL() //搜尋節點
  521. {
  522. int n;
  523. struct nodeDLL *cur;
  524.  
  525. cur = firstDLL;
  526. printf("Enter the number you want to search: "); //印出要求
  527. scanf("%d", &n); //讀入欲搜尋數字
  528. for (; cur != NULL; cur = cur->next) //找
  529. if (cur->data == n) {
  530. printf("The number is in the list.\n"); //若找到則印出訊息
  531. return;
  532. }
  533. printf("The number doesn't exist in the list.\n"); //找不到也印出訊息
  534. }
  535.  
  536. void count_DLL() //計算list中有幾個節點
  537. {
  538. int num_nodes = 0;
  539. struct nodeDLL *cur;
  540.  
  541. for (cur = firstDLL; cur != NULL; cur = cur->next)
  542. num_nodes++;
  543. printf("There are %d nodes in the list.\n", num_nodes);
  544. }
  545.  
  546. void reverse_DLL() //反轉doubly linked list
  547. {
  548. struct nodeDLL *prev, *cur;
  549.  
  550. tailDLL = firstDLL; //將tailDLL指向首端節點
  551. cur = firstDLL;
  552. firstDLL = NULL;
  553. while (cur != NULL) { //交換節點間連結，並將firstDLL指向原尾端節點
  554. prev = cur;
  555. cur = cur->next;
  556. prev->prev = cur;
  557. prev->next = firstDLL;
  558. firstDLL = prev;
  559. }
  560. printf("The list has been reversed.\n"); //印出成功訊息
  561. }
  562.  
  563. void merge_DLL(int n) //將兩條doubly linked list合併成一條
  564. {
  565. int i;
  566. struct nodeDLL *head, *tail;
  567.  
  568. srand(time(NULL));
  569. n = rand() % 10 + 1;
  570. printf("Please enter %d numbers for the first list: ", n); //要求輸入第一條隨機長度的list
  571. build_a_DLL(&head, &tail, n); //創造doubly linked list
  572. n = rand() % 10 + 1;
  573. printf("Please enter %d numbers for the second list: ", n); //要求輸入另一條隨機長度的list
  574. for (i = 0; i < n; i++) //將list插入第一條list
  575. insert_to_DLL(&head, &tail);
  576. prePrint_DLL(head); //印出結果list
  577. printf("But the initial list won't change.\n"); //並不會改變最初創建的initial list
  578. clean_DLL(head); //清空list
  579. }
  580.  
  581. void split_DLL() //將list分成奇數和偶數並印出
  582. {
  583. struct nodeDLL *cur, *even = NULL, *odd = NULL;
  584.  
  585. for (cur = firstDLL; cur->data % 2 != 0 && cur->next != NULL; cur = cur->next) //找第一個偶數節點
  586. ;
  587. if (cur->data % 2 != 0 && cur->next == NULL) { //找不到偶數則印出訊息
  588. printf("There is no even number in the list.");
  589. return;
  590. }
  591. else
  592. even = cur;
  593. for (cur = firstDLL; cur->data % 2 == 0 && cur->next != NULL; cur = cur->next) //找第一個奇數節點
  594. ;
  595. if (cur->data % 2 == 0 && cur->next == NULL) { //找不到奇數則印出訊息
  596. printf("There is no odd number in the list.");
  597. return;
  598. }
  599. else
  600. odd = cur;
  601. cur = even;
  602. printf("The even list:\n%d ", cur->data); //依序印出偶數list
  603. while (cur->next != NULL) {
  604. cur = cur->next;
  605. while (cur->data % 2 != 0 && cur->next != NULL) //找下一個偶數並印出
  606. cur = cur->next;
  607. if (cur->data % 2 == 0)
  608. printf("%d ", cur->data);
  609. else
  610. break;
  611. }
  612. printf("\n");
  613. cur = odd;
  614. printf("The odd list:\n%d ", cur->data); //依序印出奇數list
  615. while (cur->next != NULL) {
  616. cur = cur->next;
  617. while (cur->data % 2 == 0 && cur->next != NULL) //找下一個奇數並印出
  618. cur = cur->next;
  619. if (cur->data % 2 != 0)
  620. printf("%d ", cur->data);
  621. else
  622. break;
  623. }
  624. printf("\n");
  625. }
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!