void build_a_DLL(struct nodeDLL **firstDLL, struct nodeDLL **tailDLL, int n) //創造一個doubly linked list { int i; struct nodeDLL *new_node, *prev = NULL, *cur; new_node = malloc(sizeof(struct nodeDLL)); //宣告第一個節點空間 if (new_node == NULL) { printf("Error: malloc failed.\n"); return; } new_node->next = *firstDLL; //將first指向第一個節點 *firstDLL = new_node; for (i = 0; i < n; i++) { cur = *firstDLL; scanf("%d", &new_node->data); //讀入數字 while (cur->data < new_node->data && cur->next != NULL) { //定位 prev = cur; cur = cur->next; } if (cur->data < new_node->data && cur->next == NULL) { //若無節點內數字比新節點大,則新節點置於最後一個,並改變tailDLL指向 cur->next = new_node; new_node->next = NULL; new_node->prev = cur; *tailDLL = new_node; } else if (prev == NULL) { //若為最小節點 if (new_node->next == NULL) //若為第一個節點,則tailDLL指向它 *tailDLL = new_node; else { //否則只消改變first指向 new_node->next = *firstDLL; *firstDLL = new_node; } new_node->prev = NULL; } else { //其他狀況則改變前一個、後一個及新節點的連結 prev->next = new_node; new_node->next = cur; cur->prev = new_node; new_node->prev = prev; } new_node = malloc(sizeof(struct nodeDLL)); //再創另一個節點空間 if (new_node == NULL) { printf("Error: malloc failed.\n"); return; } if (i == n - 1) //若為最後一次執行for loop,則釋放新節點空間 free(new_node); } } void prePrint_DLL(struct nodeDLL *firstDLL) //正向印出doubly linked list { if (firstDLL == NULL) { printf("There is no list.\n"); return; } struct nodeDLL *cur; for (cur = firstDLL; cur != NULL; cur = cur->next) printf("%d ", cur->data); printf("\n"); } void postPrint_DLL(struct nodeDLL *tailDLL) //反向印出doubly linked list { if (tailDLL == NULL) { printf("There is no list.\n"); return; } struct nodeDLL *cur; for (cur = tailDLL; cur != NULL; cur = cur->prev) printf("%d ", cur->data); printf("\n"); } void clean_DLL(struct nodeDLL *firstDLL) //清除doubly linked list { struct nodeDLL *prev, *cur; tailDLL = NULL; for (cur = firstDLL; cur != NULL;) { prev = cur; cur = cur->next; firstDLL = cur; free(prev); } firstDLL = NULL; } void insert_to_DLL(struct nodeDLL **firstDLL, struct nodeDLL **tailDLL) //插入一新節點至doubly linked list { struct nodeDLL *new_node, *prev = NULL, *cur; new_node = malloc(sizeof(struct nodeDLL)); //創造新節點空間 if (new_node == NULL) { printf("Error: malloc failed.\n"); return; } scanf("%d", &new_node->data); //讀入數字 for (cur = *firstDLL; cur->data < new_node->data && cur->next != NULL;) { //定位 prev = cur; cur = cur->next; } if (cur->data < new_node->data && cur->next == NULL) { //若原list無節點比新節點大,則新節點與最後一個節點連結,並改變tailDLL指向 cur->next = new_node; new_node->next = NULL; new_node->prev = cur; *tailDLL = new_node; } else if (prev == NULL) { //若為最小節點 if (cur->next == NULL) //若為第一個節點,則tailDLL指向它 *tailDLL = new_node; else { //否則與首端節點連結,並改變first指向 new_node->next = *firstDLL; cur->prev = new_node; *firstDLL = new_node; } new_node->prev = NULL; } else { //其他狀況則改變前一個、後一個及新節點的連結 prev->next = new_node; new_node->next = cur; cur->prev = new_node; new_node->prev = prev; } } void delete_from_DLL() //從list中刪除一個節點 { int n; struct nodeDLL *cur, *prev = NULL; if (firstDLL == NULL) { //若無list,則印出訊息 printf("Nothing to delete.\n"); return; } printf("Enter the number you want to delete: "); //印出要求 scanf("%d", &n); //讀入欲刪除數字 for (cur = firstDLL; cur != NULL && cur->data != n; prev = cur, cur = cur->next) //找節點 ; if (cur == NULL) { //找不到則印出訊息 printf("The number doesn't exist in the list.\n"); return; } else if (prev == NULL) { //若為第一個節點則改變first指向 firstDLL = cur->next; if (cur->next == NULL) //若list中只有一個節點則不動作 ; else cur->next->prev = NULL; //否則第二個節點變為首端節點 } else { //其他狀況則前一個節點與後一個節點連結 prev->next = cur->next; if (cur->next == NULL) //若欲刪除最後一個節點,則tailDLL指向前一個節點 tailDLL = prev; else cur->next->prev = prev; } free(cur); //釋放節點空間 printf("The node has been deleted.\n"); //印出訊息 } void search_DLL() //搜尋節點 { int n, num_node = 1; struct nodeDLL *cur; cur = firstDLL; printf("Enter the number you want to search: "); //印出要求 scanf("%d", &n); //讀入欲搜尋數字 for (; cur != NULL; cur = cur->next, num_node++) //找 if (cur->data == n) { printf("The number is in No.%d list.\n", num_node); //若找到則印出訊息 return; } printf("The number doesn't exist in the list.\n"); //找不到也印出訊息 } void count_DLL() //計算list中有幾個節點 { int num_nodes = 0; struct nodeDLL *cur; for (cur = firstDLL; cur != NULL; cur = cur->next) num_nodes++; printf("There are %d nodes in the list.\n", num_nodes); } void reverse_DLL() //反轉doubly linked list { struct nodeDLL *prev, *cur; tailDLL = firstDLL; //將tailDLL指向首端節點 cur = firstDLL; firstDLL = NULL; while (cur != NULL) { //交換節點間連結,並將firstDLL指向原尾端節點 prev = cur; cur = cur->next; prev->prev = cur; prev->next = firstDLL; firstDLL = prev; } printf("The list has been reversed.\n"); //印出成功訊息 } void merge_DLL(int n) //將兩條doubly linked list合併成一條 { int i; struct nodeDLL *head = NULL, *tail = NULL; srand(time(NULL)); n = rand() % 10 + 1; printf("Please enter %d numbers for the first list: ", n); //要求輸入第一條隨機長度的list build_a_DLL(&head, &tail, n); //創造doubly linked list n = rand() % 10 + 1; printf("Please enter %d numbers for the second list: ", n); //要求輸入另一條隨機長度的list for (i = 0; i < n; i++) //將list插入第一條list insert_to_DLL(&head, &tail); printf("The merged list:\n"); prePrint_DLL(head); //印出結果list printf("But the initial list won't change.\n"); //並不會改變最初創建的initial list clean_DLL(head); //清空list } void split_DLL() //將list分成奇數和偶數並印出 { struct nodeDLL *cur, *even = NULL, *odd = NULL; for (cur = firstDLL; cur->data % 2 != 0 && cur->next != NULL; cur = cur->next) //找第一個偶數節點 ; if (cur->data % 2 != 0 && cur->next == NULL) { //找不到偶數則印出訊息 printf("There is no even number in the list."); return; } else even = cur; for (cur = firstDLL; cur->data % 2 == 0 && cur->next != NULL; cur = cur->next) //找第一個奇數節點 ; if (cur->data % 2 == 0 && cur->next == NULL) { //找不到奇數則印出訊息 printf("There is no odd number in the list."); return; } else odd = cur; cur = even; printf("The even list:\n%d ", cur->data); //依序印出偶數list while (cur->next != NULL) { cur = cur->next; while (cur->data % 2 != 0 && cur->next != NULL) //找下一個偶數並印出 cur = cur->next; if (cur->data % 2 == 0) printf("%d ", cur->data); else break; } printf("\n"); cur = odd; printf("The odd list:\n%d ", cur->data); //依序印出奇數list while (cur->next != NULL) { cur = cur->next; while (cur->data % 2 == 0 && cur->next != NULL) //找下一個奇數並印出 cur = cur->next; if (cur->data % 2 != 0) printf("%d ", cur->data); else break; } printf("\n"); }
Google Code Prettify
2011年1月4日 星期二
C - Linked List (鏈結串列) Part 2
以下為Doubly Linked List的部分:
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言