github源碼

一元多項(xiàng)式

在數(shù)學(xué)上，一個(gè)一元多項(xiàng)式Pn(x)可以按升冪寫為：
Pn(x) = p0 + p1x + p2x^2 + ... + pnx^n
它由n+1個(gè)系數(shù)唯一確定，因此可用一個(gè)線性表P來表示。
P = (p0,p1,p2,...,pn)
每一項(xiàng)的指數(shù)i隱含在其系數(shù)pi的序號里。
然而，在通常的應(yīng)用中，多項(xiàng)式的次數(shù)可能很高且變化很大，使得順序存儲的最大長度很難確定。特別是在處理形如：
S(x) = 1 + 3x^10000 + 2x^20000
的多項(xiàng)式時(shí)，就要使用一長度為20001的線性表來表示，表中僅有三個(gè)非零元素，這種對內(nèi)存空間的浪費(fèi)是應(yīng)當(dāng)避免的，但是如果只存非零系數(shù)項(xiàng)則顯然必須同時(shí)存儲相應(yīng)的指數(shù)。
則存儲可表示為（(p1,e1),(p2,e2),...(pn,en)）
顯然，用鏈表來存儲多項(xiàng)式參數(shù)更加靈活，節(jié)省空間。

Polynomial.c文件

#include <stdio.h>
#include <malloc.h>
#include "Polynomial.h"

static void clear(Polynomial *This);
static int isEmpty(Polynomial *This);
static int length(Polynomial *This);
static void print(Polynomial *This);
static int appendElem(Polynomial *This, ElemType e);

Polynomial *InitPolynomial(){
    Polynomial *L = (Polynomial *)malloc(sizeof(Polynomial));
    Node *p = (Node *)malloc(sizeof(Node));
    L->This = p;
    p->next = NULL;
    L->clear = clear;
    L->isEmpty = isEmpty;
    L->length = length;
    L->print = print;
    L->appendElem = appendElem;
    return L;
}

Polynomial *CreatePolynomial(ElemType *params,int length){
    Polynomial *L = InitPolynomial();
    int i;
    for(i=0;i<length;i++){
        L->appendElem(L, *(params+i));
    }
    return L;
}

void DestroyPolynomial(Polynomial *L){
    L->clear(L);
    free(L->This);
    free(L);
    L = NULL;
}

static void clear(Polynomial *This){
    Node *p = This->This->next;
    Node *temp = NULL;
    while(p){
        temp = p;
        p = p->next;
        free(temp);
    } 
    p = This->This;
    p->next = NULL;
}

static int isEmpty(Polynomial *This){
    Node *p = This->This;
    if(p->next){
        return 0;
    }else{
        return 1;
    }
}

static int length(Polynomial *This){
    int j = 0;
    Node *p = This->This->next;
    while(p){
        j++;
        p = p->next;
    } 
    return j;
}

static void print(Polynomial *This){
    Node *p = This->This->next;
    if(p){
        printf("%fx^%f", p->elem.coefficient,p->elem.exponent);
        p = p->next;
    }
    while(p){
        printf(" + %fx^%f", p->elem.coefficient,p->elem.exponent);
        p = p->next;
    } 
    printf("\n");
}

static int appendElem(Polynomial *This, ElemType e){
    Node *p = This->This;
    Node *temp = (Node *)malloc(sizeof(Node));
    if(!temp) return -1;
    while(p){
        if(NULL == p->next){
            temp->elem.coefficient = e.coefficient;
            temp->elem.exponent = e.exponent;
            p->next = temp;
            temp->next =  NULL;
        }
        p = p->next;
    } 
    return 0;
}

Polynomial *addPolynomial(Polynomial *pa,Polynomial *pb){
    Polynomial *L = InitPolynomial();
    ElemType a,b,sum;
    Node *ha = pa->This->next;
    Node *hb = pb->This->next;
    while(ha&&hb){
        a = ha->elem;
        b = hb->elem;
        if(a.exponent > b.exponent){
            L->appendElem(L, b);
            hb = hb->next;
        }else if(a.exponent == b.exponent){
            sum.exponent = a.exponent;
            sum.coefficient = a.coefficient + b.coefficient;
            if(sum.coefficient != 0){
                L->appendElem(L, sum);
            }
            ha = ha->next;
            hb = hb->next;
        }else{
            L->appendElem(L, a);
            ha = ha->next;
        }
    }
    while(ha){
        a = ha->elem;
        L->appendElem(L, a);
        ha = ha->next;
    }
    while(hb){
        b = hb->elem;
        L->appendElem(L, b);
        hb = hb->next;
    }
    return L;
}

Polynomial *subPolynomial(Polynomial *pa,Polynomial *pb){
    Polynomial *L = InitPolynomial();
    ElemType a,b,sub;
    Node *ha = pa->This->next;
    Node *hb = pb->This->next;
    while(ha&&hb){
        a = ha->elem;
        b = hb->elem;
        if(a.exponent > b.exponent){
            sub.exponent = b.exponent;
            sub.coefficient = -b.coefficient;
            L->appendElem(L, sub);
            hb = hb->next;
        }else if(a.exponent == b.exponent){
            sub.exponent = a.exponent;
            sub.coefficient = a.coefficient - b.coefficient;
            if(sub.coefficient != 0){
                L->appendElem(L, sub);
            }
            ha = ha->next;
            hb = hb->next;
        }else{
            L->appendElem(L, a);
            ha = ha->next;
        }
    }
    while(ha){
        a = ha->elem;
        L->appendElem(L, a);
        ha = ha->next;
    }
    while(hb){
        b = hb->elem;
        sub.exponent = b.exponent;
        sub.coefficient = -b.coefficient;
        L->appendElem(L, sub);
        hb = hb->next;
    }
    return L;
}

Polynomial *kMulPolynomial(Polynomial *pa,ElemType a){
    Polynomial *L = InitPolynomial();
    Node *ha = pa->This->next;
    ElemType temp;
    while(ha){
        temp.exponent = ha->elem.exponent + a.exponent;
        temp.coefficient = ha->elem.coefficient * a.coefficient;
        L->appendElem(L, temp);
        ha = ha->next;
    }
    return L;
}

Polynomial *mulPolynomial(Polynomial *pa,Polynomial *pb){
    Polynomial *temp = InitPolynomial();
    Polynomial *temp1 = NULL,*temp2 = NULL;
    Node *hb = pb->This->next;
    while(hb){
        temp1 = kMulPolynomial(pa,hb->elem);
        temp2 = addPolynomial(temp1,temp);
        DestroyPolynomial(temp1);   
        DestroyPolynomial(temp);
        temp = temp2;
        hb = hb->next;
    }
    return temp;
}

Polynomial.h文件

/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef __POLYNOMIAL_H
#define __POLYNOMIAL_H
/* Includes ------------------------------------------------------------------*/
/* Exported types ------------------------------------------------------------*/
typedef struct ElemType{
    double coefficient; //系數(shù)
    double exponent;//指數(shù)
}ElemType;

typedef struct Node{
    ElemType elem;  //存儲空間
    struct Node *next;
}Node;

typedef struct Polynomial{
    Node *This;
    void (*clear)(struct Polynomial *This);
    int (*isEmpty)(struct Polynomial *This);
    int (*length)(struct Polynomial *This);
    void (*print)(struct Polynomial *This);
    int (*appendElem)(struct Polynomial *This, ElemType e);
}Polynomial;

/* Exported macro ------------------------------------------------------------*/
Polynomial *CreatePolynomial(ElemType *params,int length);
void DestroyPolynomial(Polynomial *L);
Polynomial *addPolynomial(Polynomial *pa,Polynomial *pb);
Polynomial *subPolynomial(Polynomial *pa,Polynomial *pb);
Polynomial *kMulPolynomial(Polynomial *pa,ElemType a);
Polynomial *mulPolynomial(Polynomial *pa,Polynomial *pb);

#endif

testPolynomial.c文件

#include <stdio.h>
#include <malloc.h>
#include "Polynomial.h"

int main(void){
    //7+3x+9X^8+5x^17
    ElemType params_a[4]={{7,0},{3,1},{9,8},{5,17}};
    //8x+22x^7+-9x^8
    ElemType params_b[3]={{8,1},{22,7},{-9,8}};
    Polynomial *pa = CreatePolynomial(params_a,4);
    Polynomial *pb = CreatePolynomial(params_b,3);
    Polynomial *sum_ab,*sub_ab,*mul_ab,*kmul_a;
    printf("pa = ");
    pa->print(pa);
    printf("pb = ");
    pb->print(pb);
    sum_ab = addPolynomial(pa,pb);
    printf("pa + pb = ");
    sum_ab->print(sum_ab);
    sub_ab = subPolynomial(pa,pb);
    printf("pa - pb = ");
    sub_ab->print(sub_ab);
    mul_ab = mulPolynomial(pa,pb);
    printf("pa * pb = ");
    mul_ab->print(mul_ab);
    kmul_a = kMulPolynomial(pa,params_b[0]);
    printf("pa * 8x = ");
    kmul_a->print(kmul_a);
    DestroyPolynomial(pa);
    DestroyPolynomial(pb);
    DestroyPolynomial(sum_ab);
    DestroyPolynomial(mul_ab);
    DestroyPolynomial(kmul_a);
    return 0;
}

編譯：

gcc Polynomial.c Polynomial.h testPolynomial.c -o testPolynomial

運(yùn)行testPolynomial
輸出：

pa = 7.000000x^0.000000 + 3.000000x^1.000000 + 9.000000x^8.000000 + 5.000000x^17.000000
pb = 8.000000x^1.000000 + 22.000000x^7.000000 + -9.000000x^8.000000
pa + pb = 7.000000x^0.000000 + 11.000000x^1.000000 + 22.000000x^7.000000 + 5.000000x^17.000000
pa - pb = 7.000000x^0.000000 + -5.000000x^1.000000 + -22.000000x^7.000000 + 18.000000x^8.000000 + 5.000000x^17.000000
pa * pb = 56.000000x^1.000000 + 24.000000x^2.000000 + 154.000000x^7.000000 + 3.000000x^8.000000 + 45.000000x^9.000000 + 198.000000x^15.000000 + -81.000000x^16.000000 + 40.000000x^18.000000 + 110.000000x^24.000000 + -45.000000x^25.000000
pa * 8x = 56.000000x^1.000000 + 24.000000x^2.000000 + 72.000000x^9.000000 + 40.000000x^18.000000