您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言實現一元多項式運算庫：鏈表儲存與四則運算完整源碼

編輯：關於C

一元多項式是代數運算基礎。本文提供基於單鏈表的完整實現，支援建立、銷毀、列印、加減乘、逆序等操作，採用帶頭結點設計，係數為 double、指數為 int，適合教學與工程參考。

資料結構定義

#define DEV 0.0000002   // 係數近零判定閾值
#define TRUE 1
#define OK 1
#define ERROR 0
#define CHECK(t) do{if(!(t)){return 0;}}while(0)

typedef int Status;
typedef struct term {
    double coef;           // 係數
    int expn;              // 指數
    struct term *next;     // 下一項
} PolyNode, *Poly;

核心操作函數

節點管理

// 建立節點
Status makeNode(double coef, int expn, Poly *p) {
    (*p) = (Poly)malloc(sizeof(struct term));
    CHECK(*p);
    (*p)->coef = coef;
    (*p)->expn = expn;
    (*p)->next = 0;
    return OK;
}

// 銷毀多項式
Status destroyPoly(Poly *head) {
    Poly p = *head;
    while (p) {
        *head = p->next;
        free(p);
        p = *head;
    }
    *head = 0;
    return OK;
}

插入節點（按指數遞增有序）

Status AddNodePoly(Poly *head, double coef, int expn) {
    CHECK(*head);
    if (fabs(coef) < DEV) return OK;  // 忽略零係數
    
    Poly q = (*head)->next;
    Poly p = (*head);
    Poly s;
    
    // 尋找插入位置
    while (q && expn < q->expn) {
        p = q;
        q = q->next;
    }
    
    if (q == 0 || expn > q->expn) {  // 新指數
        CHECK(makeNode(coef, expn, &s));
        p->next = s;
        s->next = q;
    } else {  // 同指數合併係數
        q->coef += coef;
        if (fabs(q->coef) < DEV) {   // 係數抵消為零
            p->next = q->next;
            free(q);
        }
    }
    return OK;
}

建立多項式（互動輸入）

Status createPoly(Poly *head) {
    if (*head) destroyPoly(head);
    CHECK(makeNode(0, 0, head));  // 頭結點
    
    int expn; double coef;
    do {
        scanf("%lf%d", &coef, &expn);
        if (fabs(coef) < DEV && expn == 0) break;  // 0 0 結束
        if (fabs(coef) < DEV) continue;
        if (!AddNodePoly(head, coef, expn)) return ERROR;
    } while (TRUE);
    return OK;
}

列印多項式

Status print(Poly head) {
    CHECK(head);
    Poly p = head->next;
    while (p) {
        printf("%1.1f", p->coef);
        if (p->expn) printf("*x^%d", p->expn);
        if (p->next && p->next->coef > 0) printf("+");
        p = p->next;
    }
    printf("\n");
    return OK;
}

多項式加法

Status AddPoly(Poly *a, Poly *b) {
    CHECK(*a && *b && *a != *b);
    Poly p = *a, p1 = (*a)->next, p2 = (*b)->next, t;
    
    while (p1 && p2) {
        if (p1->expn == p2->expn) {
            p1->coef += p2->coef;
            if (fabs(p1->coef) < DEV) {  // 係數為零刪除節點
                t = p1->next;
                free(p1);
                p1 = t;
            } else {
                p->next = p1;
                p1 = p1->next;
                p = p->next;
            }
            t = p2->next;
            free(p2);
            p2 = t;
        } else {
            t = (p1->expn > p2->expn) ? p1 : p2;
            p->next = t;
            p = t;
            t = t->next;
            // 注意：原代碼此處有語法問題，建議改為：
            if (p1->expn > p2->expn) p1 = t; else p2 = t;
        }
    }
    p->next = 0;
    if (p2) p->next = p2;
    free(b);
    b = 0;
    return OK;
}

減法、乘法、逆序

// 減法 = 加上負多項式
Status SubPoly(Poly *a, Poly *b) {
    CHECK(*a && *b && *a != *b);
    Poly p = (*b)->next;
    while(p) { p->coef = -p->coef; p = p->next; }
    return AddPoly(a, b);
}

// 乖法：雙重循環逐項相乘再合併
Status multiPoly(Poly *a, Poly *b) {
    CHECK(*a && *b);
    Poly head, p1, p2;
    CHECK(makeNode(0, 0, &head));
    p1 = (*a)->next;
    while(p1) {
        p2 = (*b)->next;
        while(p2) {
            AddNodePoly(&head, p1->coef*p2->coef, p1->expn+p2->expn);
            print(head);  // 調試用，正式版應移除
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    *a = head;
    return OK;
}

// 逆序（就地反轉鏈表）
Status reverse(Poly head) {
    CHECK(head);
    Poly e = 0, p = head->next, t;
    while(p) {
        t = p->next;
        p->next = e;
        e = p;
        p = t;
    }
    head->next = e;
    return OK;
}

主程式測試

int main() {
    freopen("c:/in.log", "r", stdin);
    Poly a = 0, b = 0;
    if (createPoly(&a)) print(a);
    if (createPoly(&b)) print(b);
    if (SubPoly(&a, &b)) print(a);
    destroyPoly(&a);
    return 0;
}