设计函数分别求两个一元多项式的乘积与和。 输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
输入样例:
4 3 4 -5 2 6 1 -2 0
3 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 1
5 20 -4 4 -5 2 9 1 -2 0
题意理解
求解思路 1.多项式表示 数据结构设计 //将struct与typedef分开定义typedef struct PolyNode *Polynomial;//使用 typedef 给一个还未完全声明的类型 PolyNode 起了一个新别名Polynomialstruct PolyNode{int coef;//系数int expon;//指数Polynomial link;//指向下一个域的指针（声明link，类型是Polynomial，Polynomial表示的是结构体的别名）};
2.程序框架 int main(){Polynomial P1,P2,PP,PS;//读入多项式1，P1、P2都是链表结构的指针P1=ReadPoly();//读入多项式2P2=ReadPoly();//乘法运算并输出，返回的也是指针PP=Mult(P1,P2);PrintPoly(PP);//加法运算并输出PS=Add(P1,P2);PrintPoly(PS);return 0;} 3.读多项式
题目要求先输入有多少项，再一对对输入系数和指数，中间用空格分隔
Rear初值是多少？
两种处理方法：
Rear初值为NULL，在Attach函数中根据Rear是否为NULL做不同处理Rear指向一个空结点，最后再删除空结点（一致性更强）
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);//每读入一个结点，插在当前结果表达式的后面。rear要改变，所以传指针Attach(c,e,&Rear);}//删除临时生成的头节点t=P;P=P->link;free(t);return P;}
//传入系数、指数、Polynomial类型的指针（Polynomial本身也是指针）void Attach(int c,int e,Polynomial *pRear){Polynomial P;//申请新结点，结点类型为结构体PolyNodeP=(Polynomial)malloc(sizeof(struct PolyNode));//对新结点赋值P->coef=c;P->expon=e;P->link=NULL;(*pRear)->link=P;*pRear=P;//修改pRear的值} 4.加法实现 int compare(int e1,int e2){ if(e1>e2) return 1; else if(e1<e2) return -1; else return 0;}Polynomial Add(Polynomial P1,Polynomial P2){ Polynomial PS,rear,temp; int sum; //构造空结点，rear指向当前处理结果的尾巴 PS=(Polynomial)malloc(sizeof(struct PolyNode)); PS->link=NULL; rear=PS; 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);//coef=0 then do nothing P1=P1->link; P2=P2->link; break; } } while(P1){ Attach(P1->coef,P1->expon,&rear); P1=P1->link; } while(P2){ Attach(P2->coef,P2->expon,&rear); P2=P2->link; } //rear->link=NULL; temp=PS; PS=PS->link; free(temp); return PS;} 5.乘法实现
将P1当前项(c1i,e1i)乘P2当前项（c2i,e2i),并插入到结果多项式中。关键是要找到插入位置（要求指数递减）
初始结果多项式可由P1第一项乘P2获得（如上）
Polynomial Mult(Polynomial P1,Polynomial P2){Polynomial P,Rear,t1,t2,t;int c,e;//P1、P2相乘， 只要有一个为空，返回nullif(!P1||!P2) return NULL;t1=P1;t2=P2;//申请空结点P=(Polynomial)malloc(sizeof(struct PolyNode));P->link=NULL;Rear=P;//先用P1的第一项乘以P2，得到Pwhile(t2){Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);t2=t2->link;//t2往后挪}t1=t1->link;//两重循环 t1每一项乘t2每一项while(t1){t2=P2;Rear=P;//Rear一开始指向Pwhile(t2){e=t1->expon+t2->expon;//指数相加得到当前指数c=t1->coef*t2->coef;//系数相乘得到当前系数//找插入位置。比较指数，将当前结果按照指数降序插进结果多项式while(Rear->link&&Rear->link->expon>e)//Rear的下一项的指数大于要插入的指数，所以rear还要往后挪Rear=Rear->link;if(Rear->link&&Rear->link->expon==e){//Rear的下一项的指数等于要插入的指数，要做合并if(Rear->link->coef+c)//系数相加后不等于0，c加进原来的Rear->link->coef+=c;else{//系数相加后等于0，删掉t=Rear->link;Rear->link=t->link;free(t);}}else{//Rear的下一项的指数小于要插入的指数，可以插入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;} 6.多项式输出
链表遍历
void PrintPoly(Polynomial P){ /* 输出多项式 */int flag = 0; /* 辅助调整输出格式用 */if (!P) {printf("0 0n"); return;}while (P) {if (!flag)flag = 1;elseprintf(" ");printf("%d %d", P->coef, P->expon);P = P->link;}printf("n");} 运行结果