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
| #include <stdio.h>
#include <stdlib.h>
/* 构建数据结构来存储多项式 */
typedef struct list {
int coef;
int expon;
struct list *Next;
} *List;
/* 读入函数 */
List Read();
/* 加法操作 */
List Add(List L1, List L2);
/* 乘法操作 */
List Multiplication(List L1, List L2);
/* 输出结果函数 */
void Print(List L);
/* 连接节点函数 */
List Attach(int coef, int expon, List p);
typedef int bool;
#define true 1
#define false -1
List Read() {
int num;
List Head, Pt, prePt; /* 定义头节点，用Pt和prePt结点来创建链表 */
Head = (List) malloc(sizeof(struct list)); /* 为头节点开辟空间 */
if (Head == NULL) { /* 如果Head结点分配的空间为空 */
printf("error!\n");/* 输出错误并退出程序 */
exit(0);
}
Head->Next = NULL; /* 初始化刚开辟的Head结点 */
prePt = Head; /* 将Head的位置赋值为prePt */
scanf("%d", &num); /* 记录输入的多项式数目 */
while (num--) {
Pt = (List) malloc(sizeof(struct list)); /* 创建新的结点来存放多项式 */
if (Pt == NULL) { /* 如果分配的空间为空，则输出错误并退出循环 */
printf("error!\n");
exit(0);
} else {
scanf("%d%d", &Pt->coef, &Pt->expon); /* 将系数和指数读入结点中 */
prePt->Next = Pt; /* 使得Head的Next指向Pt */
prePt = Pt; /* 更新prePt的位置为下一个，来实现尾插法插入多项式结点 */
Pt->Next = NULL; /* 设置新建节点的Next为NULL */
}
}
return Head; /* 最后返回头节点 */
}
/* 实现多项式加法 */
List Add(List L1, List L2) {
int t, sum;
List L, p1, p2, p, Pt;
L = (List) malloc(sizeof(struct list)); /* 创建一个新的链表来存放加法多项式 */
p = L; /* 使用p来对存放加法多项式的链表进行操作 */
p1 = L1->Next, p2 = L2->Next; /* 分别使用p1，p2来对L1，L2进行操作 */
//特殊情况
if (L1 == NULL || L2 == NULL) /* 当输入链表为空时 */
return NULL;
else {
while (p1 && p2) { /* 当一个链表遍历完 */
t = p2->expon - p1->expon; /* 用t来记录两个多项式首项指数的差值 */
if (t > 0) { /* 如果指数差值大于0 */
p = Attach(p2->coef, p2->expon, p); /* 说明p2项的指数大于p1项的指数，将p2放到新的链表L中去 */
p2 = p2->Next; /* 这里存放了一个p2的项，即p2用掉了个一个 */
} else if (t < 0) { /* 反之存放指数大的p1 */
p = Attach(p1->coef, p1->expon, p);
p1 = p1->Next; /* p1用掉了一个 */
} else {
sum = p1->coef + p2->coef;
if (sum == 0) { /* 如果两个指数相等且系数相加等于0，p1,p2都用掉一项 */
p1 = p1->Next; /* 系数和等于0，就不用创造新的节点放在链表L中了 */
p2 = p2->Next;
} else { /* 如果系数和不等于0，则将合成的一项放入链表L中 */
p = Attach(sum, p1->expon, p); /* 若系数和不为0，则将加法结果放到链表L中 */
p1 = p1->Next;
p2 = p2->Next;
}
}
}
}
/* 连接还没有用完的链表 */
while (p1) { /* 假设p1没有用完 */
p = Attach(p1->coef, p1->expon, p); /* 则将剩下的p1放入链表L中 */
p1 = p1->Next; /* 遍历p1剩下的项 */
}
while (p2) { /* 假设p2没有用完 */
p = Attach(p2->coef, p2->expon, p); /* 将设下的p2放入链表L中 */
p2 = p2->Next; /* 遍历p2剩下的项 */
}
return L; /* 返回存放加法结果的链表 L */
}
List Multiplication(List L1, List L2) {
if (L1 == NULL || L2 == NULL) /* 当输入多项式列表为空时 */
return NULL;
int tempcoef, tempexpon; /* 用tempcoef和tempexpon来记录当前结点的计算结果 */
List L, p1, p2, Ptr, TmpCell, Pt;
L = (List) malloc(sizeof(struct list)); /* 创建链表L来存放乘法结果 */
L->Next = NULL; /* 初始化链表L */
p1 = L1->Next; /* p1为L1的第一个结点 */
while (p1) {
p2 = L2->Next; /* 初始化p2为L2的第一个节点 */
Ptr = L; /* 使用Ptr来对链表L进行操作 */
while (p2) {
tempcoef = (p1->coef) * (p2->coef); /* 计算系数乘法结果 */
tempexpon = p1->expon + p2->expon; /* 计算指数乘法结果 */
while (Ptr->Next && Ptr->Next->expon > tempexpon) /* 根据乘法结果的指数来寻找在链表L中的存放位置 */
Ptr = Ptr->Next;
/* 找到位置的下一个节点的指数大于小于等于当前计算出的指数 */
if (Ptr->Next == NULL) /* 如果Ptr的下一个节点为NULL */
Pt = Attach(tempcoef, tempexpon, Ptr); /* 则可以直接将当前乘法结果放入L中 */
else if (Ptr->Next->expon == tempexpon) { /* 如果Ptr下一个结点的指数等于当前计算的指数 */
//系数之后不为0直接改变原结点系数
if (Ptr->Next->coef + tempcoef) /* 将当前计算出的系数加上去如果不等于0 */
Ptr->Next->coef += tempcoef; /* 则修改下一个节点的系数 */
else { /* 如果系数和为0，则删除该节点 */
TmpCell = Ptr->Next;
Ptr->Next = TmpCell->Next;
free(TmpCell);
}
} else { /* 普通情况 */
Pt = (List) malloc(sizeof(struct list)); /* 申请空间 */
Pt->coef = tempcoef; /* 对节点进行初始化 */
Pt->expon = tempexpon;
Pt->Next = Ptr->Next; /* 将节点插入 */
Ptr->Next = Pt;
}
p2 = p2->Next;
}
p1 = p1->Next;
}
return L;
}
/* 输出函数 */
void Print(List L) {
bool flag = false;
List Pt = L->Next;
if (Pt == NULL) /* 如果为空表 */
printf("0 0");
else {
while (Pt) {
/* 实现结束后，不多打一个空格 */
if (flag == false) {
printf("%d %d", Pt->coef, Pt->expon);
Pt = Pt->Next;
flag = true;
} else {
printf(" %d %d", Pt->coef, Pt->expon);
Pt = Pt->Next;
}
}
}
printf("\n");
return;
}
List Attach(int coef, int expon, List p) {
List Pt; /* 使用Pt来操作链表 */
Pt = (List) malloc(sizeof(struct list)); /* 在链表L中创建新的结点 */
Pt->coef = coef;
Pt->expon = expon;
Pt->Next = NULL;
p->Next = Pt; /* 将结点Pt插入链表 */
p = p->Next; /* 更新p的位置来插入后续结点 */
return p; /* 返回更新后p的位置 */
}
int main() {
List Ladd, L1, L2, Lmult;
L1 = Read(); /* 读入多项式1 */
L2 = Read(); /* 读入多项式2 */
Lmult = Multiplication(L1, L2); /* 计算多项式乘法结果 */
Print(Lmult); /* 输出多项式结果 */
Ladd = Add(L1, L2); /* 计算多项式加法结果 */
Print(Ladd); /* 输出多项式加法结果 */
return 0;
}
|