一元多項式加法與乘法運算：C 語言鏈表實現詳解

編輯：關於C語言

一元多項式加法與乘法運算：C 語言鏈表實現詳解

多項式運算是數據結構課程中的經典案例。本文通過鏈表結構實現一元多項式的加法與乘法，詳細解析輸入輸出格式、節點設計、核心算法邏輯及完整代碼，幫助你掌握多項式運算的編程實現。

問題描述

輸入兩個一元多項式，每個多項式以非零項個數開頭，隨後按指數遞減順序給出系數和指數。要求輸出它們的乘積多項式和和多項式，同樣按指數遞減輸出非零項的系數和指數，零多項式輸出 `0 0`。

數據結構設計

使用帶頭結點的單鏈表存儲多項式，每個節點包含系數、指數和指向下一節點的指針：

typedef struct polyNode {
    int coef;           // 系數
    int exp;            // 指數
    struct polyNode *next;
} polyNode, *polyList;

核心算法邏輯

1. 多項式加法 `add()`

類似於合併兩個有序鏈表：雙指針遍歷兩個多項式，比較指數：

指數相等 → 系數相加，若結果非零則創建新節點。
指數較大者 → 直接複製該節點到結果鏈表。
最後將剩餘鏈表直接接在結果後。

2. 多項式乘法 `mul()`

採用「分發律」思想：遍歷第一個多項式的每一項，乘以第二個多項式的所有項，生成臨時多項式，再調用 add() 累加到結果中。

完整 C 語言實現

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

typedef struct polyNode {
    int coef;
    int exp;
    struct polyNode *next;
} polyNode, *polyList;

// 銷毀鏈表釋放內存
void DestroyList(polyList L) {
    polyNode *tmp;
    while (L) {
        tmp = L->next;
        free(L);
        L = tmp;
    }
}

// 輸出多項式
void printList(polyList L) {
    polyNode *x = L->next;
    if (x == NULL) {
        printf("0 0");
        return;
    }
    while (x != NULL) {
        if (x->next == NULL)
            printf("%d %d", x->coef, x->exp);
        else
            printf("%d %d ", x->coef, x->exp);
        x = x->next;
    }
}

// 創建多項式鏈表（按指數遞減輸入）
polyList creatList(int n) {
    polyNode *head = (polyNode *)malloc(sizeof(polyNode));
    polyNode *r = head;
    int coef, exp;
    while (n--) {
        scanf("%d%d", &coef, &exp);
        polyNode *p = (polyNode *)malloc(sizeof(polyNode));
        p->coef = coef;
        p->exp = exp;
        r->next = p;
        r = p;
    }
    r->next = NULL;
    return head;
}

// 多項式加法
polyList add(polyList a, polyList b) {
    polyNode *ha = a->next, *hb = b->next;
    polyNode *h = (polyNode *)malloc(sizeof(polyNode));
    polyNode *r = h;
    int temp;

    while (ha && hb) {
        polyNode *p = (polyNode *)malloc(sizeof(polyNode));
        if (ha->exp < hb->exp) {
            p->exp = hb->exp; p->coef = hb->coef; hb = hb->next;
        } else if (ha->exp > hb->exp) {
            p->exp = ha->exp; p->coef = ha->coef; ha = ha->next;
        } else {
            temp = ha->coef + hb->coef;
            if (temp != 0) {
                p->exp = ha->exp; p->coef = temp;
                r->next = p; r = p;
            }
            ha = ha->next; hb = hb->next;
            continue; // 系數為0不接入鏈表
        }
        r->next = p; r = p;
    }
    // 接上剩餘部分
    while (hb) {
        polyNode *p = (polyNode *)malloc(sizeof(polyNode));
        p->exp = hb->exp; p->coef = hb->coef;
        hb = hb->next; r->next = p; r = p;
    }
    while (ha) {
        polyNode *p = (polyNode *)malloc(sizeof(polyNode));
        p->exp = ha->exp; p->coef = ha->coef;
        ha = ha->next; r->next = p; r = p;
    }
    r->next = NULL;
    DestroyList(a); DestroyList(b); // 釋放原鏈表
    return h;
}

// 多項式乘法
polyList mul(polyList a, polyList b) {
    polyNode *ha = a->next, *hb = b->next;
    polyList c = (polyNode *)malloc(sizeof(polyNode));
    c->next = NULL;
    if (!ha || !hb) return c;

    while (ha) {
        polyList tempc = (polyNode *)malloc(sizeof(polyNode));
        polyNode *r = tempc;
        hb = b->next;
        while (hb) {
            polyNode *p = (polyNode *)malloc(sizeof(polyNode));
            p->exp = ha->exp + hb->exp;
            p->coef = ha->coef * hb->coef;
            hb = hb->next;
            r->next = p; r = p;
        }
        r->next = NULL;
        c = add(c, tempc); // 累加
        ha = ha->next;
    }
    return c;
}

int main() {
    int n1, n2;
    polyList a, b, L1, L2;
    scanf("%d", &n1); a = creatList(n1);
    scanf("%d", &n2); b = creatList(n2);
    L1 = mul(a, b);
    L2 = add(a, b);
    printList(L1); printf("\n");
    printList(L2);
    DestroyList(L1); DestroyList(L2);
    return 0;
}