C 語言鏈表長整數加法：if 條件分支邏輯與符號位處理深度解析

開發者研讀長整數鏈表加法代碼，對 if(e1*e2==1) 等條件分支邏輯感到困惑。本文從演算法設計角度，逐行解析符號位編碼、同號/異號處理邏輯與進位/借位機制。

核心資料結構與符號編碼

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

// 表頭節點特殊設計：
// head->data =  1  表示正數
// head->data = -1  表示負數
// 實際數值節點存儲絕對值 (0-9999)
// 鏈表順序：表頭 → 最高位 → ... → 最低位 → 循環回表頭

關鍵變數含義

if 條件分支完整邏輯解析

第一層：同號 vs 異號

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 {
    // 【異號】：大絕對值減小絕對值，結果符號跟隨大者
    // s->data = p1->data*e1 + p2->data*e2 (已帶符號)
    if (s->data >= 0) {
        carry = 0;            // 結果為正，無借位
    } else {
        s->data += 10000;     // 結果為負，借位處理 (補碼思維)
        carry = -1;           // 標記借位
    }
}

後續迴圈：統一處理邏輯

// 每輪迴圈處理下一位
s->data = p1->data*e1 + p2->data*e2 + sum->data*carry;
//   當前位帶符號值        +  上一輪進位/借位影響

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; }
}

為什麼用 e1*e2==1 判斷同號？

• e1, e2 ∈ {1, -1}
• 同號：1*1=1 或 (-1)*(-1)=1 → e1*e2 == 1
• 異號：1*(-1)=-1 或 (-1)*1=-1 → e1*e2 == -1
• 這是數學技巧：避免寫 (e1==1 && e2==1) || (e1==-1 && e2==-1) 的冗長判斷

演算法核心流程圖

輸入兩長整數 → 建立雙向循環鏈表 (表頭存符號)
      ↓
從最低位開始 (p1=prior, p2=prior)
      ↓
同號? → 是 → 絕對值相加 + 進位傳播 → 結果符號=e1
  ↓ 否
異號 → 帶符號相加 (大減小) + 借位傳播 → 結果符號跟隨大絕對值
      ↓
處理剩餘高位 (單鏈表繼續)
      ↓
最終進位/借位處理
      ↓
移除最高位前導零
      ↓
輸出結果

代碼中潛在 Bug 提示

總結

這段代碼實作的是帶符號絕對值表示法的長整數加減法：

• e1*e2==1 是同號判斷的數學簡寫
• 同號走「絕對值相加 + 進位」，異號走「帶符號相加 + 借位」
• data * e1 將節點絕對值轉為帶符號值參與運算
• carry = 1/0/-1 分別表示進位/無/借位

理解「符號位分離、絕對值鏈表、進位借位傳播」三大核心機制，即可看懂全部條件分支邏輯。