多项式相加，链表

93 阅读 0 评论 62 点赞

我是靠谱客的博主义气高山，这篇文章主要介绍多项式相加，链表，现在分享给大家，希望可以做个参考。

一条单链表可以表示一个一元多项式，每个节点包含三个域：指数、系数和后继节点（指针或引用）。
表示多项式3X4-6X2+5X-10的单链表如图所示。给定两个多项式，实现两个多项式相加算法。

输入格式

第一行输入包含两个整数m,n
后续为m行和n行数据
m，n分别代表两个多项式的项数
后续每一行代表多项式的项，包含a,b两个数据，表示该项的系数和指数。

输出格式

从较高指数到较低指数，依次输出求得的和。
每行一项，格式与输入相同，但无需输出项数，系数为0的项也不输出。

输入样例 复制

2 3

1 2

1 1

2 2

1 1

2 0

输出样例 复制

3 2

2 1

2 0

复制代码

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode
{
int coef, expn;
struct LNode* next;
}LNode, * LinkList;
LinkList ListInsert(int n)
{
LinkList head, p, q, pre, tail;
head = new LNode;
head->next = NULL;
tail = head;
for (int i = 0; i < n; i++)
{
p = new LNode;
cin >> p->coef >> p->expn;
pre = head;
q = head->next;
while (q && q->expn > p->expn)
{
pre = q;
q = q->next;
}
p->next = q;
pre->next = p;
}
return head;
}
void Add(LinkList heada, LinkList headb)
{
int sum;
LinkList pa, pb, pc, r;
pa = heada->next;
pb = headb->next;
pc = heada;
while (pa && pb)
{
if (pa->expn == pb->expn)
{
sum = pa->coef + pb->coef;
if (sum != 0)
{
pa->coef = sum;
pc->next = pa; pc = pa;
pa = pa->next;
r = pb; pb = pb->next; delete r;
}
else
{
r = pa; pa = pa->next; delete r;
r = pb; pb = pb->next; delete r;
}
}
else if (pa->expn < pb->expn)
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
else
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
}
pc->next = pa ? pa : pb;
}
void print(LinkList head)
{
LinkList p;
p = head->next;
while (p != NULL)
{
cout << p->coef << " " << p->expn << endl;
p = p->next;
}
}
int main()
{
LinkList heada, headb;
int m, n;
cin >> m >> n;
heada = ListInsert(m);
headb = ListInsert(n);
Add(heada, headb);
print(heada);
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
#include<bits/stdc++.h>
using namespace std;
typedef struct LNode
{
int coef, expn;
struct LNode* next;
}LNode, * LinkList;
LinkList ListInsert(int n)
{
LinkList head, p, q, pre, tail;
head = new LNode;
head->next = NULL;
tail = head;
for (int i = 0; i < n; i++)
{
p = new LNode;
cin >> p->coef >> p->expn;
pre = head;
q = head->next;
while (q && q->expn > p->expn)
{
pre = q;
q = q->next;
}
p->next = q;
pre->next = p;
}
return head;
}
void Add(LinkList heada, LinkList headb)
{
int sum;
LinkList pa, pb, pc, r;
pa = heada->next;
pb = headb->next;
pc = heada;
while (pa && pb)
{
if (pa->expn == pb->expn)
{
sum = pa->coef + pb->coef;
if (sum != 0)
{
pa->coef = sum;
pc->next = pa; pc = pa;
pa = pa->next;
r = pb; pb = pb->next; delete r;
}
else
{
r = pa; pa = pa->next; delete r;
r = pb; pb = pb->next; delete r;
}
}
else if (pa->expn < pb->expn)
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
else
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
}
pc->next = pa ? pa : pb;
}
void print(LinkList head)
{
LinkList p;
p = head->next;
while (p != NULL)
{
cout << p->coef << " " << p->expn << endl;
p = p->next;
}
}
int main()
{
LinkList heada, headb;
int m, n;
cin >> m >> n;
heada = ListInsert(m);
headb = ListInsert(n);
Add(heada, headb);
print(heada);
return 0;
}