C - Linked List (鏈結串列) Part 2

以下為Doubly Linked List的部分：

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");
}