02-线性结构2 一元多项式的乘法与加法运算

#include <stdio.h> #include <stdlib.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; } Polynomial Add(Polynomial P1,Polynomial P2) { Polynomial P,temp,t1,t2; t1=P1; t2=P2; P=(Polynomial)malloc(sizeof(struct PolyNode));//链表头空结点 P->link=NULL; temp=P; while(t1&&t2) { if(t1->expon==t2->expon) { if(!(t1->coef+t2->coef)==0) { Attach(t1->coef+t2->coef,t1->expon,&temp); t1=t1->link; t2=t2->link; } else //相加系数为0 { t1=t1->link; t2=t2->link; } } else if(t1->expon>t2->expon) { Attach(t1->coef,t1->expon,&temp); t1=t1->link; } else if(t1->expon<t2->expon) { Attach(t2->coef,t2->expon,&temp); t2=t2->link; } } for(;t1;t1=t1->link) //一个多项式已经加完 { Attach(t1->coef,t1->expon,&temp); } for(;t2;t2=t2->link) { Attach(t2->coef,t2->expon,&temp); } temp=P; P=P->link; free(temp); return P; } Polynomial Mult(Polynomial P1,Polynomial P2) { Polynomial P,Rear,t1,t2,t; int c,e; if(!P1||!P2) return NULL; t1=P1;t2=P2; P=(Polynomial)malloc(sizeof(struct PolyNode)); P->link=NULL; Rear=P; while(t2) //先用P1的第一项乘以P2，得到P,后面是往里面插 { Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear); t2=t2->link; } t1=t1->link; while(t1) { t2=P2; Rear=P; while(t2) { //Attach(t1->coef*t2->coef,t1->expon+t2->expon;&Rear); 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) //相加系数不为0 Rear->link->coef+=c; else{ //相加系数为0，删除该结点 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; } t=P; P=P->link; free(t); return P; } void PrintPoly(Polynomial P) { if(!P) { printf("0 0"); } while(P) { printf("%d %d",P->coef,P->expon); P=P->link; if(!P==NULL) //只有在指针域不为NULL时，才输出空格间隔开每个多项式。即在多项式末位没有空格 { printf(" "); } } printf("\n"); } int main() { Polynomial P1,P2,PP,PS; P1=ReadPoly(); P2=ReadPoly(); PP=Mult(P1,P2); PrintPoly(PP); PS=Add(P1,P2); PrintPoly(PS); return 0; }