單鏈表 GetElem 函數邏輯漏洞深度剖析：那個 if 條件真的錯了嗎？

問題代碼回顧

教材中常見的單鏈表按位序查找函數 GetElem：

Status GetElem(LinkList L, int i, ElemType &e) {
    LinkList p = L->next;  // 首元節點
    int j = 1;             // 計數器

    while (p && j < i) { // 尋找第 i 個節點
        p = p->next;
        ++j;
    }

    if (!p || j > i)     // 【爭議點】若未找到則返回 ERROR
        return ERROR;

    e = p->data;
    return OK;
}

作者質疑：if (!p || j > i) 中的 j > i 是多餘還是錯誤？

作者認為：循環結束時只有兩種情況：

1. p == NULL（遍歷到表尾仍未到第 i 個）
2. j == i（正好找到第 i 個節點）

因此 j > i 永不成立，條件等價於 if (!p)，寫 j > i 是邏輯冗餘甚至誤導。

深度驗證：真的永不成立嗎？

讓我們嚴格推導循環不變量：

• 循環前：p 指向第 j 個節點（初始 j=1，p 指向首元）
• 每次迭代：p 後移一位，j++，不變量保持
• 循環條件：p != NULL && j < i

循環終止時，必有 p == NULL 或 j >= i。結合不變量：

• 若 p == NULL：表長 < i，未找到
• 若 j >= i：因不變量 j 每次只增 1，且循環條件為 j < i，故退出時必有 j == i

結論：j > i 確實永不可能為真。

為什麼教材還這麼寫？

1. 防禦性編程習慣：雖然邏輯上不可能，但顯式判斷 j > i 可防範未來代碼修改導致的邏輯錯誤（如將循環條件改為 j <= i）
2. 統一錯誤語義：!p 表示「越界」，j > i 表示「邏輯異常」，分開處理便於擴展錯誤碼
3. 教學示範完整邊界：強調「未找到」包含兩類：越界與邏輯錯誤

更優雅的寫法

Status GetElem(LinkList L, int i, ElemType &e) {
    if (i < 1) return ERROR;           // 先檢查合法性
    LinkList p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    if (!p) return ERROR;              // 只有這一種失敗情況
    e = p->data;
    return OK;
}

總結

作者的直覺完全正確：j > i 在當前邏輯下永不成立，屬於冗餘防禦代碼。但這並非「錯誤」，而是風格差異。理解循環不變量、嚴格推導邊界條件，才是數據結構學習的核心收穫——比背誦教材代碼重要得多。