7-1 一元多项式的乘法与加法运算
设计函数分别求两个一元多项式的乘积与和。
输入格式
输入分 2 行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数 (绝对值均为不超过 1000 的整数)。数字间以空格分隔。
输出格式
输出分 2 行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出 0 0 。
输入样例
1
2
| 4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
|
输出样例
1
2
| 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
|
长度限制：16KB
时间限制：200ms
内存限制：64MB
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include<iostream>
using namespace std;
typedef int dt;
typedef struct LNode{
dt coe,exp;
LNode *next;
}LNode,*List;
List CreatePoly(){
List head=(List)malloc(sizeof(LNode)),curr=head;
head->next=nullptr;
int n;
cin>>n;
if(n==0){
List node=(List)malloc(sizeof(LNode));
node->next=nullptr;
node->coe=node->exp=0;
curr->next=node;
return head;
}
while(n--){
List node=(List)malloc(sizeof(LNode));
node->next=nullptr;
cin>>node->coe>>node->exp;
curr->next=node;
curr=node;
}
return head;
}
void PrintPoly(List L){
List head=L->next;
if(head)
for(List p=head;p;p=p->next){
cout<<p->coe<<" "<<p->exp;
if(p->next) cout<<" ";
}
else cout<<"0 0";
cout<<endl;
}
void SortPoly(List L){
for(List p1=L->next;p1->next;p1=p1->next)
for(List p2=p1->next;p2;p2=p2->next)
if(p2->exp>p1->exp){
dt t=p2->exp; p2->exp=p1->exp; p1->exp=t;
t=p2->coe; p2->coe=p1->coe; p1->coe=t;
}
}
void UnionPoly(List L){
for(List p1=L->next;p1;p1=p1->next)
for(List p2=p1->next;p2;p2=p2->next)
if(p2->exp==p1->exp){
p1->coe=p1->coe+p2->coe;
p2->coe=p2->exp=0;
}
}
void DeleteNullPolyNode(List L){
List p1=L,p2=L->next;
while(p2)
if(p2->coe==0){
p1->next=p2->next;
free(p2);
p2=p1->next;
}else{
p1=p2;
p2=p2->next;
}
}
List MultiPoly(List L1,List L2){
List head=(List)malloc(sizeof(LNode)),curr=head;
head->next=nullptr;
for(List p1=L1->next;p1;p1=p1->next)
for(List p2=L2->next;p2;p2=p2->next){
List node=(List)malloc(sizeof(LNode));
node->next=nullptr;
node->coe=p1->coe*p2->coe;
node->exp=p1->exp+p2->exp;
curr->next=node;
curr=node;
}
UnionPoly(head);
SortPoly(head);
DeleteNullPolyNode(head);
return head;
}
List AddPoly(List L1,List L2){
List head=(List)malloc(sizeof(LNode)),curr=head;
head->next=nullptr;
for(List p1=L1->next;p1;p1=p1->next){
List node=(List)malloc(sizeof(LNode));
node->next=nullptr;
node->coe=p1->coe;
node->exp=p1->exp;
curr->next=node;
curr=node;
}
for(List p2=L2->next;p2;p2=p2->next){
List node=(List)malloc(sizeof(LNode));
node->next=nullptr;
node->coe=p2->coe;
node->exp=p2->exp;
curr->next=node;
curr=node;
}
UnionPoly(head);
SortPoly(head);
DeleteNullPolyNode(head);
return head;
}
int main(){
List L1=CreatePoly();
List L2=CreatePoly();
List L3=MultiPoly(L1,L2);
List L4=AddPoly(L1,L2);
PrintPoly(L3);
PrintPoly(L4);
}
|
