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
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
| #include <stdio.h>
#include <iostream> // 用于输入输出
//#include <list>//使用list函数库
using namespace std; // c++常规写法
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList; // LinkList是一个单链表（结构体）
// =====================================================(1)创建l1和l2两个表代表两个一元多项式
void CreatList(LinkList *head, LinkList *head2){
*head = NULL; // 初始化表头
*head2 = NULL;
LinkList tail = NULL; // 初始化尾指针
LinkList tail2 = NULL;
int n; // 表长
// 确定两个多项式的每项系数
printf("两个多项式中次数【最高】的项是几次幂？\n");
scanf("%d", &n); // 用最高次数+1确定表长，二次就表长为3
++n;
/*
printf("第二个多项式中次数最高的项是几次？\n");
int m;
scanf("%d", &m);
++m;
if (m > n) n = m; // 比较两个式子长度，取最长的做表长
*/
// 接下来把链表创建起来
printf("请按照【升幂】顺序将多项式的所有系数在下方输入，缺的幂次【用0补全】但不要跳过不写：\n注意常数项是【第0项】，算【第0次幂】。所以你应该先输入常数。\n");
printf("请输入第一个式子的各项系数：\n");
int i;
int tmp;
for (i = 0; i < n; ++i) {
scanf("%d", &tmp); // 传入系数
LNode *newNode = new LNode; // 更新为c++写法
newNode->data=tmp;
newNode->next=NULL;
if(*head == NULL){
*head = newNode; // 第一个节点
tail = newNode; // 初始化尾指针
}else{
tail->next = newNode; // 将新节点添加到链表末尾
tail = newNode; // 更新尾指针
}
}
printf("请输入第二个式子的各项系数：\n");
for(i = 0; i < n; ++i){
scanf("%d", &tmp);
LNode *newNode = new LNode; // 是c++语言的写法
newNode->data = tmp; // 用于传递数据
newNode->next = NULL;
if(*head2 == NULL) {
*head2=newNode; // 第一个节点
tail2 = newNode; // 初始化尾指针
}else{
tail2->next = newNode; // 将新节点添加到链表末尾
tail2 = newNode; // 更新尾指针
}
}
}
// ========================================================(2)打印显示多项式L1和L2和L3之类的等等
void PrintList(LinkList head){ // 需要打印哪个就引用哪个L，后续可以直接输入表名调用输出
LNode *p = head;
int exponent = 0;
bool first = true;
while(p){
if(p->data != 0) {
if(!first) {
if (p->data > 0){
printf(" +"); // 用+把正数项连接起来
}else{
printf(" -"); // 用-把负数项连接起来
}
}else{
if(p->data < 0){
printf("-"); // 第一个负数项前不需要空格
}
}
int absData=abs(p->data); // 取绝对值
if(exponent == 0){
printf("%d", absData);
}else if(exponent == 1){
printf("%dx", absData); // 系数
}else{
printf("%dx^%d", absData, exponent); // 系数和幂次
}
first = false;
}
p = p->next;
exponent++;
}
printf("\n");
}
// ======================================================(3)销毁指定多项式==========case:4
void DestroyList(LinkList *head){ // 销毁需要引用指针地址，吗？
LNode *p = *head;
while(p){
LNode *q = p->next;
delete p;
p = q;
}
*head = NULL;
}
// =================================================================(4)求L1和L2多项式的和
void AddList(LinkList L1, LinkList L2, LinkList *L3){
LNode *p = L1;
LNode *q = L2;
LNode *s = NULL;
*L3 = NULL;
while(p && q){
LNode *newNode = new LNode; // 更新为c++写法
newNode->next = NULL;
if(*L3 == NULL){
*L3 = newNode;
s = newNode;
}else{
s->next = newNode;
s = newNode;
}
// 对应幂次的项进行系数相加
s->data = p->data + q->data;
p = p->next;
q = q->next;
}
// 如果L1还有剩余项
while(p){
LNode *newNode = new LNode; // 更新c++写法
newNode->data = p->data;
newNode->next = NULL;
if(*L3 == NULL) {
*L3 = newNode;
s = newNode;
} else {
s->next = newNode;
s = newNode;
}
p = p->next;
}
// 如果L2还有剩余项
while(q){
LNode *newNode = new LNode; // c++写法
newNode->data = q->data;
newNode->next = NULL;
if(*L3 == NULL){
*L3 = newNode;
s = newNode;
}else{
s->next = newNode;
s = newNode;
}
q = q->next;
}
}
// ===================================================================(5)求两个多项式的差
void SubList(LinkList L1, LinkList L2, LinkList *L3){
LNode *p = L1;
LNode *q = L2;
LNode *s = NULL;
*L3 = NULL;
while(p && q){
LNode *newNode = new LNode; // 更新为c++写法
newNode->next = NULL;
if (*L3 == NULL) {
*L3 = newNode;
s = newNode;
} else {
s->next = newNode;
s = newNode;
}
// 对应幂次的项进行系数相加
s->data = p->data - q->data; //默认L1减去L2
p = p->next;
q = q->next;
}
// 如果L1还有剩余项
while(p){
LNode *newNode = new LNode; // 更新c++写法
newNode->data = p->data;
newNode->next = NULL;
if (*L3 == NULL) {
*L3 = newNode;
s = newNode;
} else {
s->next = newNode;
s = newNode;
}
p = p->next;
}
// 如果L2还有剩余项，需要转化成相反数
while(q){
LNode *newNode = new LNode; // c++写法
newNode->data = -q->data;
newNode->next = NULL;
if (*L3 == NULL) {
*L3 = newNode;
s = newNode;
}else{
s->next = newNode;
s = newNode;
}
q = q->next;
}
}
// =====================================================================(6)求两个多项式的积
void MulList(LinkList L1, LinkList L2, LinkList *L3){
*L3 = NULL;
LNode *s = NULL; // 定义s
// 计算L1和L2的最大幂次
/*
发现用不了ListLength函数，所以只好自己写了
// 使用ListLength函数获取L1和L2的长度
int len1 = ListLength(L1);
int len2 = ListLength(L2);
*/
int len1 = 0, len2 = 0;
LNode *p = L1;
while(p){
len1++;
p = p->next;
}
LNode *q = L2;
while(q){
len2++;
q = q->next;
}
// 最大幂次之和决定结果数组大小
int maxExp = len1 + len2 - 1;
int *result = new int[maxExp](); // 初始化为0
// 创建一个临时数组来存储结果，以使计算方便（。因为不会直接算出来）
// 计算多项式乘积
p = L1;
int exp1 = 0; // exp1是第一个式子里的幂次
while (p) {
q = L2;
int exp2 = 0; // exp2是第二个式子里的幂次
while(q){
result[exp1 + exp2] += p->data * q->data;
//在对应幂次的数组位置上加进去系数的乘积的计算结果
//没有的幂次默认为空
q = q->next;
exp2++;
}
p = p->next;
exp1++;
}
// 将结果数组转换为链表L3
for(int i = 0; i < maxExp; i++) {
// 即使系数为0，也需要保留位置，但不需要输出为链表节点
LNode *newNode = new LNode;
newNode->data = result[i]; // 保存数组中的结果到链表节点中
newNode->next = NULL;
if (*L3 == NULL) {
*L3 = newNode;
s = newNode;
} else {
s->next = newNode;
s = newNode;
}
}
//delete[] result; // 释放数组内存，但是目前会报错
}
int main(){ // ================================================================计算入口
LinkList l1, l2, l3;
printf("程序开始！\n");
while(1){
CreatList(&l1, &l2);
printf("下面显示你刚刚输入的多项式：\n");
PrintList(l1);
PrintList(l2);
printf("正确吗？\n输入1：正确！可以继续操作；\n输入2：重新输入！\n");
int choose1;
scanf("%d", &choose1);
switch(choose1) {
case 1:
// 继续操作，跳出循环
break;
case 2:
DestroyList(&l1);
DestroyList(&l2);
printf("L1和L2销毁成功！请重新输入！\n");
continue; // 重新输入
default:
printf("输入错误，请重新选择！\n");
continue; // 重新输入
}
break; // 跳出while循环
}
while(1){
printf("操作菜单：\n输入你想进行的操作：\n");
printf("输入1：求和\n输入2：求差\n输入3：求积\n输入4：销毁\n输入5：退出\n");
int op;
scanf("%d", &op);
switch (op) {
case 1:
AddList(l1, l2, &l3);
printf("求和结果：\n");
PrintList(l3);
break;
case 2:
SubList(l1, l2, &l3);
printf("求差结果：\n");
PrintList(l3);
break;
case 3:
MulList(l1, l2, &l3);
printf("求积结果：\n");
PrintList(l3);
break;
case 4:
DestroyList(&l1);
DestroyList(&l2);
DestroyList(&l3);
printf("L1、L2和L3销毁成功！\n");
break;
case 5:
printf("程序结束！\n");
return 0;
default:
printf("输入错误！请重新输入！\n");
break;
}
printf("还要做其他操作吗？\n输入1：回到操作菜单\n输入2：退出\n");
int op2;
scanf("%d", &op2);
if (op2 != 1) {
printf("程序结束或操作错误意外退出\n");
break;
}
}
return 0;
}
|