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

发表于 更新于 阅读次数： 本文字数： 4.4k 阅读时长 ≈ 4 分钟

7-2 一元多项式的乘法与加法运算
https://pintia.cn/problem-sets/15/problems/710

首先大致思路是做好输入输出之后，先做加法（一是比乘法简单，二是后面乘法也会用到加法）再做乘法。
加法：加法的过程其实和上一道题”两个有序链表的合并“非常相似，只不过这里的合并是按照系数和指数来进行的。上一题的一些坑这里也都有，因为遇到过，也比较容易避开。
乘法：实现了加法之后，乘法其实比较容易。将两个多项式A、B相乘的结果拆分为把多项式A中各项（a,b,c,…）和多项式B相乘的结果 累加。其中一个项a和一个多项式B相乘的结果拆分为一个项a和多项式B中各项（x,y,z,…）相乘的结果 累加。最后再分成一个项a和一个项x的乘积。反过来再利用已实现的多项式加法函数进行累加即可（把一个项视作只有一项的多项式）。

零多项式的来源：

  1. 输入了零多项式 （题目已经说明了只会输入非零多项式）
  2. 运算（ 加法/乘法）得到零多项式

坑：

  1. 零多项式
    不管是输入了零多项式，还是运算（ 加法/乘法）得到零多项式，最终只要在输出函数中进行判断就可以。因此引入了tag变量，tag为true时，没有输出过非零项，说明目前为止num是零多项式。
  2. 可能必须先做乘法才能做加法，视加法的实现细节而定。
    我的代码中多项式加法的结果并不是创建了一个新的链表，而是将原来的两个链表拆开重组而成的，这样会改变原来两个多项式，所以一定要先做乘法（乘法是创建一个新的链表作为结果）。
  3. 格式问题
    因为有零多项式和系数为0的项的存在，再加上题目对格式（回车、空格）有要求，所以比较容易出错。

格式问题：解决方法是加入printed变量，用于控制

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
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#include <stdio.h>
#include <string.h>
#include<stdlib.h>
typedef struct Node node;
typedef struct Node* ptr;

struct Node
{
	int coe;
	int log;
	ptr next;
};

void print(ptr num);

//功能：根据输入，创建多项式链表，返回头指针
ptr createNode() {
	ptr num = NULL, now = NULL;
	int a;
	scanf("%d", &a);
	for (int i = 0; i < a; i++)
	{
		ptr temp = (ptr)malloc(sizeof(node));
		scanf("%d", &temp->coe);
		scanf("%d", &temp->log);
		temp->next = NULL;

		if (num == NULL)
		{
			num = temp;
			now = temp;
		}
		else
		{
			now->next = temp;
			now = now->next;
		}
	}
	return num;
}

//功能：将两个多项式相加

ptr numPlus(ptr poly1,ptr poly2) {
	ptr resPlus = NULL, now = NULL;
	while (poly1!=NULL && poly2!=NULL)
	{
		if (poly1->log < poly2->log)   //把2放到resPlus后面
		{
			if(resPlus == NULL)
			{
				resPlus = poly2;
				now = poly2;
			}
			else
			{
				now->next = poly2;
				now = now->next;
			}
			
			poly2 = poly2->next;
			now->next = NULL;
		}
		else if (poly1->log > poly2->log)  ////把1放到resPlus后面
		{
			if (resPlus == NULL)
			{
				resPlus = poly1;
				now = poly1;
			}
			else
			{
				now->next = poly1;
				now = now->next;
			}

			poly1 = poly1->next;
			now->next = NULL;
		}
		else   //幂相等：系数相加后，放到resPlus后面
		{
			if (resPlus == NULL)
			{
				poly1->coe += poly2->coe;
				resPlus = poly1;
				now = poly1;
			}
			else
			{
				poly1->coe += poly2->coe;
				now->next = poly1;
				now = now->next;
			}
			
			poly1 = poly1->next;

			//后移poly2后，释放空间
			ptr temp = poly2;
			poly2 = poly2->next;
			free(temp);

			now->next = NULL;
		}
	}

	//执行到这里，说明至少有一个为空
	if (poly1 != NULL )
	{
		if (resPlus == NULL)
		{
			resPlus = poly1;
			now = poly1;
		}
		else
		{
			now->next = poly1;
		}
	}
	else if (poly2 != NULL)
	{
		if (resPlus == NULL)
		{
			resPlus = poly2;
			now = poly2;
		}
		else   
		{
			now->next = poly2;
		}
	}
	//全都为空时不会处理

	return resPlus;
}

//功能：将两个数相乘，返回指向结果节点的指针 
ptr multiNums(ptr num1, ptr num2) {
	ptr now = (ptr)malloc(sizeof(node));
	now->coe = num1->coe * num2->coe;
	now->log = num1->log + num2->log;
	now->next = NULL;
	return now;
}

//功能:将数字num和多项式poly相乘，返回指向结果节点的指针 
ptr multiNumAndPoly(ptr num, ptr poly) {
	//数字num和多项式poly中每个数字的积的和
	ptr res =NULL;

	while (poly)
	{
		//temp:数字num和多项式poly中当前数字相乘的结果
		ptr temp = multiNums(num, poly);
		//将temp临时结果和res相加
		if (res == NULL)
			res = temp;
		else
			res = numPlus(res, temp);

		poly = poly->next;
	}
	//printf("%d %d:\n", num->coe, num->log);
	//print(res);
	return res;
}


//功能：将两个多项式相乘，返回指向结果节点的指针 
ptr numMulti (ptr poly1, ptr poly2) {
	ptr res = NULL;

	while (poly1)
	{
		//每次让num1指向的数字和多项式num2相乘
		ptr temp = multiNumAndPoly(poly1, poly2);
		if (res == NULL)
			res = temp;
		else
			res = numPlus(res, temp);

		poly1 = poly1->next;
	}
	return res;
}

//功能：输出多项式num
void print(ptr num) {
	//tag为true时，没有输出过非零项，说明目前为止num是零多项式
	int tag = 1;
	//printed=1表示输出过内容
	int printed = 0;

	if (num) {
		if (num->coe!= 0)
		{
			printf("%d %d", num->coe, num->log);
			tag = 0;
			printed = 1;
		}
		while (num->next != NULL)
		{
			num = num->next;
			if (num->coe != 0)
			{
				if (printed)
					printf(" ");
				printf("%d %d", num->coe, num->log);
				tag = 0;
			}
		}
		if (printed)
		{
			printf("\n");
		}

	}
	if (tag)
	{
		printf("0 0\n");

	}
}




int main()
{
	ptr num1 = createNode();
	ptr num2 = createNode();
	ptr resMulti = numMulti(num1, num2);
	ptr resPlus = numPlus(num1,num2);

	print(resMulti);
	print(resPlus);

	return 0;
}