C語言多項式運算：鏈結串列實作任意順序輸入自動降冪排序、加法與乘法

問題背景

原程式要求使用者按降冪序輸入多項式項（如 3x² + 2x + 1 須依序輸入 3,2 2,1 1,0），否則運算錯誤。需修改為任意順序輸入，程式自動排序後再運算。

資料結構定義

typedef struct PolyTerm {
    int coef;              // 係數
    int exp;               // 指數
    struct PolyTerm *next; // 下一項指標
} Term;

核心改進：插入時自動維持降冪序

有序插入函式

// 將新項插入多項式鏈結串列，保持指數降序
// 回傳新的頭節點指標（可能因插在頭部而改變）
Term* insert_term(Term *head, Term *new_term) {
    if (!new_term) return head;

    // 情況 1：空串列 或 新項指數 > 現有頭部指數 → 插在頭部
    if (!head || new_term->exp > head->exp) {
        new_term->next = head;
        return new_term;
    }

    // 情況 2：遍歷尋找插入位置
    Term *curr = head;
    while (curr->next && curr->next->exp > new_term->exp) {
        curr = curr->next;
    }

    // 檢查重複指數（同指數項應合併係數，這裡選擇拒絕重複輸入）
    if (curr->next && curr->next->exp == new_term->exp) {
        printf("錯誤：指數 %d 已存在，請合併係數後輸入。\n", new_term->exp);
        free(new_term);
        return head;
    }

    // 插入：新項接在 curr 之後
    new_term->next = curr->next;
    curr->next = new_term;
    return head;
}

修改後的建立多項式函式

Term* create_poly() {
    Term *head = NULL;
    int coef, exp;
    char cont = 'y';

    printf("輸入多項式項 (係數,指數)，如: 3 2  表示 3x^2\n");
    while (cont == 'y' || cont == 'Y') {
        printf("係數 指數: ");
        if (scanf("%d %d", &coef, &exp) != 2) {
            printf("輸入格式錯誤\n");
            while (getchar() != '\n'); // 清緩衝區
            continue;
        }
        if (coef == 0) {
            printf("係數為 0 略過\n");
            continue;
        }

        Term *new_term = (Term*)malloc(sizeof(Term));
        new_term->coef = coef;
        new_term->exp = exp;
        new_term->next = NULL;

        head = insert_term(head, new_term);

        printf("繼續輸入? (y/n): ");
        scanf(" %c", &cont);  // 空格吃掉殘留換行
    }
    return head;
}

多項式加法（合併同指數項）

Term* poly_add(Term *a, Term *b) {
    Term *result = NULL;
    Term *tail = NULL;

    while (a && b) {
        Term *new_term = (Term*)malloc(sizeof(Term));
        new_term->next = NULL;

        if (a->exp == b->exp) {
            new_term->exp = a->exp;
            new_term->coef = a->coef + b->coef;
            a = a->next;
            b = b->next;
            if (new_term->coef == 0) {  // 係數抵銷為 0，不加入結果
                free(new_term);
                continue;
            }
        } else if (a->exp > b->exp) {
            new_term->exp = a->exp;
            new_term->coef = a->coef;
            a = a->next;
        } else { // b->exp > a->exp
            new_term->exp = b->exp;
            new_term->coef = b->coef;
            b = b->next;
        }

        // 尾插法建立結果串列
        if (!result) result = tail = new_term;
        else { tail->next = new_term; tail = new_term; }
    }

    // 剩餘項直接接上（因已排序，直接連接即可）
    Term *remaining = a ? a : b;
    while (remaining) {
        Term *new_term = (Term*)malloc(sizeof(Term));
        new_term->coef = remaining->coef;
        new_term->exp = remaining->exp;
        new_term->next = NULL;
        if (!result) result = tail = new_term;
        else { tail->next = new_term; tail = new_term; }
        remaining = remaining->next;
    }

    return result;
}

多項式乘法

每一項與另一多項式所有項相乘，產生中間結果再合併同指數項。

Term* poly_multiply(Term *a, Term *b) {
    Term *result = NULL;

    for (Term *pa = a; pa; pa = pa->next) {
        for (Term *pb = b; pb; pb = pb->next) {
            int new_exp = pa->exp + pb->exp;
            int new_coef = pa->coef * pb->coef;

            // 將乘積項插入/合併到結果中
            result = insert_or_merge(result, new_coef, new_exp);
        }
    }
    return result;
}

// 輔助：插入或合併同指數項
Term* insert_or_merge(Term *head, int coef, int exp) {
    if (coef == 0) return head;

    // 找到指數位置
    Term *pre = NULL;
    Term *curr = head;
    while (curr && curr->exp > exp) {
        pre = curr;
        curr = curr->next;
    }

    // 找到同指數 → 合併係數
    if (curr && curr->exp == exp) {
        curr->coef += coef;
        if (curr->coef == 0) {  // 係數歸零 → 刪除節點
            if (pre) pre->next = curr->next;
            else head = curr->next;
            free(curr);
        }
        return head;
    }

    // 新指數 → 插入新節點
    Term *new_term = (Term*)malloc(sizeof(Term));
    new_term->coef = coef;
    new_term->exp = exp;
    new_term->next = curr;

    if (pre) pre->next = new_term;
    else head = new_term;

    return head;
}

輸出與記憶體釋放

void print_poly(Term *head) {
    if (!head) { printf("0\n"); return; }
    Term *curr = head;
    while (curr) {
        printf("%dx^%d", curr->coef, curr->exp);
        if (curr->next) printf(" + ");
        curr = curr->next;
    }
    printf("\n");
}

void free_poly(Term *head) {
    while (head) {
        Term *tmp = head;
        head = head->next;
        free(tmp);
    }
}

主程式整合

int main() {
    printf("=== 多項式運算系統 ===\n");
    printf("輸入第一個多項式：\n");
    Term *poly1 = create_poly();

    printf("\n輸入第二個多項式：\n");
    Term *poly2 = create_poly();

    printf("\n多項式 1: "); print_poly(poly1);
    printf("多項式 2: "); print_poly(poly2);

    Term *sum = poly_add(poly1, poly2);
    printf("加法結果: "); print_poly(sum);

    Term *product = poly_multiply(poly1, poly2);
    printf("乘法結果: "); print_poly(product);

    // 釋放所有記憶體
    free_poly(poly1);
    free_poly(poly2);
    free_poly(sum);
    free_poly(product);

    return 0;
}

執行範例

=== 多項式運算系統 ===
輸入第一個多項式：
輸入多項式項 (係數,指數)，如: 3 2  表示 3x^2
係數 指數: 2 3
繼續輸入? (y/n): y
係數 指數: 5 1
繼續輸入? (y/n): y
係數 指數: 1 0
繼續輸入? (y/n): n

輸入第二個多項式：
係數 指數: 3 2
繼續輸入? (y/n): y
係數 指數: -5 1
繼續輸入? (y/n): n

多項式 1: 2x^3 + 5x^1 + 1x^0
多項式 2: 3x^2 + -5x^1
加法結果: 2x^3 + 3x^2 + 0x^1 + 1x^0
乘法結果: 6x^5 + -10x^4 + 15x^3 + -25x^2 + 3x^1 + -5x^0

關鍵技術點總結

進階優化方向

• 乘法改用「指數陣列累加係數」再建串列，避免重複遍歷插入
• 支援浮點數係數（double coef）
• 加入多項式求導、積分、評值功能
• 使用雙向鏈結串列簡化刪除操作