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

C 語言實作多項式加減運算：鏈表儲存與單遍歷合併演算法

編輯：C 語言入門

多項式運算是經典資料結構習題。本文採用單向鏈表儲存非零項 (係數、指數)，設計單次遍歷合併演算法，時間複雜度 O(n+m)，空間複雜度 O(1) 額外空間 (就地修改)。

資料結構定義

typedef struct Node {
    float coef;        // 係數
    int exp;           // 指數
    struct Node *next;
} Node;

typedef struct { Node *head; } Poly;  // 帶哨兵節點的鏈表

哨兵節點 (head) 不存資料，簡化插入/刪除邏輯
節點按 指數遞減序 排列，便於合併同次項

核心演算法：有序鏈表合併

以 Poly A += Poly B 為例 (減法同理，係數取負再加)：

// 複製節點 (避免直接掛接 B 的節點導致雙重釋放)
Node* clone(Node *n) {
    Node *p = malloc(sizeof(Node));
    *p = *n; p->next = NULL; return p;
}

// 將項插入有序鏈表，合併同次項，係數為 0 則刪除
Node* insert_term(Node *prev, Node *term) {
    Node *cur = prev->next;
    while (cur) {
        if (term->exp == cur->exp) {           // 同次項：合併係數
            cur->coef += term->coef;
            if (fabs(cur->coef) < 1e-6) {      // 係數近 0 刪除節點
                prev->next = cur->next;
                free(cur);
            }
            return prev;                       // 保持 prev 不動，下一項仍從這裡比較
        }
        if (term->exp > cur->exp) {            // term 指數較大，插在 cur 前
            Node *n = clone(term);
            n->next = cur;
            prev->next = n;
            return n;                          // 後移 prev 至新節點
        }
        prev = cur;
        cur = cur->next;
    }
    // 到達尾部，term 指數最小，直接插在尾端
    prev->next = clone(term);
    return prev->next;
}

// 多項式加法：A += B
void poly_add(Poly *A, Poly *B) {
    Node *pa = A->head;
    Node *pb = B->head->next;  // 跳過哨兵
    while (pb) {
        pa = insert_term(pa, pb);
        pb = pb->next;
    }
}

// 多項式減法：A -= B
void poly_sub(Poly *A, Poly *B) {
    Node *pa = A->head;
    Node *pb = B->head->next;
    while (pb) {
        pb->coef = -pb->coef;      // 係數取負
        pa = insert_term(pa, pb);
        pb->coef = -pb->coef;      // 還原 B (若 B 後續仍需使用)
        pb = pb->next;
    }
}

完整可執行範例

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// ... 上述結構與函式定義 ...

// 由係數/指數陣列建立多項式 (自動合併同次項、過濾零係數)
Poly* create_poly(float *coef, int *exp, int n) {
    Poly *p = malloc(sizeof(Poly));
    p->head = malloc(sizeof(Node));
    p->head->next = NULL;
    for (int i = 0; i < n; i++) {
        if (fabs(coef[i]) < 1e-6) continue;
        Node term = {coef[i], exp[i], NULL};
        insert_term(p->head, &term);
    }
    return p;
}

void print_poly(Poly *p) {
    Node *cur = p->head->next;
    if (!cur) { puts("0"); return; }
    while (cur) {
        printf("%.2fx^%d", cur->coef, cur->exp);
        cur = cur->next;
        if (cur) printf(" + ");
    }
    putchar('\n');
}

void free_poly(Poly *p) {
    Node *cur = p->head;
    while (cur) { Node *t = cur; cur = cur->next; free(t); }
    free(p);
}

int main(void) {
    float c1[] = {2, 3, 5, -3, 9};
    int   e1[] = {2, 5, 4, 5, 6};   // 9x^6 + 3x^5 + 5x^4 + 2x^2 - 3x^5 → 合併後 9x^6 + 0x^5 + 5x^4 + 2x^2
    float c2[] = {5, 4, -5, -6, 1, 5};
    int   e2[] = {3, 8, 4, 6, 2, 7};

    Poly *A = create_poly(c1, e1, 5);
    Poly *B = create_poly(c2, e2, 6);

    puts("A(x) = "); print_poly(A);
    puts("B(x) = "); print_poly(B);

    poly_sub(A, B);  // A = A - B
    puts("A - B = "); print_poly(A);

    free_poly(A); free_poly(B);
    return 0;
}

執行結果

A(x) = 9.00x^6 + 5.00x^4 + 2.00x^2
B(x) = 5.00x^8 + 5.00x^7 + 4.00x^6 - 5.00x^4 - 6.00x^3 + 1.00x^2
A - B = -5.00x^8 - 5.00x^7 + 5.00x^6 + 10.00x^4 + 6.00x^3 + 1.00x^2

演算法分析與優化要點

指標	數值	說明
時間複雜度	O(n + m)	雙指針單遍歷，無回溯
空間複雜度	O(1) 額外	就地修改 A，僅分配新節點給 B 中不在 A 的項
穩定性	佳	浮點係數以 `fabs(coef) < 1e-6` 判零，避免精度問題