鏈表核心操作全解析：插入、刪除、遍歷、排序與 C 語言完整實作

鏈表節點操作基礎

鏈表由離散節點透過指標串聯。所有操作核心都是「修改指標指向」。假設節點結構：

typedef struct Node {
    int data;
    struct Node *pNext;
} NODE, *PNODE;

1. 在節點 p 後插入節點 q

方法一：用臨時變量

PNODE r = p->pNext; // 保存 p 原後繼
p->pNext = q;       // p 指向 q
q->pNext = r;       // q 指向原後繼

方法二：無臨時變量（兩步走）

q->pNext = p->pNext; // q 指向 p 的後繼
p->pNext = q;        // p 指向 q

方法二更簡潔，但需注意順序不可逆。

2. 刪除 p 之後的節點

PNODE r = p->pNext;          // 保存待刪節點
p->pNext = p->pNext->pNext;  // 跳過待刪節點
free(r);                     // 釋放記憶體
r = NULL;                    // 避免野指標

3. 判斷鏈表是否為空

bool IsEmpty(PNODE pHead) {
    return pHead->pNext == NULL; // 僅有頭節點視為空
}

完整功能實作：帶頭節點的單鏈表

以下代碼實現：創建、遍歷、求長、插入、刪除、查找、修改、排序。

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

typedef struct Node {
    int data;
    struct Node *pNext;
} NODE, *PNODE;

// --- 函數聲明 ---
PNODE CreateList();
void TraverseList(PNODE);
bool IsEmpty(PNODE);
int Length(PNODE);
bool InsertNode(PNODE, int, int);
bool DeleteNode(PNODE, int, int *);
bool QueryNode(PNODE, int);
bool ModifyNode(PNODE, int, int);
void SortList(PNODE);

int main() {
    PNODE pHead = CreateList();
    if (Length(pHead) == 0) {
        printf("鏈表無有效節點，退出程序！\n");
        return -1;
    }
    TraverseList(pHead);

    if (InsertNode(pHead, 2, 100)) {
        printf("插入後：");
        TraverseList(pHead);
    }

    SortList(pHead);
    printf("排序後：");
    TraverseList(pHead);
    return 0;
}

// --- 實作 ---
PNODE CreateList() {
    int len, i, val;
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (!pHead) exit(-1);
    pHead->pNext = NULL;
    PNODE pTail = pHead;

    printf("請輸入節點個數：");
    scanf("%d", &len);
    for (i = 0; i < len; i++) {
        printf("第 %d 個節點值：", i+1);
        scanf("%d", &val);
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (!pNew) exit(-1);
        pNew->data = val;
        pNew->pNext = NULL;
        pTail->pNext = pNew;
        pTail = pNew;
    }
    return pHead;
}

void TraverseList(PNODE pHead) {
    PNODE p = pHead->pNext;
    printf("遍歷整個鏈表：");
    while (p) {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}

bool IsEmpty(PNODE pHead) {
    return pHead->pNext == NULL;
}

int Length(PNODE pHead) {
    int len = 0;
    PNODE p = pHead->pNext;
    while (p) { len++; p = p->pNext; }
    return len;
}

bool InsertNode(PNODE pHead, int pos, int val) {
    int i = 0;
    PNODE p = pHead;
    // 找到第 pos-1 個節點
    while (p && i < pos - 1) { p = p->pNext; i++; }
    if (!p || i > pos - 1) return false; // 位置非法

    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (!pNew) exit(-1);
    pNew->data = val;
    pNew->pNext = p->pNext;
    p->pNext = pNew;
    return true;
}

bool DeleteNode(PNODE pHead, int pos, int *pVal) {
    int i = 0;
    PNODE p = pHead;
    while (p->pNext && i < pos - 1) { p = p->pNext; i++; }
    if (!p->pNext || i > pos - 1) return false;

    PNODE q = p->pNext;
    *pVal = q->data;
    p->pNext = q->pNext;
    free(q);
    return true;
}

void SortList(PNODE pHead) {
    int len = Length(pHead);
    for (int i = 0, p = pHead->pNext; i < len - 1; p = p->pNext, i++) {
        for (int j = i + 1, q = p->pNext; j < len; q = q->pNext, j++) {
            if (p->data > q->data) {
                int t = p->data; p->data = q->data; q->data = t;
            }
        }
    }
}

bool QueryNode(PNODE pHead, int pos) {
    int i = 0;
    PNODE p = pHead;
    while (p->pNext && i < pos - 1) { p = p->pNext; i++; }
    if (!p->pNext || i > pos - 1) return false;
    printf("第 %d 號節點值：%d\n", pos, p->pNext->data);
    return true;
}

bool ModifyNode(PNODE pHead, int pos, int val) {
    int i = 0;
    PNODE p = pHead;
    while (p->pNext && i < pos - 1) { p = p->pNext; i++; }
    if (!p->pNext || i > pos - 1) return false;
    p->pNext->data = val;
    printf("修改第 %d 號節點值為：%d\n", pos, val);
    return true;
}

數據結構觀念補充

狹義 vs 廣義

• 狹義數據結構：只研究數據存儲（個體+關係）。
• 廣義數據結構：包含存儲與操作。算法即對存儲數據的操作。

算法與存儲的關係

• 狹義：算法依賴存儲方式（如鏈表插入 O(1) 但查找 O(n)）。
• 廣義（泛型思想）：算法與存儲解耦。C++ 模板、運算符重載、指標實現泛型，同一算法適用 vector、list、deque。

線性結構對比

VC++ 編譯注意事項

1. bool 型別：C 編譯器不支援，需用 C++ 編譯器（副檔名 .cpp 或設定 /TP）。
2. 變量聲明位置：C89 要求所有變量聲明在函數開頭；C99 及 C++ 允許隨處聲明。錯誤 illegal use of this type as an expression 常因混用 C 編譯器編譯 C++ 風格代碼。