鏈表操作 Bug 尋找挑戰：三個隱藏缺陷

編輯：關於C語言

題目背景

下列程式碼實作單向鏈表的基本操作（取值、插入、刪除、建立、合併），但隱藏 **三個關鍵 Bug**。請仔細閱讀並找出它們。

原始程式碼（已修正排版）

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

typedef struct LNode {
    void *data;
    struct LNode *next;
} LNode, *LinkList;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

/* 算法 2.8：取第 i 個元素 */
Status GetElem_L(LinkList L, int i, ElemType &e) {
    LinkList p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    if (!p || j > i) return OK;   // Bug 1 在此行
    e = *(ElemType*)p->data;      // 假設 data 直接存 int
    return OK;
}

/* 算法 2.9：插入第 i 個位置 */
Status ListInsert_L(LinkList &L, int i, ElemType e) {
    LinkList p = L;
    int j = 0;
    while (p && j < i-1) {
        p = p->next;
        ++j;
    }
    if (!p || j > i-1) return ERROR;

    LinkList s = (LinkList)malloc(sizeof(LNode)); // Bug 2：變數名衝突
    s->data = (void*)&e;        // Bug 3：存區域變數位址
    s->next = p->next;
    p->next = s;
    return OK;
}

/* 算法 2.10：刪除第 i 個元素 */
Status ListDelete_L(LinkList &L, int i, ElemType &e) {
    LinkList p = L, q;
    int j = 0;
    while (p->next && j < i-1) {   // 可能漏檢 p 本身
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i-1) return ERROR;
    q = p->next;
    p->next = q->next;             // 原碼寫 p-next=q-next (語法錯)
    e = *(ElemType*)q->data;
    free(q);
    return OK;
}

/* 算法 2.11：頭插法建表 */
void CreateList_L(LinkList &L, int n) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    for (int i = n; i > 0; --i) {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        scanf("%d", (int*)p->data); // 需配合 data 實際型別
        p->next = L->next;
        L->next = p;
    }
}

/* 算法 2.12：合併有序鏈表 */
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
    LinkList pa = La->next, pb = Lb->next;
    Lc = pc = La;           // pc 未宣告
    while (pa && pb) {
        if (*(ElemType*)pa->data <= *(ElemType*)pb->data) {
            pc->next = pa; pc = pa; pa = pa->next;
        } else {
            pc->next = pb; pc = pb; pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);               // 僅釋放頭節點，Lb 其餘節點已掛到 Lc
}

int main() { return 0; }

三大 Bug 詳細分析

Bug 1：GetElem_L 回傳值邏輯錯誤

if (!p || j > i) return OK;  // 應為 return ERROR;

當鏈表長度不足或 i 非法時，p 為 NULL 或 j > i，此時應回傳 **ERROR**，原碼回傳 **OK** 會導致呼叫端誤以為取值成功，後續使用未初始化的 e 引發 UB。

Bug 2：ListInsert_L 變數名稱衝突與型別錯誤

LinkList s = (LinkList)malloc(sizeof(LNode)); // 此處 s 已是 LinkList*
s->data = (void*)&e;        // 存區域變數 e 的位址！

原碼先宣告 LNode p; (非指標)，又用 s 未宣告直接賦值，編譯不過。
即便修正宣告，**將區域變數 e 的位址存入節點** 是嚴重錯誤：函數返回後 e 生命週期結束，節點持有懸空指標。
正確做法：s->data = malloc(sizeof(ElemType)); *(ElemType*)s->data = e; 或直接將 data 改為 ElemType data; 內嵌存值。

Bug 3：ListDelete_L 語法錯誤與邊界檢查不足

p-next = q-next;  // 應為 p->next = q->next;
while (p->next && j < i-1)  // 若 L 為空或 i=1 需額外處理

p-next 非法語法，應為 p->next。
迴圈條件 p->next 假設 p 非 NULL，若 L 為空表 (L->next == NULL) 直接進入迴圈會解參考 NULL。
建議改為 while (p && j < i-1) 並在迴圈後檢查 !p || !p->next。

其他潛在問題（加分項）

MergeList_L 中 pc 未宣告；合併後 free(Lb) 僅釋放頭節點，若 Lb 其餘節點未轉移所有權會洩漏（此處實際已轉移，但語意模糊）。
CreateList_L 使用 scanf("%d", (int*)p->data) 假設 data 指向有效 int 空間，但分配節點時未為 data 分配記憶體。
缺乏 DestroyList_L 釋放整表記憶體的介面。
資料型別耦合：void *data 強制呼叫端處理轉型，建議改用模板（C++）或巨集產生型別安全版本。

修正版關鍵片段

/* GetElem_L 修正 */
if (!p || j > i) return ERROR;
e = *(ElemType*)p->data;
return OK;

/* ListInsert_L 修正 */
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = malloc(sizeof(ElemType));
*(ElemType*)s->data = e;
s->next = p->next;
p->next = s;

/* ListDelete_L 修正 */
LinkList p = L;
int j = 0;
while (p && j < i-1) { p = p->next; ++j; }
if (!p || !p->next) return ERROR;
LinkList q = p->next;
p->next = q->next;
e = *(ElemType*)q->data;
free(q->data);
free(q);
return OK;

找出這三個 Bug 需具備：邊界條件敏感度、指標/記憶體生命週期觀念、語法細節眼力。歡迎在留言區討論更多隱藏問題！