C++ 稀疏多項式鏈表實現：加法與乘法算法完善版

數據結構設計

template 
class Polynomial {
    struct Term { T coef; int exp; };
    struct Node { Term data; Node* next; };
    Node* head;      // 頭節點（哨兵）
    int termCount;   // 非零項數
    int maxExp;      // 最高次數
    // ...
};

• 升冪存儲（次數遞增），便於合並同類項。
• 頭節點簡化邊界條件（插入/刪除無需特判頭尾）。
• 項係數為 0 不存入，保持稀疏性。

核心算法：加法

Polynomial operator+(const Polynomial& rhs) const {
    Polynomial sum;
    Node *pa = head->next, *pb = rhs.head->next, *pc = sum.head;
    while (pa && pb) {
        if (pa->data.exp == pb->data.exp) {
            T c = pa->data.coef + pb->data.coef;
            if (c != 0) { pc->next = new Node{{c, pa->data.exp}, nullptr}; pc = pc->next; sum.termCount++; }
            pa = pa->next; pb = pb->next;
        } else if (pa->data.exp < pb->data.exp) {
            pc->next = new Node{pa->data, nullptr}; pc = pc->next; pa = pa->next; sum.termCount++;
        } else {
            pc->next = new Node{pb->data, nullptr}; pc = pc->next; pb = pb->next; sum.termCount++;
        }
    }
    while (pa) { pc->next = new Node{pa->data, nullptr}; pc = pc->next; pa = pa->next; sum.termCount++; }
    while (pb) { pc->next = new Node{pb->data, nullptr}; pc = pc->next; pb = pb->next; sum.termCount++; }
    return sum;
}

核心算法：乘法

Polynomial operator*(const Polynomial& rhs) const {
    Polynomial result;
    for (Node *pa = head->next; pa; pa = pa->next) {
        Polynomial temp;
        Node *pt = temp.head;
        for (Node *pb = rhs.head->next; pb; pb = pb->next) {
            T c = pa->data.coef * pb->data.coef;
            int e = pa->data.exp + pb->data.exp; // 次數相加
            if (c != 0) {
                pt->next = new Node{{c, e}, nullptr};
                pt = pt->next;
                temp.termCount++;
            }
        }
        result = result + temp; // 利用已實現的加法累加
    }
    return result;
}

關鍵修正點（對比原帖）

1. 乘法次數計算：`exp = pa->exp + pb->exp`（原帖誤為乘法）。
2. 臨時多項式 `temp` 每輪外層循環重置，避免殘留數據。
3. 內存管理：析構函數遞歸釋放鏈表，賦值運算符實現深拷貝（或禁用複製，改用移動語義 C++11）。
4. 輸入終止條件：係數為 0 結束，避免無限循環。

測試用例

int main() {
    Polynomial A, B, C, D;
    // 輸入 A: 1 0  2 1  0 (表示 1 + 2x)
    // 輸入 B: 3 0  4 2  0 (表示 3 + 4x^2)
    A.initial(); B.initial();
    C = A + B; // 4 + 2x + 4x^2
    D = A * B; // 3 + 6x + 4x^2 + 8x^3
    cout << "A=" << A << "\nB=" << B << "\nC=" << C << "\nD=" << D << endl;
    return 0;
}