一元多项式
在数学上，一个一元多项式Pn(x)可以按升幂写为：
Pn(x) = p0 + p1x + p2x^2 + ... + pnx^n
它由n+1个系数唯一确定，因此可用一个线性表P来表示。
P = (p0,p1,p2,...,pn)
每一项的指数i隐含在其系数pi的序号里。
然而，在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储的最大长度很难确定。特别是在处理形如：
S(x) = 1 + 3x^10000 + 2x^20000
的多项式时，就要使用一长度为20001的线性表来表示，表中仅有三个非零元素，这种对内存空间的浪费是应当避免的，但是如果只存非零系数项则显然必须同时存储相应的指数。
则存储可表示为（(p1,e1),(p2,e2),...(pn,en)）
显然，用链表来存储多项式参数更加灵活，节省空间。
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; //系数
double exponent;//指数
}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
运行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
