一元多项式的乘法与加法运算
1.问题描述2.问题分析2.1定义多项式数据结构结点数据PolyNode2.2将数据结点连接到多项式后面Attach2.3读入多项式数据结点ReadPoly2.4多项式求和Add2.5多项式求积Mult2.6打印多项式PrintPoly 3.代码分析3.1完整代码3.2输入输出结果1.问题描述
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
输入样例:
4 3 4 -5 2 6 1 -2 03 5 20 -7 4 3 1
输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 15 20 -4 4 -5 2 9 1 -2 0
2.问题分析
程序可以大概分为四部分：多项式数据结构表示、读入数据、求解数据（求和、求积）、输出数据。分别定义函数如下：
ReadPoly();//读入多项式结点数据
Add(P1,P2);//多项式求和
Mult(P1,P2);//多项式求积
PrintPoly(PS);//输出多项式数据
2.1定义多项式数据结构结点数据PolyNode
多项式由系数和次数组成，定义一个结构体链表，成员为系数coef、指数expon以及下一个结点的地址link。
//设计数据结构进行表示typedef struct PolyNode* Polynomial;struct PolyNode{int coef;//系数int expon;//指数Polynomial link;//下一个结点};
2.2将数据结点连接到多项式后面Attach
主要是负责为多项式继续添加结点，输入参数为新结点的指数、系数，以及尾结点指针。
//连接到多项式后面 void Attach(int c,int e,Polynomial* pRear){Polynomial P;//开辟一个结点，存储新插入的结点P=(Polynomial)malloc(sizeof(struct PolyNode)) ;P->coef=c;P->expon=e;P->link=NULL;//该结点指向空，表示最后一个结点(*pRear)->link=P;//让尾指针指向该结点*pRear=P;//修改pRear的值为新添加的这个结点 }
2.3读入多项式数据结点ReadPoly
首先输入该多项式的项数，然后按照指数递减的方式输入每个结点。每次循环读入一对数，读入系数和指数后构造结点，插入多项式中；
//读入多项式Polynomial ReadPoly(){Polynomial P,Rear,t;int c,e,N; scanf("%d",&N);//输入结点个数，即多项式的项数P=(Polynomial)malloc(sizeof(struct PolyNode));/*链表空头结点*/P->link=NULL;//第一个指针置为空，从下一个结点开始存储读入的多项式结点。Rear=P;//尾指针指向Pwhile(N--)//依次读入新的结点（多项式）{scanf("%d %d",&c,&e);Attach(c,e,&Rear);} /*将当前项插入多项式尾部*/t=P;P=P->link;free(t);/*删除临时生成的头结点*/return P; }
2.4多项式求和Add
求和的过程就是首先判断指数是否相同，如果相同，就对系数求和添加进入结果多项式中。如果不同，就将系数大的一个结点插入到结果多项式中。
int Compare(int a,int b){if(a>b)return 1;else if(a<b) return -1;else return 0;}Polynomial Add(Polynomial P1,Polynomial P2){Polynomial front,rear,temp;int sum;//为方便表头插入，先产生一个临时空结点作为结果多项式链表头 rear=(Polynomial)malloc(sizeof(struct PolyNode));front=rear;//由front记录结果多项式链表头结点while(P1&&P2)//如果都不为空，则将当前指数大的一项存入结果多项式{switch(Compare(P1->expon,P2->expon)){case 1://P1的结点大的情况Attach(P1->coef,P1->expon,&rear);P1=P1->link;break;case -1://P2的结点大的情况Attach(P2->coef,P2->expon,&rear);P2=P2->link;break;case 0://两个节点一样大的情况，系数相加存入多项式结点sum=P1->coef+P2->coef;if(sum)Attach(sum,P1->expon,&rear);P1=P1->link;P2=P2->link;break;}} /*将未处理完的另一个多项式的所有结点依次复制到结果多项式中*/for(;P1;P1=P1->link) Attach(P1->coef,P1->expon,&rear);for(;P2;P2=P2->link) Attach(P2->coef,P2->expon,&rear);rear->link=NULL;temp=front;front=front->link;/*令front指向结果多项式的第一个非零项*/free(temp);/*释放临时空表头结点*/return front; }
2.5多项式求积Mult
先用P1的第1项依次乘P2的每一项生成结果多项式，再循环遍历P1的每一项和P2的每一项相乘将结果添加到结果多项式中。
Polynomial Mult(Polynomial P1,Polynomial P2){Polynomial t1,t2,P,Rear,t;int c,e;if(!P1||!P2)return NULL;t1=P1;t2=P2; P=(Polynomial)malloc(sizeof(struct PolyNode));P->link=NULL;Rear=P;//P作为空节点，Rear负责接收后续的结点 //先用P1的第1项乘以P2，得到P while(t2){Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);t2=t2->link;}t1=t1->link;while(t1){t2=P2;Rear=P;while(t2){e=t1->expon+t2->expon;c=t1->coef*t2->coef;while(Rear->link&&Rear->link->expon>e)Rear=Rear->link;if(Rear->link&&Rear->link->expon==e){if(Rear->link->coef+c)Rear->link->coef+=c;else{t=Rear->link;Rear->link=t->link;free(t);}}else{t=(Polynomial)malloc(sizeof(struct PolyNode));t->coef=c;t->expon=e;t->link=Rear->link;Rear->link=t;Rear=Rear->link;}t2=t2->link;}t1=t1->link;}t2=P;P=P->link;free(t2);return P;}
2.6打印多项式PrintPoly
依次遍历结点，输出系数和指数即可。
void PrintPoly(Polynomial P){/*输出多项式*/int flag=0;if(!P){printf("0 0\n");return;}while(P){if(!flag)flag=1;elseprintf(" ");printf("%d %d",P->coef,P->expon);P=P->link;}printf("\n");}
3.代码分析
3.1完整代码
#include <stdio.h>//设计数据结构进行表示typedef struct PolyNode* Polynomial;struct PolyNode{int coef;int expon;Polynomial link;}; //连接到多项式后面 void Attach(int c,int e,Polynomial* pRear){Polynomial P;P=(Polynomial)malloc(sizeof(struct PolyNode)) ;P->coef=c;P->expon=e;P->link=NULL;(*pRear)->link=P;*pRear=P;//修改pRear的值 为新添加的这个结点 }//读入多项式Polynomial ReadPoly(){Polynomial P,Rear,t;int c,e,N; scanf("%d",&N);P=(Polynomial)malloc(sizeof(struct PolyNode));/*链表空头结点*/P->link=NULL;Rear=P;while(N--){scanf("%d %d",&c,&e);Attach(c,e,&Rear);} /*将当前项插入多项式尾部*/t=P;P=P->link;free(t);/*删除临时生成的头结点*/return P; } void PrintPoly(Polynomial P){/*输出多项式*/int flag=0;if(!P){printf("0 0\n");return;}while(P){if(!flag)flag=1;elseprintf(" ");printf("%d %d",P->coef,P->expon);P=P->link;}printf("\n");}int Compare(int a,int b){if(a>b)return 1;else if(a<b) return -1;else return 0;}Polynomial Add(Polynomial P1,Polynomial P2){Polynomial front,rear,temp;int sum;//为方便表头插入，先产生一个临时空结点作为结果多项式链表头 rear=(Polynomial)malloc(sizeof(struct PolyNode));front=rear;//由front记录结果多项式链表头结点while(P1&&P2){switch(Compare(P1->expon,P2->expon)){case 1:Attach(P1->coef,P1->expon,&rear);P1=P1->link;break;case -1:Attach(P2->coef,P2->expon,&rear);P2=P2->link;break;case 0:sum=P1->coef+P2->coef;if(sum)Attach(sum,P1->expon,&rear);P1=P1->link;P2=P2->link;break;}} /*将未处理完的另一个多项式的所有结点依次复制到结果多项式中*/for(;P1;P1=P1->link) Attach(P1->coef,P1->expon,&rear);for(;P2;P2=P2->link) Attach(P2->coef,P2->expon,&rear);rear->link=NULL;temp=front;front=front->link;/*令front指向结果多项式的第一个非零项*/free(temp);/*释放临时空表头结点*/return front; }Polynomial Mult(Polynomial P1,Polynomial P2){Polynomial t1,t2,P,Rear,t;int c,e;if(!P1||!P2)return NULL;t1=P1;t2=P2; P=(Polynomial)malloc(sizeof(struct PolyNode));P->link=NULL;Rear=P;//P作为空节点，Rear负责接收后续的结点 //先用P1的第1项乘以P2，得到P while(t2){Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);t2=t2->link;}t1=t1->link;while(t1){t2=P2;Rear=P;while(t2){e=t1->expon+t2->expon;c=t1->coef*t2->coef;while(Rear->link&&Rear->link->expon>e)Rear=Rear->link;if(Rear->link&&Rear->link->expon==e){if(Rear->link->coef+c)Rear->link->coef+=c;else{t=Rear->link;Rear->link=t->link;free(t);}}else{t=(Polynomial)malloc(sizeof(struct PolyNode));t->coef=c;t->expon=e;t->link=Rear->link;Rear->link=t;Rear=Rear->link;}t2=t2->link;}t1=t1->link;}t2=P;P=P->link;free(t2);return P;}int main(int argc, char** argv) {Polynomial P1,P2,PP,PS;P1=ReadPoly();P2=ReadPoly();PP=Add(P1,P2);PS=Mult(P1,P2);PrintPoly(PS);PrintPoly(PP);return 0;}
3.2输入输出结果
4 3 4 -5 2 6 1 -2 03 5 20 -7 4 3 115 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 15 20 -4 4 -5 2 9 1 -2 0
