C語言實現稀疏多項式加法與乘法：鏈表存儲、合併同類項與霍納法則求值

稀疏多項式鏈表表示

僅存儲非零項，節點包含係數、指數、下一節點指針，按指數遞增/遞減有序存放。

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

核心操作實現

1. 初始化與輸入

void init_poly(Polynomial *p) {
    *p = calloc(1, sizeof(Node)); // 頭節點
    (*p)->next = NULL;
    int n; printf("項數: "); scanf("%d", &n);
    Node *tail = *p;
    for (int i = 0; i < n; i++) {
        Node *cur = calloc(1, sizeof(Node));
        scanf("%f %d", &cur->coef, &cur->expn);
        tail->next = cur; tail = cur;
    }
    sort_poly(*p); // 確保有序
}

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

Polynomial poly_add(Polynomial a, Polynomial b) {
    Polynomial res = calloc(1, sizeof(Node));
    Node *tail = res;
    Node *pa = a->next, *pb = b->next;

    while (pa && pb) {
        Node *cur = calloc(1, sizeof(Node));
        if (pa->expn < pb->expn) {
            cur->coef = pa->coef; cur->expn = pa->expn; pa = pa->next;
        } else if (pa->expn > pb->expn) {
            cur->coef = pb->coef; cur->expn = pb->expn; pb = pb->next;
        } else { // 指數相同，係數相加
            cur->coef = pa->coef + pb->coef;
            cur->expn = pa->expn;
            pa = pa->next; pb = pb->next;
        }
        if (cur->coef != 0) { // 過濾零係數
            tail->next = cur; tail = cur;
        } else free(cur);
    }
    // 鏈接剩餘
    tail->next = pa ? pa : pb;
    return res;
}

3. 多項式乘法：雙重循環生成項 → 合併同類項

Polynomial poly_mul(Polynomial a, Polynomial b) {
    Polynomial res = calloc(1, sizeof(Node));
    Node *pa = a->next;
    while (pa) {
        Node *pb = b->next;
        while (pb) {
            Node *cur = calloc(1, sizeof(Node));
            cur->coef = pa->coef * pb->coef;
            cur->expn = pa->expn + pb->expn;
            // 尾插（暫不合併）
            Node *tail = res;
            while (tail->next) tail = tail->next;
            tail->next = cur;
            pb = pb->next;
        }
        pa = pa->next;
    }
    merge_like_terms(res); // 關鍵：合併同指數項
    return res;
}

void merge_like_terms(Polynomial p) {
    Node *pre = p->next, *cur = pre ? pre->next : NULL;
    while (cur) {
        if (pre->expn == cur->expn) {
            pre->coef += cur->coef;
            pre->next = cur->next;
            free(cur);
            cur = pre->next;
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
    // 再次過濾零係數（略）
}

4. 霍納法則求值：O(n) 時間、數值穩定

float horner_eval(Polynomial p, float x) {
    // 先轉為稠密係數數組（指數連續）
    int max_exp = get_max_expn(p);
    float *coef = calloc(max_exp + 1, sizeof(float));
    for (Node *n = p->next; n; n = n->next)
        coef[n->expn] = n->coef;

    float result = coef[max_exp];
    for (int i = max_exp - 1; i >= 0; i--)
        result = result * x + coef[i];
    free(coef);
    return result;
}

5. 打印與釋放

void print_poly(Polynomial p) {
    for (Node *n = p->next; n; n = n->next) {
        printf("%.1fx^%d", n->coef, n->expn);
        if (n->next) printf(" + ");
    }
    puts(";");
}

void free_poly(Polynomial p) {
    Node *cur = p;
    while (cur) { Node *nxt = cur->next; free(cur); cur = nxt; }
}

完整主程序

int main(void) {
    Polynomial p1, p2, sum, prod;
    init_poly(&p1); init_poly(&p2);
    sort_poly(p1); sort_poly(p2);

    printf("P1 = "); print_poly(p1);
    printf("P2 = "); print_poly(p2);

    sum = poly_add(p1, p2);
    prod = poly_mul(p1, p2);

    printf("Sum = "); print_poly(sum);
    printf("Prod = "); print_poly(prod);

    printf("P1(2) = %.2f\n", horner_eval(p1, 2.0));
    printf("P2(2) = %.2f\n", horner_eval(p2, 2.0));

    free_poly(p1); free_poly(p2); free_poly(sum); free_poly(prod);
    return 0;
}

關鍵算法複雜度

優化方向

• 乘法合併同類項用雜湊表 unordered_map<int, float> 降至 O(m×n) 期望時間。
• 引入指數跳表或平衡樹支援動態插入/刪除項。
• 係數類型模板化支援 double/complex/模數域。