數據結構實戰：C語言鏈表實現多項式加法運算

鏈式存儲實現多項式加法：項節點設計、讀取、合併同類項、銷毀

使用單鏈表表示稀疏多項式，按指數遞增有序存儲，實現多項式輸入、顯示、相加、內存管理完整流程。

數據結構設計

typedef struct term *Link;
struct term {
    int coef;      // 係數
    int exp;       // 指數
    Link next;
};

typedef struct {
    Link head;  // 頭節點(哨兵)
    Link tail;  // 尾指針
} *Poly;

核心操作實現

初始化與節點創建

Poly poly_init() {
    Poly p = malloc(sizeof(*p));
    p->head = p->tail = malloc(sizeof(struct term));
    p->head->next = NULL;
    return p;
}

Link make_term(int c, int e) {
    Link t = malloc(sizeof(*t));
    t->coef = c; t->exp = e; t->next = NULL;
    return t;
}

尾插法讀取多項式

void read_terms(Poly p) {
    int n, c, e;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d_%d", &c, &e);  // 格式: 係數_指數
        p->tail = p->tail->next = make_term(c, e);
    }
}

多項式加法：歸併同類項

Poly poly_add(Poly p1, Poly p2) {
    Poly p = poly_init();
    Link t1 = p1->head->next, t2 = p2->head->next;
    
    while (t1 && t2) {
        if (t1->exp < t2->exp) {
            p->tail = p->tail->next = make_term(t1->coef, t1->exp);
            t1 = t1->next;
        } else if (t1->exp > t2->exp) {
            p->tail = p->tail->next = make_term(t2->coef, t2->exp);
            t2 = t2->next;
        } else {  // 指數相同，係數相加
            int sum = t1->coef + t2->coef;
            if (sum != 0)  // 係數為0不存儲
                p->tail = p->tail->next = make_term(sum, t1->exp);
            t1 = t1->next; t2 = t2->next;
        }
    }
    // 餘項接入
    for (; t1; t1 = t1->next)
        p->tail = p->tail->next = make_term(t1->coef, t1->exp);
    for (; t2; t2 = t2->next)
        p->tail = p->tail->next = make_term(t2->coef, t2->exp);
    return p;
}

顯示與銷毀

void show(Poly p) {
    Link t = p->head->next;
    if (!t) return;
    for (; t->next; t = t->next) {
        int sign = (t->next->coef > 0) ? '+' : '-';
        printf("%dX^%d %c ", abs(t->coef), t->exp, sign);
    }
    printf("%dX^%d\n", abs(t->coef), t->exp);
}

void destroy(Poly p) {
    Link t = p->head, nxt;
    while (t) { nxt = t->next; free(t); t = nxt; }
    free(p);
}

測試用例

輸入:
3          // p1 項數
2_3 5_1 1_0  // 2x^3 + 5x^1 + 1
2          // p2 項數
3_2 -5_1   // 3x^2 - 5x^1

輸出:
2X^3 + 3X^2 + 1X^0

算法複雜度

• 時間：O(m+n)，單次掃描歸併
• 空間：O(m+n)，結果鏈表

工程化擴展

• 支援減法/乘法/求導/積分
• 稠密多項式改用數組存儲
• 係數泛型化支援浮點/複數
• 解析器支援標準數學表達式輸入

鏈表實現多項式是數據結構教材經典案例，完美展示動態存儲、有序歸併、內存管理核心技能。