C語言自學攻略-鏈結串列進階教學與應用

相信讀者現在對於鏈結串列有了更多的認識，所以我再進一步，示範更多關於鏈結串列的操作，這部分示範會將程式模組化。將鏈結串列的操作寫進一個標頭檔，並在主程式中引入。

#ifndef LINKLIST_H
#define LINKLIST_H

#include <stdio.h>
#include <stdlib.h>

/* 
 * 定義節點結構: 
 *  - data: 資料 
 *  - next: 指向下一個節點的指標 
 */
struct node {
    int data;
    struct node *next;
};

typedef struct node NODE;  /* 將 struct node 定義成 NODE 型態 */

/* 函式原型宣告 */
NODE *createList(int *, int);    /* 串列建立函數 */
void printList(NODE *);           /* 串列列印函數 */
void freeList(NODE *);            /* 釋放串列記憶體函數 */
NODE *searchNode(NODE *, int);   /* 搜尋節點函數 */
void insertNode(NODE**, NODE *, int);    /* 插入節點函數 */
NODE *deleteNode(NODE *, NODE *); /* 刪除節點函數 */
NODE *reverseList(NODE *);        /* 反轉串列函數 */

#endif

#include "linklist.h"
/* 
createList()：根據傳入的陣列 arr 與長度 len，依序建立鏈結串列。
回傳鏈結串列的第一個節點 (Head)。
*/
NODE *createList(int *arr, int len)
{
    /* 當沒有任何資料時，直接回傳 NULL 表示空串列 */
    if (len == 0) {
        return NULL;
    }

    NODE *Head = NULL;      /* 用來記錄串列的第一個節點 */
    NODE *current = NULL;    /* 用來指向目前新配置的節點 */
    NODE *previous = NULL;   /* 用來記錄前一個節點，以便串接 */

    for(int i = 0; i < len; i++)
    {
        /* 配置一個新的節點空間 */
        current = (NODE *) malloc(sizeof(NODE));
        current->data = arr[i];  /* 設定節點的資料成員 */
        current->next = NULL;    /* 先將新節點的 next 設為 NULL */

        if(i == 0) {
            /* 若是第一個節點，就將 Head 指向它 */
            Head = current;
        } else {
            /* 不是第一個節點的話，就將前一個節點的 next 指向當前節點 */
            previous->next = current;
        }
        /* 將 previous 移到目前節點，以方便下一圈的串接 */
        previous = current;
    }
    return Head;    /* 最後回傳第一個節點以利接下來的操作。 */
}

• 首先，建立函式要求您提供陣列內容和長度，有了兩者，我們就可以照著先前的邏輯一一去設定鏈結串列的節點資訊。

好，接著實作列印函式的部分，接在createList()後面:

/*
printList()：輸出串列中所有節點的 data 值。
若串列為空，則印出 "List is empty!"。
*/
void printList(NODE *Head)
{
    if(Head == NULL) {
        printf("List is empty!\n");
        return;
    }

    NODE *node = Head;  /* 暫存指標，用來遍歷串列 */
    while(node != NULL)
    {
        printf("%3d", node->data); /* 印出目前節點資料 */
        node = node->next;        /* 移動到下一個節點 */
    }
    printf("\n");
}

• 該函式不需要回傳值，所以設為void ，只要傳入該函式鏈結串列的第一個節點，就可以遍歷串列的資訊。

接著實作釋放串列記憶體 的部分:

/*
freeList()：釋放整個串列所佔據的動態記憶體空間。
*/
void freeList(NODE *Head)
{
    NODE *current = Head;
    NODE *tmp;

    while (current != NULL)
    {
        tmp = current;       /* 先記錄目前節點 */
        current = current->next; /* 讓 current 指向下一個節點 */
        free(tmp);           /* 釋放剛剛記錄的節點 */
    }
}

• 概念差不多，該函式不需要回傳值，所以設為void，只要傳入該函式鏈結串列的第一個節點，就可以遍歷串列並釋放記憶體。

接著實作搜尋節點函數 的部分，這對於我們之後插入與刪除節點非常有關連:

/*
searchNode()：在串列中搜尋第一個 data 等於 item 的節點。
若找到，回傳該節點的位址；若找不到，回傳 NULL。
*/
NODE* searchNode(NODE *Head, int item)
{
    NODE *node = Head;
    while (node != NULL)
    {
        if (node->data == item) {
            return node;  /* 找到目標值就回傳該節點位址 */
        } else {
            node = node->next;  /* 繼續往下一個節點找 */
        }
    }
    /* 如果走完串列皆未找到，回傳 NULL */
    return NULL;
}

接著實作插入節點 的部分:

/*
insertNode()：在指定的 node 節點之後插入一個新的節點，新節點的 data 為 item。
*/
void insertNode(NODE **Head, NODE *node, int item)
{
		/* 我們在主程式中已經檢查過 found != NULL 才執行 插入的動作， 所以以下程式碼沒有必要 */
		/* 
		不過，某些情況下，你會希望「若串列是空的，仍能用 insertNode() 來插入第一個節點」，所以可能會需要檢查 node == NULL ，
		並執行相對應的狀況操作，不過這邊我不多做討論。
		*/
		
		/* 
		if (node == NULL) {
        printf("Error: The given node is NULL. Cannot insert.\n");
        return;
    }
    */
    NODE *newnode = (NODE *) malloc(sizeof(NODE)); /* 配置新節點記憶體 */
    newnode->data = item;         /* 新節點資料設置為 item */
    
    /* 如果要插入到第一個節點前 */
    if (node == *Head) {
		    newnode->next = *Head;   /* 將 newnode的next 指向下一個節點 */
        *Head = newnode;         /* 將 Head 指向新節點 */
    }
    else{
		    /* 新節點的 next 先接在原 node->next 之後 */
		    newnode->next = node->next;
		
				    /* 再把原 node->next 指向新節點，完成插入 */
		    node->next = newnode;
    }
}

• 注意NODE **Head 是二次指標，指向串列頭部的指標。

下面三張圖，分別顯示了插入頭部、插入尾部、以及插入任一地方的視覺化圖像，供讀者參考。

• 插入頭部:

• 插入尾部:

• 插入任一地方:

接著實作刪除節點 的部分:

/*
deleteNode()：刪除指定的 node，並回傳串列第一個節點的位址。
假設 node 一定存在於串列之中。
*/
NODE* deleteNode(NODE *Head, NODE *node)
{
    /* 若串列為空，無法刪除 */
    if (Head == NULL)
    {
        printf("Nothing to delete!\n");
        return NULL;
    }
    
    /* 如果要刪除的是第一個節點 */
    if (node == Head) {
        Head = Head->next;      /* 將 Head 指向下一個節點 */
    } else {
        /* 不是第一個節點則需要先找到 node 的前一個節點 */
        NODE *ptr = Head;
        while (ptr->next != node) {
            ptr = ptr->next;
        }
        /* ptr->next 現在就是 node，故重新串接以跳過 node */
        ptr->next = node->next;
    }
    free(node); /* 釋放要刪除的節點 */
    return Head;
}

下面三張圖，分別顯示了刪除頭部、刪除尾部、以及刪除任一地方的視覺化圖像，供讀者參考。

• 刪除頭部:

• 刪除尾部:

• 刪除任一地方:

接著實作反轉串列 的部分:

/*
reverseList()：反轉整個鏈結串列，回傳反轉後的第一個節點位址。
*/
NODE *reverseList(NODE *Head)
{
    NODE *previous = NULL;    /* 指向前一個節點的指標 */
    NODE *current = Head;/* 指向目前節點的指標 */
    NODE *next = NULL;    /* 暫存下一個節點的指標 */

    while (current != NULL)
    {
        next = current->next;      /* 暫存下一個節點 */
        current->next = previous;  /* 將目前節點的 next 指向前一個節點（反轉） */
        previous = current;        /* 移動 previous 到目前節點 */
        current = next;            /* current 移動到下一個節點（即原本的 current->next） */
    }
    /* 當 current 走到 NULL 時，previous 即為新的第一個節點 */
    return previous;
}

下面提供反轉串列的視覺化圖像，供讀者參考。

• 前面三個步驟圖說明了一次迴圈內的做的事，最後一個步驟圖顯示下一次迴圈內的所有步驟。
• 這邊讀者可以繼續按照步驟推導出最後的反轉結果。

目前，我們已經實作了所有的函式，接著就要撰寫主程式來進行測試。

/* 
main.c
*/
#include "linklist.h"

int main(void)
{
    /* 測試用的整數陣列 */
    int arr[] = {10, 20, 30, 40, 50};
    int len = sizeof(arr) / sizeof(arr[0]);

    /* 1. 建立串列並列印 */
    NODE *first = createList(arr, len);
    printf("建立完成後的串列: ");
    printList(first);

    /* 2. 搜尋節點 */
    int target = 10;
    NODE *found = searchNode(first, target);
    if (found != NULL) {
        printf("找到節點，節點值為: %d\n", found->data);
    } else {
        printf("未找到節點值為 %d 的節點\n", target);
    }

    /* 3. 插入節點：*/
    if (found != NULL) {
        insertNode(&first, found, 99);
        printf("在頭部插入節點，結果串列: ");
        printList(first);

        target = 30;
        found = searchNode(first, target);
        insertNode(&first, found, 67);
        printf("在值為 %d 的節點之後插入 67，結果串列: ", target);
        printList(first);
    }

    /* 4. 刪除節點：先嘗試刪除第一個節點 */
    if (first != NULL) {
        first = deleteNode(first, first);
        printf("刪除第一個節點後的串列: ");
        printList(first);
    }

    /* 5. 搜尋並刪除某個值（例如 40）的節點 */
    NODE *node40 = searchNode(first, 40);
    if (node40 != NULL) {
        first = deleteNode(first, node40);
        printf("刪除值為 40 的節點後的串列: ");
        printList(first);
    } else {
        printf("找不到值為 40 的節點，無法刪除\n");
    }

    /* 6. 測試串列反轉 */
    printf("反轉前的串列: ");
    printList(first);
    first = reverseList(first);
    printf("反轉後的串列: ");
    printList(first);

    /* 7. 釋放串列 */
    freeList(first);
    first = NULL;

    /* 8. 測試空串列情況: 再次嘗試刪除（應顯示空串列訊息） */
    first = deleteNode(first, first); // 這裡傳入 NULL, 會直接觸發 "Nothing to delete!"
    printList(first); // 印出空串列

    return 0;
}

最後，要測試的話，請照著以下步驟:

1. 先將上述三個檔案（linklist.h、linklist.c、main.c）放在同一個資料夾下。
2. 在終端機（Terminal）或命令列（Command Prompt）中，移動到該資料夾後編譯：

gcc main.c linklist.c -o main

3. 然後執行程式:

./main.exe

4. 最後觀察輸出結果

如此，我們就完成了鏈結串列的簡單操作之練習。