C 語言鏈表實作長整數加法：異號相加 Bug 根因分析與修正方案

開發者實作雙向鏈表儲存長整數 (每節點 4 位數) 進行加法，發現異號相加 (如 -2 + 1) 結果錯誤輸出 -1,9999，且 0+0 也異常。本文深度分析演算法邏輯缺陷並提供修正思路。

核心資料結構

typedef struct node {
    int data;           // 節點數值 (0-9999)
    struct node *prior; // 前驅指標
    struct node *next;  // 後繼指標
} node;

// 表頭節點特殊用法：
// head->data = 1 (正數) 或 -1 (負數)  — 符號位
// head->next 指向最高位節點 (萬位)
// 尾節點 next 指向 head->next (循環雙向鏈表)

演算法流程回顧

1. create()：讀取逗號分隔輸入 (如 1,2345,6789)，建立循環雙向鏈表，表頭存符號
2. add_Num()：從最低位 (尾節點) 向最高位 (頭節點) 逐節點相加，處理進位
3. output()：從最高位輸出，補齊前導零

異號相加 Bug 根因分析

當前邏輯缺陷

在 add_Num() 中，異號處理邏輯 (e1*e2 != 1) 存在根本性錯誤：

// 當前錯誤邏輯片段
if (e1 * e2 == 1) { // 同號
    sum->data = e1;
    s->data = abs(s->data);
    if (s->data >= 10000) { s->data -= 10000; carry = 1; }
    else carry = 0;
} else { // 異號 — 這裡邏輯錯誤！
    if (s->data >= 0) carry = 0;
    else { s->data += 10000; carry = -1; }
}

為什麼 -2 + 1 會輸出 -1,9999？

• 輸入：num1 = -2 (表頭 -1, 節點 2), num2 = 1 (表頭 1, 節點 1)
• 相加：s->data = 2*(-1) + 1*1 = -1
• 異號分支：s->data < 0 → s->data += 10000 = 9999, carry = -1
• 結果表頭符號取 e1 (即 -1)，輸出 -1,9999
• 本質錯誤：演算法嘗試用「補數」思維處理異號減法，但鏈表儲存的是絕對值 + 符號位，非補數表示，導致借位邏輯錯亂

正確處理異號相加的策略

異號相加 = 大絕對值減小絕對值，結果符號跟隨大絕對值

修正步驟

1. 比較絕對值大小：遍歷鏈表比較兩數絕對值 (忽略表頭符號)
2. 大減小：將較大絕對值鏈表減去較小絕對值鏈表
3. 處理借位：從低位向高位借位 (反向進位)
4. 設定結果符號：結果表頭符號 = 較大絕對值原本的符號
5. 移除前導零：最高位若為 0 且非唯一節點，刪除節點

參考實作資源

建議參考經典教學實作：

• 長整數加法鏈表完整實作 (CSDN)
• 大整數運算演算法詳解 (新浪部落格)
• 百度文檔：鏈表實作大整數加減法

重構建議

若非教學必須用鏈表，現代 C 語言建議：

• 使用 GMP (GNU Multiple Precision) 庫：mpz_t 類型支援任意精度整數
• 或 C++ boost::multiprecision::cpp_int
• 自行實作時，改用動態陣列 (vector) 儲存每位數字，索引運算比指標操作簡單、除錯容易

總結

鏈表長整數加法的異號 Bug 根因在於符號-絕對值表示法下錯用補數借位邏輯。正確做法是分離「比較大小→大減小→借位→設定符號」四步驟。建議教學階段先用陣列實作掌握核心演算法，再挑戰指標版本；實務專案直接採用成熟多精度庫。