一元多项式的加法与乘法运算#
题意理解#
设计函数分别求两个一元多项式的乘积与和
求解思路#
- 多项式表示
- 程序框架
- 读多项式
- 加法实现
- 乘法实现
- 多项式输出
多项式的表示#
仅表示非零项
数据结构设计#
1
2
3
4
5
6
| typedef struct PolyNode *Polynomial;
struct PolyNode{
int coef;
int expon;
Polynomial link;
};
|
程序框架搭建#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int main(){
读入多项式1
读入多项式2
乘法运算并输出
加法运算并输出
return 0;
}
int main(){
Polynomial P1, P2, PP, PS;
P1 = ReadPoly();
P2 = ReadPoly();
PP = Mult(P1, P2);
PrintPoly(PP);
PS = Add(P1, P2);
PrintPoly(PS);
}
|
需要设计的函数：
如果读入多项式#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| Polynomial ReadPoly(){
Polynomial P, Rear, t;
int c, e, N;
scanf("%d", &N);
P = (Polynomial)malloc(sizeof(struct PolyNode));//链表头空结点
P->link = NULL;
Rear = P;
while (N--){
scanf("%d%d",&c, &e);
Attach(c, e, &Rear);//将当前项插入多项式尾部
}
t = P;
P = P->link;
free(t);//删除临时生成的头结点
return P;
}
|
Rear初值是多少？
两种处理方法：
Rear初值为NULL
在Attach函数中根据Rear是否为NULL做不同处理
Rear指向一个空姐点
1
2
3
4
5
6
7
8
9
| void Attach(int c, int e, Polynomial *pRear){
Polynomial P;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef = c;//对新结点赋值
P->expon = e;
P->link = P;
*pRear = P;//修改*pRear值
}
|
如何将两个多项式相加#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| Polynomial Add(Polynomial P1, Polynomial P2){
t1 = P1;
t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
Rear = P;
while (t1 && t2){
if (t1->expon == t2->expon){
}
else if (t1->expon > t2->expon){
}
else{
}
while (t1){
}
while (t2){
}
}
return P;
}
|
如何将两个多项式相乘#
方法：
- 将乘法运算转换为加法运算
将P1当前项（ci,ei）乘P2多项式，再加到结果多项式里
1
2
3
4
5
6
7
8
| t1 = P1;
t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
Rear = P;
while (t2){
Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);
t2 = t2->link;
}
|
- 逐项插入
将P1当前项（c1i, e1i)乘P2当前项（c2i, e2i），并插入到结果中。并插入到结果中。关键是要找到插入位置
初始结果多项式可由P1第一项乘P2获得
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
| Polynomial Mult(Polynomial P1, Polynomial P2){
Polynomial P, Rear, t1, t2, t;
int c, e;
if (!P1||!P2) return NULL;
t1 = P1;
t2 = P2;
while(t2){//先用P1的第1项乘以P2，得到P
Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);
t2 = t2->link;
}
t1 = t1->link;
while (t1){
t2 = P2;
Rear = P;
while (t2){
e = t1->expon + t2->expon;
c = t1->coef * t2->coef;
while (Rear->link && Rear->link->expon > e)
Rear = Rear->link;
if (Rear->link && Rear->link->expon == e){
if (Rear->link->coef + c)
Rear->link->coef+=c;
else{
t = Rear->link;
Rear->link = t->link;
free(t);
}
}
else{
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = c;
t->expon = e;
t->link = Rear->link;
Rear->link = t;
Rear = Rear->link;
}
t2 = t2->link;
}
t1 = t1->link;
}
t2 = P;P = P->link; free(t2);
}
|
如何将多项式输出#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void PrintPoly(Polynomial P){
//输出多项式
int flat = 0;
if(!P){
printf("0 0\n");return;
}
while(P){
if(!flag)
flag = 1;
else
printf(" ");
}
printf("\n");
}
|