數據結構基石：線性表鏈式存儲結構深度解析與 C 語言實現

數據結構基石：線性表鏈式存儲結構深度解析與 C 語言實現

鏈式存儲結構不要求邏輯相鄰元素物理相鄰，通過指針串聯離散內存塊，完美解決了順序表「插刪需移動、擴容遷移」的痛點。本文將從結構定義、節點實現、建表算法、查找操作四個維度，配合 C 語言完整代碼，徹底攻克單鏈表核心知識點。

一、鏈式存儲核心概念

• 節點：數據域 + 指針域。數據域存值，指針域存後繼節點地址。
• 頭節點：附設在首元節點前，數據域可存長度或不存數據，指針域指向首元節點。統一了空表與非空表、首元節點與普通節點的操作邊界條件。
• 單鏈表：每個節點僅有一個指向後繼的指針，最後一個節點指針為 NULL。
• 邏輯順序 ≠ 物理順序：節點可散落在堆內存任意位置，靈活利用內存碎片。

二、節點定義與動態內存管理

typedef struct LNode {
    ElemType data;           // 數據域
    struct LNode *next;      // 指針域，指向下一個節點
} LNode, *LinkList;          // LinkList 本質是指向頭節點的指針

// 動態分配節點
LNode *p = (LNode*)malloc(sizeof(LNode));
if (!p) exit(OVERFLOW);      // 分配失敗處理

// 釋放節點
free(p);                     // p 必須指向 malloc 分配的地址

三、建表算法：頭插法 vs 尾插法

兩種方法時間複雜度均為 O(n)，但生成鏈表順序相反。

1. 頭插法

新節點總是插在頭節點之後，變成新的首元節點。輸入順序與鏈表順序逆序。

LinkList CreateList_H(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    int x;
    while (scanf("%d", &x), x != 9999) { // 以 9999 為結束標記
        LNode *p = (LNode*)malloc(sizeof(LNode));
        p->data = x;
        p->next = L->next;  // ① 先右：新節點指向原首元節點
        L->next = p;        // ② 後左：頭節點指向新節點
    }
    return L;
}

2. 尾插法

維護尾指針 r，新節點插在尾部，輸入順序與鏈表順序正序。

LinkList CreateList_R(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    LNode *r = L;           // 尾指針初始指向頭節點
    int x;
    while (scanf("%d", &x), x != 9999) {
        LNode *p = (LNode*)malloc(sizeof(LNode));
        p->data = x;
        p->next = NULL;
        r->next = p;        // 尾節點指向新節點
        r = p;              // 尾指針後移
    }
    return L;
}

關鍵口訣

凡涉及「鉤鏈/重鉤鏈」且未給出直接後繼，**必須遵循「先右後左」**，否則斷鏈丟失節點。

四、單鏈表查找操作

1. 按序號查找 GetElem(L, i)

從頭節點出發，順鏈掃描第 i 個節點。非隨機存取結構，時間複雜度 O(n)。

Status GetElem(LinkList L, int i, ElemType &e) {
    LNode *p = L->next; int j = 1;
    while (p && j < i) { p = p->next; ++j; }
    if (!p || j > i) return ERROR; // i 越界
    e = p->data;
    return OK;
}

2. 按值查找 LocateElem(L, key)

從首元節點遍歷，比較數據域與 key，找到返回節點指針，否則返回 NULL。平均 O(n)。

LNode* LocateElem(LinkList L, ElemType key) {
    LNode *p = L->next;
    while (p && p->data != key) p = p->next;
    return p; // 找到返回節點指針，未找到返回 NULL
}

五、插入與刪除操作

1. 插入 ListInsert(L, i, e)

在第 i 個位置前插入 e。核心：找到第 i-1 個節點，執行「先右後左」鉤鏈。

Status ListInsert(LinkList &L, int i, ElemType e) {
    LNode *p = L; int j = 0;
    while (p && j < i-1) { p = p->next; ++j; } // 找前驅
    if (!p || j > i-1) return ERROR;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;  // ① 先右
    p->next = s;        // ② 後左
    return OK;
}

2. 刪除 ListDelete(L, i, &e)

刪除第 i 個節點，並用 e 返回其值。核心：找到第 i-1 個節點，斷鏈釋放。

Status ListDelete(LinkList &L, int i, ElemType &e) {
    LNode *p = L; int j = 0;
    while (p->next && j < i-1) { p = p->next; ++j; } // 找前驅
    if (!p->next || j > i-1) return ERROR;
    LNode *q = p->next;      // q 指向被刪節點
    p->next = q->next;       // 斷鏈
    e = q->data;
    free(q);                 // 釋放
    return OK;
}

六、時間複雜度總結

七、總結

單鏈表以靈活的動態內存分配、O(1) 表頭插刪（頭插法）、無需預分配空間著稱，代價是查找為 O(n) 且額外指針空間開銷。掌握「頭節點統一邊界」、「先右後左鉤鏈」、「尾插法保持順序」三大核心技巧，配合熟練的 malloc/free 內存管理，即可自信應對各類鏈表考試與工程實踐。