您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言問答

C語言雙向鏈表深度解析：創建、查找、刪除關鍵代碼逐行註釋

編輯：C 語言問答

數據結構定義


struct node {
    char name[20];
    struct node *next;  // 後驅指針
    struct node *prior; // 前驅指針
};

每個節點包含**數據域** (name) 和**兩個指針域** (next 指向後繼，prior 指向前驅)。
形成雙向鏈表：head ↔ node1 ↔ node2 ↔ ... ↔ tail。

關鍵函數逐行註釋

1. 創建鏈表 `creat(n)`


struct node *creat(int n) {
    struct node *h, *p, *s;
    int i;
    h = (struct node*)malloc(sizeof(struct node)); // 分配頭節點 (不存有效數據)
    h->name[0] = '\0';                             // 頭節點標記為空串
    h->prior = NULL;                               // 頭節點無前驅
    h->next = NULL;                                // 頭節點暫無後繼
    p = h;                                         // p 為尾指針，初指向頭節點

    for (i = 0; i < n; i++) {
        s = (struct node*)malloc(sizeof(struct node)); // 分配新節點
        p->next = s;                              // 1. 當前尾節點 p 的 next 指向新節點 s
        printf("Input the %d student's name:", i+1);
        scanf("%s", s->name);                     // 讀取數據
        s->prior = p;                             // 2. 新節點 s 的 prior 指向前驅 p (雙向鏈接關鍵！)
        s->next = NULL;                           // 3. 新節點 s 暫為尾節點，next 為 NULL
        p = s;                                    // 4. 尾指針 p 後移至新節點 s
    }
    p->next = NULL;                               // 終止條件 (其實循環最後 s->next 已是 NULL)
    return h;                                     // 返回頭節點指針
}

雙向鏈接三步曲：p->next = s; s->prior = p; p = s; —— 先連後驅，再連前驅，最後移動尾指針。

2. 查找節點 `search(h, x)`


struct node *search(struct node *h, char *x) {
    struct node *p;
    char *y;
    p = h->next;                          // 從第一個有效節點開始 (跳過頭節點)
    while (p) {                           // 遍歷直到 NULL
        y = p->name;
        if (strcmp(y, x) == 0) return p;  // 找到返回節點指針
        else p = p->next;                 // 否則移至下一個
    }
    printf("cannot find datd!\n");
    return NULL;                          // 未找到返回 NULL (原代碼缺少返回，隱式返回隨機值，危險！)
}

3. 刪除節點 `del(p)` —— 核心難點


void del(struct node *p) {
    // 前提：p 非頭節點、非尾節點、鏈表至少 2 個有效節點
    p->next->prior = p->prior;  // 1. 後繼節點的 prior 指向 p 的前驅 (跳過 p)
    p->prior->next = p->next;   // 2. 前驅節點的 next 指向 p 的後繼 (跳過 p)
    free(p);                    // 3. 釋放 p 內存
}

圖解雙向刪除

刪除前：  ... ←→ [前驅] ←→ [p] ←→ [後繼] ←→ ...
               ↑           ↑           ↑
           p->prior     p           p->next

步驟1: p->next->prior = p->prior;
       後繼節點的 prior 指向改為前驅節點
       ... ←→ [前驅] ←→ [p]    [後繼] ←→ ...
               ↑           ↑      ↑
           p->prior     p      p->prior (已修改)

步驟2: p->prior->next = p->next;
       前驅節點的 next 指向改為後繼節點
       ... ←→ [前驅] ---------→ [後繼] ←→ ...
               ↑                 ↑
           p->prior           p->next

結果：p 被「繞過」，前驅與後繼直接雙向鏈接。釋放 p 完成刪除。

邊界條件處理 (原代碼缺失，必須補全)


void del_safe(struct node *p) {
    if (!p) return;                    // 空指針保護
    if (p->prior) p->prior->next = p->next; // 有前驅則連接
    if (p->next) p->next->prior = p->prior; // 有後繼則連接
    // 若 p 是頭節點後第一個，p->prior 是頭節點，頭節點 next 更新
    // 若 p 是尾節點，p->next 為 NULL，無需操作後繼
    free(p);
}

主函數流程

輸入節點數 number，調用 creat 建表。
遍歷打印鏈表 (sp = head->next; while(sp) { printf("%s", sp->name); sp=sp->next; })。
輸入要查找的姓名 sname，調用 search。
打印找到的姓名，調用 del(sp) 刪除。
再次遍歷打印驗證刪除結果。

原代碼 Bug 與隱患

問題	代碼位置	後果	修正
`search` 未找到無返回值	函數末尾	未定義行為，主函數 `sp` 成垃圾值，後續 `del` 崩潰	返回 `NULL`，主函數判斷 `if (!sp) { ... }`
`del` 不處理頭/尾/單節點	全函數	刪除首尾節點時解引用 NULL 崩潰	加邊界檢查 `if (p->prior)...`
`scanf("%s", sname)` 無長度限制	主函數	緩衝區溢出風險	`scanf("%19s", sname)`
`printf("%s", &*(sp->name))` 怪異寫法	打印處	等價 `sp->name`，但難讀	直接 `printf("%s", sp->name)`
頭節點數據域未用但佔內存	`creat`	浪費 1 節點空間 (可接受)	或改用無頭節點版本

總結

雙向鏈表核心操作：**創建時雙向鏈接 (p->next=s; s->prior=p;)、刪除時雙向繞過 (p->next->prior=p->prior; p->prior->next=p->next;)**。
原代碼邏輯框架正確，但**缺失邊界處理、錯誤返回、輸入安全**，屬典型「能跑通幸福路徑、遇異常即崩潰」教學代碼。實戰中必須補全健壯性檢查，封裝為 list_init/insert/erase/find/destroy 完整 ADT 接口。