您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言入門

C 語言單鏈表實現多項式運算：加減乘除完整代碼詳解

編輯：C 語言入門

多項式運算是鏈表結構的經典應用場景。本文基於嚴蔚敏《數據結構》接口規範，採用帶頭節點的有序單鏈表存儲多項式（按指數遞增），實現加法、減法、乘法三大核心運算，代碼包含創建、銷毀、打印、複製、有序插入、定位查找等完整工具函數，可直接編譯運行。

數據結構設計

項節點定義

typedef struct {
    int coef;   // 系數
    int expn;   // 指數
} Term;

鏈表節點

typedef struct LNode {
    Term data;
    struct LNode *next;
} LNode, *LinkList;

多項式類型

typedef LinkList Polynomial;  // 帶頭節點的有序單鏈表，按 expn 遞增

核心輔助函數

項比較器

// 返回值：-1 (a<b), 0 (a==b), 1 (a>b) —— 僅比較指數
int CompareTerm(Term a, Term b) {
    if (a.expn < b.expn) return -1;
    if (a.expn > b.expn) return 1;
    return 0;
}

有序定位查找


typedef struct {
    Polynomial pos;  // 目標位置的前驅節點
    int type;        // -1: 插在 pos 後(比所有大), 0: 找到相同指數, 1: 插在 pos 後(比 pos->next 小)
} LocateResult;

LocateResult Locate(Polynomial head, Term e) {
    LocateResult res = {head, -1};
    Polynomial p = head;
    while (p->next) {
        int cmp = CompareTerm(p->next->data, e);
        if (cmp == 0) { res.pos = p; res.type = 0; return res; }      // 找到同指數
        if (cmp > 0)  { res.pos = p; res.type = 1; return res; }      // 找到第一個更大的
        p = p->next;
    }
    res.pos = p; res.type = -1;  // 比所有現有項指數都大，插在尾部
    return res;
}

有序插入/合併同指數項


void OrderedInsert(Polynomial head, Term e) {
    LocateResult lr = Locate(head, e);
    if (lr.type == 0) {  // 同指數項已存在，系數相加
        lr.pos->next->data.coef += e.coef;
        if (lr.pos->next->data.coef == 0) {  // 系數歸零，刪除該節點
            Polynomial tmp = lr.pos->next;
            lr.pos->next = tmp->next;
            free(tmp);
        }
    } else {  // 新指數，創建節點插入
        Polynomial node = (Polynomial)malloc(sizeof(LNode));
        node->data = e;
        node->next = lr.pos->next;
        lr.pos->next = node;
    }
}

多項式創建（交互式輸入）


void CreatePolynomial(Polynomial head) {
    head->next = NULL;
    Term t;
    printf("請輸入系數 指數 (系數為 0 結束)：");
    while (scanf("%d %d", &t.coef, &t.expn) == 2 && t.coef != 0) {
        OrderedInsert(head, t);
        printf("下一項：");
    }
}

深度複製鏈表


Polynomial ClonePolynomial(Polynomial head) {
    Polynomial newHead = (Polynomial)malloc(sizeof(LNode));
    newHead->next = NULL;
    Polynomial src = head->next, dst = newHead;
    while (src) {
        Polynomial node = (Polynomial)malloc(sizeof(LNode));
        node->data = src->data;
        node->next = NULL;
        dst->next = node;
        dst = node;
        src = src->next;
    }
    return newHead;
}

打印輸出


void PrintPolynomial(Polynomial head) {
    Polynomial p = head->next;
    if (!p) { puts("0"); return; }
    while (p) {
        printf("%dx^%d", p->data.coef, p->data.expn);
        if (p->next && p->next->data.coef > 0) printf(" + ");
        else if (p->next) printf(" ");
        p = p->next;
    }
    putchar('\n');
}

三大核心運算實現

1. 多項式加法：`Pa = Pa + Pb`（銷毀 Pb）


Polynomial AddPolynomial(Polynomial pa, Polynomial pb) {
    Polynomial pc = pa;           // 結果存入 pa，pc 指向結果鏈表最後一個節點
    Polynomial qa = pa->next, qb = pb->next;
    Polynomial hb = pb;           // 保存 pb 頭節點以便釋放

    while (qa && qb) {
        int cmp = CompareTerm(qa->data, qb->data);
        if (cmp == 0) {  // 指數相同，系數相加
            qa->data.coef += qb->data.coef;
            if (qa->data.coef == 0) {  // 系數為零，刪除 qa 節點
                pc->next = qa->next;
                free(qa);
                qa = pc->next;
            } else {
                pc = qa;
                qa = qa->next;
            }
            // 釋放 qb 節點
            Polynomial tmp = qb;
            qb = qb->next;
            free(tmp);
        } else if (cmp < 0) {  // qa 指數較小，接入結果鏈
            pc->next = qa;
            pc = qa;
            qa = qa->next;
        } else {  // qb 指數較小，摘下 qb 接入結果鏈
            pc->next = qb;
            pc = qb;
            qb = qb->next;
        }
    }
    // 收尾剩餘部分
    if (qa) pc->next = qa;
    else    pc->next = qb;
    free(hb);  // 釋放 pb 頭節點
    return pa;
}

2. 多項式減法：`Pa = Pa - Pb`


Polynomial SubtractPolynomial(Polynomial pa, Polynomial pb) {
    // 將 pb 所有系數取反，轉化為加法
    for (Polynomial p = pb->next; p; p = p->next)
        p->data.coef = -p->data.coef;
    return AddPolynomial(pa, pb);  // 復用加法邏輯
}

3. 多項式乘法：`Pa = Pa * Pb`

數學原理：(Σ aᵢxᵉⁱ) * (Σ bⱼxᵉʲ) = Σᵢ Σⱼ (aᵢbⱼ)x^(eⁱ+ᵉʲ)。對 Pb 每一項，乘以 Pa 的完整副本得到中間多項式，再累加到結果。


Polynomial MultiplyPolynomial(Polynomial pa, Polynomial pb) {
    Polynomial result = (Polynomial)malloc(sizeof(LNode));
    result->next = NULL;  // 空多項式作為累加器

    Polynomial qb = pb->next;
    while (qb) {
        // 複製 pa 並乘以 qb 項
        Polynomial temp = ClonePolynomial(pa);
        for (Polynomial q = temp->next; q; q = q->next) {
            q->data.coef *= qb->data.coef;
            q->data.expn += qb->data.expn;
        }
        // 累加到結果
        result = AddPolynomial(result, temp);  // AddPolynomial 會銷毀 temp
        qb = qb->next;
    }
    // 清理原輸入鏈表
    Polynomial p;
    while ((p = pa)) { pa = pa->next; free(p); }
    while ((p = pb)) { pb = pb->next; free(p); }
    return result;
}

主程序測試


int main() {
    Polynomial pa = (Polynomial)malloc(sizeof(LNode));
    Polynomial pb = (Polynomial)malloc(sizeof(LNode));

    printf("=== 輸入多項式 A ===\n");
    CreatePolynomial(pa);
    printf("A = "); PrintPolynomial(pa);

    printf("\n=== 輸入多項式 B ===\n");
    CreatePolynomial(pb);
    printf("B = "); PrintPolynomial(pb);

    printf("\n=== A + B ===\n");
    Polynomial sum = AddPolynomial(ClonePolynomial(pa), ClonePolynomial(pb));
    PrintPolynomial(sum);
    // 清理 sum...
    
    printf("\n=== A - B ===\n");
    Polynomial diff = SubtractPolynomial(ClonePolynomial(pa), ClonePolynomial(pb));
    PrintPolynomial(diff);

    printf("\n=== A * B ===\n");
    Polynomial prod = MultiplyPolynomial(ClonePolynomial(pa), ClonePolynomial(pb));
    PrintPolynomial(prod);

    return 0;
}

關鍵工程細節總結

環節	易錯點	最佳實踐
有序插入	忘記處理系數歸零刪除節點	插入即合併，系數為 0 立即 unlink + free
加法合併	雙指針移動邏輯混亂，內存洩漏	pc 永遠指向結果鏈表尾部，qa/qb 為工作指針，釋放節點即時進行
減法復用	直接修改原 pb 影響調用者	調用前 Clone，或在減法內部 Clone 後再取反
乘法中間量	重複遍歷 pa 產生 O(n²m) 而非 O(nm)	對 pb 每項 Clone 一次 pa 並批量修改指數系數，再累加
內存管理	銷毀時頭節點未 free	統一約定：頭節點也是 malloc 產生，銷毀時逐個 free 直到 NULL