数据结构（二）线性结构 —— 编程作业 02 ：一元多项式的乘法与加法运算_设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出

数据结构系列内容的学习目录$\to$浙大版数据结构学习系列内容汇总。

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

  输入格式： 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。
        数字间以空格分隔。

  输出格式： 输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。
        数字间以空格分隔，但结尾不能有多余空格。
        零多项式应输出0 0。

  输入样例：

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
1
2

  解题思路： 见数据结构（二）—— 线性结构（4）：应用实例的4.2节（一元多项式的加法与乘法运算）。

  代码实现：

#include<iostream> 
using namespace std;

typedef struct PolyNode {
	int coef;//系数 
	int exp;//指数 
	struct PolyNode *next;
} *Polynomial;

Polynomial read(Polynomial P);
void print(Polynomial P);
Polynomial getMuti(Polynomial P1, Polynomial P2);
Polynomial getAdd(Polynomial P1, Polynomial P2);

Polynomial read(Polynomial P)
{
	Polynomial s = NULL, temp;
	P = (struct PolyNode*)malloc(sizeof(struct PolyNode));
	temp = P;
	int n, COEF, EXP;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> COEF >> EXP;
		if (COEF != 0)
		{
			s = (struct PolyNode *)malloc(sizeof(struct PolyNode));
			s->coef = COEF;
			s->exp = EXP;
			P->next = s;
			P = s;
		}
	}
	P->next = NULL;
	return temp;
}

void print(Polynomial P)
{
	int num = 0, temp = 0;  //temp用于统计P里面有多少个元素，num 用于统计有多少个系数为0的数 
	Polynomial val = P;
	while (val->next)
	{
		val = val->next;
		temp++;
	}
	if (P->next != NULL)
	{
		while (P->next)
		{
			if (P->next->coef != 0)
			{
				cout << P->next->coef << " " << P->next->exp;
				Polynomial val = P->next;
				while (val->next&&val->next->coef == 0)
				{
					val = val->next;
				}
				if (val->next == NULL)
					cout << endl;
				else
					cout << " ";
			}
			else
				num++;
			P = P->next;
		}
		if (num == temp)
			cout << 0 << " " << 0 << endl;
	}
	else
		cout << 0 << " " << 0 << endl;
}

Polynomial getAdd(Polynomial P1, Polynomial P2)
{
	Polynomial P, temp = NULL, s = NULL;
	P = (struct PolyNode *)malloc(sizeof(struct PolyNode));
	temp = P;

	while (P1->next&&P2->next)
	{
		if (P1->next->exp > P2->next->exp)
		{
			s = (struct PolyNode *)malloc(sizeof(struct PolyNode));
			s->coef = P1->next->coef;
			s->exp = P1->next->exp;
			P->next = s;
			P = s;
			P1 = P1->next;
		}
		else if (P1->next->exp < P2->next->exp)
		{
			s = (struct PolyNode *)malloc(sizeof(struct PolyNode));
			s->coef = P2->next->coef;
			s->exp = P2->next->exp;
			P->next = s;
			P = s;
			P2 = P2->next;
		}
		else
		{
			s = (struct PolyNode *)malloc(sizeof(struct PolyNode));
			s->coef = P2->next->coef + P1->next->coef;
			s->exp = P2->next->exp;
			P->next = s;
			P = s;
			P1 = P1->next;
			P2 = P2->next;
		}
	}
	if (P1->next)
		P->next = P1->next;
	else
		P->next = P2->next;
	return temp;
}

Polynomial getMuti(Polynomial P1, Polynomial P2) {
	/*
	在这里我们采用的是：逐项插入。
	1，先拿出P2的第一项，让它与P1的每一项相乘，从而得到P
	2，再拿出P2的第二项，让它与P1的每一项相乘，每乘一项，就将其插入到P中
	3，依次重复上面的步骤，最终得到P，将其打印出来
	*/
	Polynomial P, temp = NULL, s = NULL;
	P = (struct PolyNode *)malloc(sizeof(struct PolyNode));
	temp = P;
	Polynomial Pa = P1;

	//拿出P2的第一项，让它与P1的每一项相乘,从而得到P
	while (Pa->next) {
		s = (struct PolyNode *)malloc(sizeof(struct PolyNode));
		s->coef = Pa->next->coef * P2->next->coef;  //P1的每一项与P2的第一项的系数相乘
		s->exp = Pa->next->exp + P2->next->exp;  //P1的每一项与P2的第一项的指数相加
		P->next = s;
		P = s;
		Pa = Pa->next;
	}
	P->next = NULL;
	P = temp;
	Polynomial Pb = P2->next;  //再拿出P2的第二项，让它与P1的每一项相乘，每乘一项，就将其插入到P中
	while (Pb&&Pb->next)
	{
		Pa = P1;
		while (Pa->next)
		{
			s = (struct PolyNode *)malloc(sizeof(struct PolyNode));
			s->coef = Pa->next->coef * Pb->next->coef;
			s->exp = Pa->next->exp + Pb->next->exp;
			while (P->next)  //将刚相乘的一项插入到P中
			{
				if (s->exp > P->next->exp)
				{
					Polynomial val = P->next;
					P->next = s;
					s->next = val;
					break;
				}
				else if (s->exp == P->next->exp)
				{
					P->next->coef += s->coef;
					break;
				}
				P = P->next;
			}
			if (P->next == NULL)
			{
				P->next = s;
				s->next = NULL;
			}
			P = temp;
			Pa = Pa->next;  //拿出P1的下一项
		}
		Pb = Pb->next;  //拿出P2的下一项
	}
	return temp;
}

int main()
{
	Polynomial P1 = NULL;
	Polynomial P2 = NULL;
	Polynomial P = NULL;

	P1 = read(P1);
	P2 = read(P2);

	P = getMuti(P1, P2);
	print(P);

	P = getAdd(P1, P2);
	print(P);

	system("pause");
	return 0;
}
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

  测试： 输入样例的测试效果如下图所示。