7-2 一元多项式的乘法与加法运算

题目描述

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

输入

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

思路

首先要确定多项式的储存结构,决定用链表按照指数递降顺序存储。

接下来无非就是两个难题,一个是怎么加,一个是怎么乘。

难点

一开始的时候我乘法用了我现在用的加法算法在一个个向后推,可以说是相当的蠢萌了。

加法标准做法是3个循环搞定,第一轮循环两个链表同时向后推,一个推到最后就把另一个剩下的全接上去就可以了。

乘法有很多种做法,我用了老师讲的插入法。

两轮循环,每一次都要向已有的链表上插入一个新的点,有时需要合并,有时需要删点。

源代码

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <iostream>
using namespace std;
const int MAX = 1003;
struct node{
int coef;//系数
int expo;//指数
node * next;
};
node * CreatList(node * head); //单链表的读入与创建
void PrintList(node * head); //输出以head为头结点的链表
node * MultiplyList(node * p1, node *p2); //多项式乘法
void Attach(int coef, int expo, node **nodepointer); //插入一个节点至nodepointer后
node * AddList(node * p1, node *p2); //多项式加法
void FreeList(node * p); //内存释放

int main(int argc, char const *argv[]) {
node *head1 = NULL, *head2 = NULL;
head1 = CreatList(head1);
head2 = CreatList(head2);
node *multi = MultiplyList(head1, head2);
node *add = AddList(head1, head2);
PrintList(multi);cout << endl;
PrintList(add);
FreeList(head1);FreeList(head2);FreeList(multi);FreeList(add);
return 0;
}

node * CreatList(node * head)
{
int coef, expo, k;
node * p;
head = new node;
cin >> k;
if ( !k ) return NULL;
cin >> coef >> expo;
head->coef = coef;
head->expo = expo;
head->next = NULL;
p = head;
for (size_t i = 1; i < k; i++) {
cin >> coef >> expo;
node *temp = new node;
p->next = temp;
temp->coef = coef;
temp->expo = expo;
temp->next = NULL;
p = temp;
}
return head;
}

void PrintList(node * head)
{
if ( !head ) {
cout << "0 0";
}
while ( head ) {
cout << head->coef << " " << head->expo;
head = head->next;
if ( head ) cout << " ";
}
}
//by inserting to the right place 2 loops
node * MultiplyList(node * p1, node *p2)//p is the pointor
{ //poining to the current node
node *head = new node;
head->expo = MAX;
head->next = NULL;
while ( p1 ) {
node *p = p2;
while ( p ) {
//PrintList(head->next);
//cout << endl << endl;
int coef = p1->coef * p->coef;
int expo = p1->expo + p->expo;
node *temp = head;
while ( true ) { //point to one in front
// cout << "once ";
if ( !(temp->next) || temp->next->expo<=expo ) break;
temp = temp->next;
}
//now temp points to the insert place ahead
// cout << "now expo is " << expo;
// cout << "my temp->expo = " << temp->expo << endl;
if ( temp->next && temp->next->expo == expo ) {
if ( temp->next->coef + coef == 0 ) { //delete
node * tobefreed = temp->next;
temp->next = tobefreed->next;
delete tobefreed;
}else { //join together
temp->next->coef += coef;
}
}else Attach(coef, expo, &temp);
p = p->next;
}
p1 = p1->next;
}
node * tobedeleted = head;
head = head->next;
delete tobedeleted;
return head;
}

void Attach(int coef, int expo, node **nodepointer)
{
// cout << "now coef=" << coef << " expo=" << expo <<
// " inserted after expo=" << (*nodepointer)->expo << endl;
node * temp = new node;
temp->coef = coef;
temp->expo = expo;
temp->next = (*nodepointer)->next;
(*nodepointer)->next = temp;//here
// cout << "now temp->next=" << temp->next;
// cout << " *nodepointer points to expo" << (*nodepointer)->expo;
}

node * AddList(node * p1, node *p2) //receive 2 pointers and return the AddList
{ //head is a pointer to the head node
node * p, * head;
head = new node; //head is a head noder contains
p = head; //nothing but a next pointor
head->coef = 0;
head->expo = 0;
head->next = NULL;
while ( p1 && p2 ) {
int expo1, expo2;
expo1 = p1->expo;
expo2 = p2->expo;
if ( expo1 > expo2 ) {//copy
p->next = new node;
p = p->next;
p->next = NULL;
p->expo = p1->expo;
p->coef = p1->coef;
p1 = p1->next;
}else if ( expo1 < expo2 ) {
p->next = new node;
p = p->next;
p->next = NULL;
p->expo = p2->expo;
p->coef = p2->coef;
p2 = p2->next;
}else {
int coef = p1->coef + p2->coef;
if ( coef ) {
p->next = new node;
p = p->next;
p->next = NULL;
p->expo = p1->expo;
p->coef = coef;
}
p1 = p1->next;
p2 = p2->next;
}
}
while ( p2 ) {
p->next = new node;
p = p->next;
p->next = NULL;
p->expo = p2->expo;
p->coef = p2->coef;
p2 = p2->next;
}
while ( p1 ) {
p->next = new node;
p = p->next;
p->next = NULL;
p->expo = p1->expo;
p->coef = p1->coef;
p1 = p1->next;
}
//cout << head->next;
p = head;
head = head->next;
delete p;
return head;
// if ( head->next ) {
// }else {
// return head;
// }
}

void FreeList(node * p)
{
node * next;
while ( p ) {
next = p->next;
delete p;
p = p->next;
}
}

/*
程序最后的两个细节问题
1- 当加法结果为零时的输出
2- 当有一个k为零时的输出
*/