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

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

时间限制：200ms
内存限制：64MB
代码长度限制：16kB
判题程序：系统默认
作者：DS课程组
单位：浙江大学

https://pta.patest.cn/pta/test/3512/exam/4/question/62613

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分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<bits/stdc++.h>
  2 using namespace std;
  3 
  4 typedef struct Node *List;
  5 struct Node
  6 {
  7     int coef,expon;
  8     Node *next;
  9 };
 10 
 11 List build(int n);
 12 void print(List L);
 13 void attach(int c,int e,List &tail);
 14 List Plus(List L1,List L2);
 15 List Mult(List L1,List L2);
 16 
 17 int main()
 18 {
 19     int n;
 20     List L1,L2,L3,L4;
 21     cin>>n;
 22     L1=build(n);
 23     cin>>n;
 24     L2=build(n);
 25     L3=Plus(L1,L2);
 26     L4=Mult(L1,L2);
 27     print(L4);
 28     print(L3);
 29     return 0;
 30 }
 31 List build(int n)
 32 {
 33     if(!n)
 34         return NULL;
 35     List L=new Node,p=L;
 36     int x,y;
 37     while(n--)
 38     {
 39         cin>>x>>y;
 40         if(n)
 41             p->next=new Node;
 42         p->coef=x;
 43         p->expon=y;
 44         if(n)
 45             p=p->next;
 46     }
 47     p->next=NULL;
 48     return L;
 49 }
 50 void print(List L)
 51 {
 52     if(!L)
 53     {
 54         cout<<"0 0
";
 55         return;
 56     }
 57     List p=L;
 58     while(p)
 59     {
 60         cout<<p->coef<<' '<<p->expon<<((p->next)?" ":"
");
 61         p=p->next;
 62     }
 63 }
 64 void attach(int c,int e,List &tail)
 65 {
 66     List p=new Node;
 67     p->coef=c;
 68     p->expon=e;
 69     p->next=NULL;
 70     tail->next=p;
 71     tail=p;
 72 }
 73 List Plus(List L1,List L2)
 74 {
 75     List L=new Node,tail=L;
 76     while(L1&&L2)
 77     {
 78         int flag=L1->expon-L2->expon;
 79         if(flag>0)
 80         {
 81             attach(L1->coef,L1->expon,tail);
 82             L1=L1->next;
 83         }
 84         else if(flag<0)
 85         {
 86             attach(L2->coef,L2->expon,tail);
 87             L2=L2->next;
 88         }
 89         else
 90         {
 91             int c=L1->coef+L2->coef;
 92             if(c)
 93                 attach(c,L1->expon,tail);
 94             L1=L1->next;
 95             L2=L2->next;
 96         }
 97     }
 98     for(;L1;L1=L1->next)
 99         attach(L1->coef,L1->expon,tail);
100     for(;L2;L2=L2->next)
101         attach(L2->coef,L2->expon,tail);
102     List t=L->next;
103     delete(L);
104     L=t;
105     return L;
106 }
107 List Mult(List L1,List L2)
108 {
109     if(!L1||!L2)
110         return NULL;
111     List L=NULL,t,t1=new Node;
112     for(;L1;L1=L1->next)
113     {
114         List tail=t1;
115         for(List t2=L2;t2;t2=t2->next)
116         {
117             attach(L1->coef*t2->coef,L1->expon+t2->expon,tail);
118         }
119         L=Plus(L,t1->next);
120         tail=t1->next;
121         while(tail)
122         {
123             t=tail->next;
124             delete(tail);
125             tail=t;
126         }
127     }
128     delete(t1);
129     return L;
130 }