链表实现多项式相加
例如,已知多项式
L
1
L_1
L1,
L
2
L_2
L2如下:
{
L
1
=
4
x
5
+
3
x
4
+
2
x
2
+
x
+
6
L
2
=
6
x
7
+
5
x
4
+
3
x
3
+
7
x
\begin{cases} L_1=4x^5+3x^4+2x^2+x+6 \\ L_2=6x^7+5x^4+3x^3+7x\\ \end{cases}
{L1=4x5+3x4+2x2+x+6L2=6x7+5x4+3x3+7x根据以上条件求二者的和
L
3
=
L
1
+
L
2
L_3=L_1+L_2
L3=L1+L2
数据结构
若用两个定长数组来表示每一项的系数和指数,由于多项式的项数多变,很难确定预分配的空间大小,极易造成空间浪费或者索引越界。故较好的表示方法是用链表。
结构体定义
每个节点包括一个系数域c,一个指数域e和一个指向下一节点的指针域
#include<iostream>
using namespace std;
typedef struct node{
node *next;
int c;
int e;
}node,*List;
链表(多项式)初始化
为链表创建一个头结点,便于表示
void Init(List &L)
{
L=new node;
L->next=NULL;
}
Insert()
插入单个节点(多项式的某一项)
由于每次输入时都是一个节点(多项式的某一项)故将这块代码写了个函数
void Insert(List &L,int c,int e)
{
List s=new node;
s->c=c;
s->e=e;
L->next=s;
s->next=NULL;
L=L->next; //因为采用尾插法,故插入完将指针移至最后一项
}
input()
输入
将输入部分代码包装起来,便于输入多个多项式
注:输入多项式时要降幂输入,得到的结果才是降幂输出
void input(List &L)
{
int c,e;
cout<<"输入系数:"<<endl;
cin>>c;
List p=L;
while(c)
{
cout<<"输入指数:"<<endl;
cin>>e;
Insert(p,c,e);
cout<<"请输入下一项的系数,若输入完毕,请按0回车:";
cin>>c;
}
}
sum()
求和函数
将多项式L1和L2相加得到L3
List sum(List L1,List L2)
{
List L3;
Init(L3);
List p1=L1->next,p2=L2->next,p3=L3;//p1,p2分别指向多项式 L1 和 L2 的首项,p3指向L3中待插入位置的前一项。
while(p1&&p2)
{
if(p1->e==p2->e)
{
Insert(p3,p1->c+p2->c,p1->e);
p1=p1->next;
p2=p2->next;
}
else if( (p1->e) > (p2->e))
{
Insert(p3,p1->c,p1->e);
p1=p1->next;
}
else
{
Insert(p3,p2->c,p2->e);
p2=p2->next;
}
}
while(p2)
{
Insert(p3,p2->c,p2->e);
p2=p2->next;
}
while(p1)
{
Insert(p3,p1->c,p1->e);
p1=p1->next;
}
return L3;
}
print()
输出函数
将链表(多项式)信息输出到屏幕
void print(List L)
{
List p=L->next;
int count=0;
while(p)
{
if (count==0)
cout<<p->c<<"x^"<<p->e;
else
cout<<" + "<<p->c<<"x^"<<p->e;
count++;
p=p->next;
}
cout<<endl;
}
测试代码
int main()
{
List L1;
Init(L1);
cout<<"输入多项式L1:"<<endl;
input(L1);
cout<<"多项式L1为:";
print(L1);
List L2;
Init(L2);
cout<<"输入多项式L2:"<<endl;
input(L2);
cout<<"多项式L2为:";
print(L2);
List L3=sum(L1,L2);
cout<<"多项式L1与多项式L2的和L3为:";
print(L3);
system("pause");
}
测试结果