原题链接：https://pta.patest.cn/pta/test/15/exam/4/question/710
题目：
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分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 #include<stdio.h> 2 #include<stdlib.h> 3 /* 定义结构，但是更推荐这种定义 4 typedef struct PolyNode{ 5 int coef; 6 int expon; 7 struct PolyNode *Next; 8 }*PolyNode; */ 9 typedef struct PolyNode *Polynomial ; 10 struct PolyNode 11 { 12 int coef; 13 int expon; 14 Polynomial Next; 15 }; 16 /*连接函数，通过参数的传递，构成链表，注意*rear是指针的指针，故能修改rear的地址（值）*/ 17 void Attach(int coef,int expon,Polynomial *rear) 18 { 19 Polynomial P; 20 P=(Polynomial)malloc(sizeof(struct PolyNode)); 21 P->coef=coef; 22 P->expon=expon; 23 P->Next=NULL; 24 (*rear)->Next=P; 25 (*rear)=P; 26 } 27 /* 读入数据函数*/ 28 Polynomial ReadPoly() 29 { 30 int N; 31 int coef,expon; 32 Polynomial P,rear,t; 33 P=(Polynomial)malloc(sizeof(struct PolyNode)); //采用开头构造空节点P的方法 34 P->Next=NULL; 35 rear=P; 36 scanf("%d",&N); 37 while(N--) 38 { 39 scanf("%d %d",&coef,&expon); 40 Attach(coef,expon,&rear); 41 } 42 t=P; 43 P=P->Next; 44 free(t); //将空节点删除 45 return P; 46 } 47 /* 加法的实现函数 */ 48 Polynomial Add(Polynomial P1,Polynomial P2) 49 { 50 Polynomial P,rear,t; 51 P=(Polynomial)malloc(sizeof(struct PolyNode)); //创建空节点 52 P->Next=NULL; 53 rear=P; // rear 指向P 54 int sum; 55 while(P1 && P2) 56 { 57 if (P1->expon>P2->expon) //按指数递减的顺序排列 58 { 59 Attach(P1->coef,P1->expon,&rear); //拷贝P1,P1后移，依次类推 60 P1=P1->Next; 61 } 62 else if (P1->expon<P2->expon) 63 { 64 Attach(P2->coef,P2->expon,&rear); 65 P2=P2->Next; 66 } 67 else 68 { 69 sum=P1->coef+P2->coef; 70 if (sum) Attach(sum,P1->expon,&rear); //系数之和不为0才拷贝，P1,P2同时后移 71 P1=P1->Next; 72 P2=P2->Next; 73 } 74 } 75 while (P1){Attach(P1->coef,P1->expon,&rear);P1=P1->Next;} //继续将剩下的拷贝过去 76 while (P2){Attach(P2->coef,P2->expon,&rear);P2=P2->Next;} 77 t=P; 78 P=P->Next; 79 free(t); //释放空的头节点 80 return P; 81 } 82 /* 乘法实现的函数 */ 83 Polynomial Mult(Polynomial P1,Polynomial P2) 84 { 85 Polynomial P,rear,t1,t2,t; 86 int c,e; 87 if (!P1 || !P2) return NULL; 88 t1 = P1; 89 t2 = P2; 90 P = (Polynomial)malloc(sizeof(struct PolyNode)); 91 P->Next = NULL; 92 rear = P; 93 while(t2) //先得出一个链表，即P1的第一项分别和P2的每一项相乘 94 { 95 Attach(t1->coef * t2->coef,t1->expon + t2->expon,&rear); 96 t2 = t2->Next; 97 } 98 t1=t1->Next; 99 while (t1) //将每一项结果和原始链表对比，对原始链表进行增，改，删等操作 100 { 101 t2 = P2; 102 rear = P; 103 while(t2) 104 { 105 e = t1->expon + t2->expon; 106 c = t1->coef * t2->coef; 107 while(rear->Next && rear->Next->expon>e )rear=rear->Next; //！！！一定注意&&前后表达式顺序不能反！ 108 if (rear->Next && rear->Next->expon==e) 109 { 110 if(rear->Next->coef+c)rear->Next->coef+=c; 111 else{t=rear->Next;rear->Next=t->Next;free(t);}//删除该节点 112 } 113 else //<e， 在rear后插入一个新的节点 114 { 115 t=(Polynomial)malloc(sizeof(struct PolyNode)); 116 t->coef=c; 117 t->expon=e; 118 t->Next=rear->Next; 119 rear->Next=t; 120 rear=rear->Next; 121 } 122 t2=t2->Next; 123 } 124 t1=t1->Next; 125 } 126 t=P; 127 P=P->Next; 128 free(t); //释放空的头节点 129 return P; 130 } 131 /* 输出函数 */ 132 void PrintPoly(Polynomial P) 133 { 134 int flag=0; 135 if(!P){printf("0 0 ");return;} 136 while(P) 137 { 138 if (!flag)flag=1; //符合题目要求格式，即结尾没有空格 139 else printf(" "); 140 printf("%d %d",P->coef,P->expon); 141 P=P->Next; 142 } 143 printf(" "); 144 } 145 int main() 146 { 147 Polynomial P1,P2,PP,PS; 148 P1=ReadPoly(); 149 P2=ReadPoly(); 150 PP=Mult(P1,P2); 151 PrintPoly(PP); 152 PS=Add(P1,P2); 153 PrintPoly(PS); 154 return 0; 155 }