C語言鏈表實現多項式加法與乘法：稀疏多項式、項合併、霍納求值完整實作

編輯：關於C語言

資料結構設計

typedef struct Node {
    float coef;      // 係數
    int expn;        // 指數
    struct Node *next;
} Node, *Polynomial;

采用**帶頭節點的單鏈表**，按**指數遞增**有序存儲，便於合併同類項。

核心操作實作

1. 多項式建立 (輸入係數指數對)

Polynomial CreatePoly() {
    Polynomial head = (Polynomial)malloc(sizeof(Node));
    head->next = NULL;
    Node *tail = head;

    int n;
    printf("項數: ");
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        float c; int e;
        scanf("%f %d", &c, &e);
        if(c == 0) continue;  // 跳過零係數
        
        Node *p = (Node*)malloc(sizeof(Node));
        p->coef = c; p->expn = e; p->next = NULL;
        tail->next = p;
        tail = p;
    }
    return head;
}

2. 多項式加法：歸併兩有序鏈表

Polynomial PolyAdd(Polynomial pa, Polynomial pb) {
    Polynomial pc = (Polynomial)malloc(sizeof(Node));
    pc->next = NULL;
    Node *tail = pc;

    Node *a = pa->next, *b = pb->next;
    while(a && b) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->next = NULL;
        
        if(a->expn < b->expn) {
            p->coef = a->coef; p->expn = a->expn;
            a = a->next;
        } else if(a->expn > b->expn) {
            p->coef = b->coef; p->expn = b->expn;
            b = b->next;
        } else {  // 指數相同，係數相加
            p->coef = a->coef + b->coef;
            p->expn = a->expn;
            a = a->next; b = b->next;
        }
        
        if(p->coef != 0) {  // 非零係數才接入
            tail->next = p;
            tail = p;
        } else {
            free(p);  // 零係數丟棄
        }
    }
    
    // 接上剩餘項
    tail->next = a ? a : b;
    return pc;
}

3. 多項式乘法：交叉相乘 + 合併同類項

Polynomial PolyMultiply(Polynomial pa, Polynomial pb) {
    Polynomial pc = (Polynomial)malloc(sizeof(Node));
    pc->next = NULL;

    for(Node *a = pa->next; a; a = a->next) {
        for(Node *b = pb->next; b; b = b->next) {
            float c = a->coef * b->coef;
            int e = a->expn + b->expn;
            if(c == 0) continue;
            
            // 插入或合併到結果表 (保持有序)
            Node *prev = pc, *curr = pc->next;
            while(curr && curr->expn < e) {
                prev = curr; curr = curr->next;
            }
            if(curr && curr->expn == e) {
                curr->coef += c;  // 合併同類項
                if(curr->coef == 0) {  // 係數歸零刪除節點
                    prev->next = curr->next;
                    free(curr);
                }
            } else {
                Node *p = (Node*)malloc(sizeof(Node));
                p->coef = c; p->expn = e;
                p->next = curr;
                prev->next = p;
            }
        }
    }
    return pc;
}

4. 霍納法則求值 (O(n))

float HornerEval(Polynomial p, float x) {
    // 先收集係數到陣列 (指數可能不連續)
    float coef[100] = {0};
    int max_exp = 0;
    for(Node *n = p->next; n; n = n->next) {
        if(n->expn >= 0 && n->expn < 100)
            coef[n->expn] = n->coef;
        if(n->expn > max_exp) max_exp = n->expn;
    }
    
    float result = coef[max_exp];
    for(int i = max_exp - 1; i >= 0; i--)
        result = result * x + coef[i];
    return result;
}

5. 輸出格式化

void PrintPoly(Polynomial p) {
    Node *n = p->next;
    if(!n) { printf("0\n"); return; }
    
    while(n) {
        printf("%.1fx^%d", n->coef, n->expn);
        if(n->next) printf(" + ");
        n = n->next;
    }
    printf("\n");
}

完整主程式

int main() {
    Polynomial p1 = CreatePoly();
    Polynomial p2 = CreatePoly();
    
    printf("P1 = "); PrintPoly(p1);
    printf("P2 = "); PrintPoly(p2);
    
    Polynomial sum = PolyAdd(p1, p2);
    printf("P1+P2 = "); PrintPoly(sum);
    
    Polynomial prod = PolyMultiply(p1, p2);
    printf("P1*P2 = "); PrintPoly(prod);
    
    float x = 2.0;
    printf("P1(%.1f) = %.4f\n", x, HornerEval(p1, x));
    printf("P2(%.1f) = %.4f\n", x, HornerEval(p2, x));
    
    // 釋放所有鏈表 (略)
    return 0;
}

測試案例

輸入 P1: 3項
  2.0 1   (2x)
  3.0 0   (3)
  1.0 2   (x²)
輸入 P2: 2項
  1.0 1   (x)
  1.0 0   (1)

P1 = 3.0x^0 + 2.0x^1 + 1.0x^2
P2 = 1.0x^0 + 1.0x^1
P1+P2 = 4.0x^0 + 3.0x^1 + 1.0x^2
P1*P2 = 3.0x^0 + 5.0x^1 + 3.0x^2 + 1.0x^3
P1(2.0) = 11.0000  (4 + 4 + 1*4 = 12? Wait: 3 + 2*2 + 1*4 = 11 ✓)
P2(2.0) = 3.0000   (1 + 2 = 3 ✓)

關鍵設計決策對比

設計點	方案 A	方案 B (本文)	優勢
指數順序	遞減	遞增	符合直覺，易合併
零係數處理	保留	刪除/不插入	節省空間，輸出乾淨
乘法合併	先生成再合併	邊乘邊合併	一次遍歷，O(mn) 不變但常數小
求值演算法	直接冪次求和	霍納法則	乘法次數最少，數值穩定