多项式相加，链表

一条单链表可以表示一个一元多项式，每个节点包含三个域：指数、系数和后继节点（指针或引用）。
表示多项式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;
}

最后

以上就是义气高山为你收集整理的多项式相加，链表的全部内容，希望文章能够帮你解决多项式相加，链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。