一元多項式運算：鏈表實現加減乘除完整 C 語言教學案例

一元多項式運算：鏈表實現加減乘除完整 C 語言教學案例

一元多項式 P(x) = a₀x^e₀ + a₁x^e₁ + ... 的加減乘運算是數據結構教材經典案例。本文採用帶頭結點的單鏈表，按指數遞增順序存儲，實現多項式輸入、輸出、複製、加法、減法、乘法、銷毀全流程，附帶交互式菜單演示。

數據結構定義

typedef struct Polyn {
    int coef;      // 系數
    int exp;       // 指數
    struct Polyn* next;
} Polyn, *Polynlist;

核心算法：多項式加法 AddPolyn

雙指針 qa、qb 同步遍歷兩有序鏈表，prior 維護結果鏈表尾部：

• qa->exp < qb->exp：qa 節點直接接入結果，qa 後移
• qa->exp > qb->exp：摘取 qb 節點插入 qa 前，qb 後移
• 指數相等：系數相加，非零則更新 qa 系數並釋放 qb；零則雙雙釋放，prior 銜接 qa->next

void AddPolyn(Polyn* p, Polyn* p1) { // p = p + p1, 銷毀 p1
    Polyn *qa = p->next, *qb = p1->next, *prior = p, *r;
    while (qa && qb) {
        if (qa->exp < qb->exp) { prior = qa; qa = qa->next; }
        else if (qa->exp > qb->exp) {
            r = qb; qb = qb->next;
            r->next = qa; prior->next = r; prior = r;
        } else {
            if (qa->coef + qb->coef != 0) {
                qa->coef += qb->coef; r = qb; qb = qb->next; free(r);
            } else {
                r = qa; qa = qa->next; prior->next = qa; free(r);
                r = qb; qb = qb->next; free(r);
            }
        }
    }
    if (qb) prior->next = qb; // p1 剩餘項接入
    free(p1); // 釋放 p1 頭結點
}

減法與乘法複用加法邏輯