單鏈表實現多項式加減乘運算：完整代碼結構與模組設計

帶頭節點單鏈表實現多項式運算：模組化設計指南

採用帶頭節點的單鏈表存儲多項式，每節點含係數與指數。模組劃分為頭文件、庫函數、測試程式，結構清晰便於維護擴展。

模組架構

• poly.h：數據結構定義、函數聲明
• fatal.h：錯誤處理宏
• poly.c：核心運算實現（加、減、乘、導數、求值等）
• testpoly.c：測試用例與演示

核心數據結構

// poly.h 關鍵定義
typedef struct Node *PtrToNode;
typedef PtrToNode Polynomial;  // 多項式即鏈表頭指標

struct Node {
    int Coefficient;   // 係數
    int Exponent;      // 指數
    PtrToNode Next;    // 下一項
};

項按指數遞減序存儲，便於合併同類項與運算遍歷。

關鍵操作函數簽名

Polynomial PolyAdd(Polynomial P1, Polynomial P2);      // 加法
Polynomial PolySub(Polynomial P1, Polynomial P2);      // 減法
Polynomial PolyMult(Polynomial P1, Polynomial P2);     // 乘法
void PolyPrint(Polynomial P);                          // 打印
void PolyFree(Polynomial P);                           // 釋放
int PolyEval(Polynomial P, int x);                     // 求值

加法/減法核心邏輯（歸併思想）

Polynomial PolyAdd(Polynomial P1, Polynomial P2) {
    Polynomial Result = MakeEmpty(NULL);
    PtrToNode r = Result;
    P1 = P1->Next; P2 = P2->Next;  // 跳過頭節點

    while (P1 && P2) {
        if (P1->Exponent > P2->Exponent) {
            Attach(P1->Coefficient, P1->Exponent, &r);
            P1 = P1->Next;
        } else if (P1->Exponent < P2->Exponent) {
            Attach(P2->Coefficient, P2->Exponent, &r);
            P2 = P2->Next;
        } else {  // 指數相同，係數相加
            int sum = P1->Coefficient + P2->Coefficient;
            if (sum) Attach(sum, P1->Exponent, &r);
            P1 = P1->Next; P2 = P2->Next;
        }
    }
    // 處理剩餘項
    for (; P1; P1 = P1->Next) Attach(P1->Coefficient, P1->Exponent, &r);
    for (; P2; P2 = P2->Next) Attach(P2->Coefficient, P2->Exponent, &r);
    return Result;
}

乘法核心邏輯（分發+合併）

Polynomial PolyMult(Polynomial P1, Polynomial P2) {
    if (!P1->Next || !P2->Next) return MakeEmpty(NULL);  // 零多項式

    Polynomial Result = MakeEmpty(NULL);
    PtrToNode t1, t2, r;

    for (t1 = P1->Next; t1; t1 = t1->Next) {
        Polynomial Temp = MakeEmpty(NULL);
        r = Temp;
        for (t2 = P2->Next; t2; t2 = t2->Next) {
            Attach(t1->Coefficient * t2->Coefficient,
                   t1->Exponent + t2->Exponent, &r);
        }
        Result = PolyAdd(Result, Temp);  // 累加部分積
        PolyFree(Temp);
    }
    return Result;
}

測試驗證要點

• 零多項式處理（輸入/輸出）
• 同類項合併正確性（係數抵消為 0 時刪除節點）
• 大指數差距測試（稀疏多項式）
• 記憶體洩漏檢測（valgrind）

擴展建議

• 添加多項式導數運算
• 支援浮點係數（double）
• 實現稀疏矩陣轉換接口
• 提供 Python/C++ 綁定