C++稀疏多項式鏈表實現：加法乘法運算完整模板類與避坑指南

問題背景

使用鏈表實現稀疏多項式加法、乘法運算，遇到「輸出結果為0」的核心問題，根因在於析構函數導致臨時對象銷毀時釋放共享鏈表節點。

核心修復：移除析構函數自動釋放，改用手動管理

// 錯誤：析構函數自動刪除鏈表
~Polynomial() {
    Node* p = first;
    while (p) { Node* q = p->next; delete p; p = q; }
}

// 正確：提供手動釋放方法
void myfree() {
    Node* p = first, *q;
    while (p) { q = p->next; delete p; p = q; }
}

完整修正代碼關鍵點

1. 節點構造函數修復

Node(T x = 0, unsigned y = 0, Node* p = 0) {
    data.xishu = x;
    data.mi = y;
    next = p;  // 原代碼錯誤聲明了局部變量 Node* next = p;
}

2. 加法運算符優化

Polynomial operator+(const Polynomial& second) {
    Polynomial sum;
    Node *pa = first->next, *pb = second.first->next, *pc = sum.first;
    
    while (pa && pb) {
        if (pa->data.mi == pb->data.mi) {
            T x = pa->data.xishu + pb->data.xishu;
            if (x) {  // 系數不為0才創建節點
                pc->next = new Node(x, pa->data.mi);
                pc = pc->next;
                ++sum.num;
                sum.highestdigit = pa->data.mi;
            }
            pa = pa->next; pb = pb->next;
        } else if (pa->data.mi > pb->data.mi) {  // 降冪排列
            pc->next = new Node(pa->data.xishu, pa->data.mi);
            pc = pc->next; pa = pa->next;
            ++sum.num; sum.highestdigit = pa->data.mi;
        } else {
            pc->next = new Node(pb->data.xishu, pb->data.mi);
            pc = pc->next; pb = pb->next;
            ++sum.num; sum.highestdigit = pb->data.mi;
        }
    }
    // 處理剩餘節點...
    return sum;
}

3. 輸入初始化修復

void initial() {
    // 先釋放舊鏈表 (保留頭節點)
    Node* p = first->next, *q;
    while (p) { q = p->next; delete p; p = q; }
    p = first;
    
    num = 0; highestdigit = 0;
    T a; int b;
    while (cin >> a && a != 0 && cin >> b) {
        if (b >= highestdigit) highestdigit = b;
        ++num;
        p->next = new Node(a, b);
        p = p->next;
    }
    fflush(stdin); // 清理輸入緩衝
}

4. 輸出運算符健壯化

ostream& operator<<(ostream& out, Polynomial& a) {
    Node *p = a.first->next;
    if (p == NULL) return out;  // 空多項式
    
    if (p->data.xishu == 0) { out << endl; return out; }
    
    if (p->data.xishu != 1) out << p->data.xishu << "x^" << p->data.mi;
    else out << "x^" << p->data.mi;
    
    p = p->next;
    while (p) {
        out << '+';
        if (p->data.xishu != 1) out << p->data.xishu << "x^" << p->data.mi;
        else out << "x^" << p->data.mi;
        p = p->next;
    }
    return out;
}

測試驗證

int main() {
    Polynomial a, b, c;
    a.initial();  // 輸入如: 3 2  2 1  1 0  0 0
    cout << "a= " << a << endl;
    b.initial();
    cout << "b=" << b << endl;
    c = a + b;
    cout << "c=" << c << endl;
    
    a.myfree(); b.myfree(); c.myfree(); // 手動釋放
    return 0;
}

關鍵避坑總結