多项式加法的C语言实现

链表的三个主要例子之一,多项式加法

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
#include <stdio.h>
#include <stdlib.h>

typedef struct Node *PtrToNode;

struct Node {
int Coefficient; // 系数
int Exponent; // 指数
PtrToNode Next;
};

typedef PtrToNode Polynomial; // 多项式

PtrToNode CreatPoly();
void Insert(int Coefficient, int Exponent, Polynomial Poly);
Polynomial AddPoly(Polynomial Polya, Polynomial Polyb);

Polynomial CreatPoly() {
PtrToNode head = (PtrToNode)malloc(sizeof(struct Node));
head->Next = NULL;
int Coefficient, Exponent;
// 输入为系数指数,以-1结束
while(~scanf("%d", &Coefficient) && Coefficient != -1) {
scanf("%d", &Exponent);
Insert(Coefficient, Exponent, head);
}
return head;
}

Polynomial AddPoly(Polynomial Polya, Polynomial Polyb) {
PtrToNode head = (PtrToNode)malloc(sizeof(struct Node));
head->Next = NULL;
int Coefficient, Exponent;
PtrToNode p;
p = Polya->Next;
while (p != NULL) {
Insert(p->Coefficient, p->Exponent, head);
p = p->Next;
}
p = Polyb->Next;
while (p != NULL) {
Insert(p->Coefficient, p->Exponent, head);
p = p->Next;
}
return head;
}

void Insert(int Coefficient, int Exponent, Polynomial Poly) {
PtrToNode p;
p = Poly;

// 注意判断是不是空链表,即第一个插入的元素
while (p->Next != NULL && p->Next->Exponent > Exponent) {
p = p->Next;
}

if(p->Next != NULL && p->Next->Exponent == Exponent) {
p->Next->Coefficient += Coefficient;
}
else {
PtrToNode node = (PtrToNode)malloc(sizeof(struct Node));
node->Coefficient = Coefficient;
node->Exponent = Exponent;
node->Next = p->Next;
p->Next = node;
}
}

void PrintPoly(Polynomial Poly) {
PtrToNode p;
p = Poly->Next;
while (p != NULL) {
printf("%dx^%d", p->Coefficient, p->Exponent);
if(p->Next != NULL)
printf(" + ");
p = p->Next;
}
printf("\n");
}

int main() {
Polynomial polya = CreatPoly();
PrintPoly(polya);
Polynomial polyb = CreatPoly();
PrintPoly(polyb);
Polynomial polyc = AddPoly(polya, polyb);
PrintPoly(polyc);
return 0;
}