单链表的应用——两个多项式求和
提到多项式想必定会想到其系数和指数，定义数据结构
typedef struct Polynomial{
float coe; // 多项式系数
int exp; //多项式指数
struct Polynomial *next;
}Polynomial,*Linklist;
之所以运用单链表实现该功能是因为会涉及数据的插入与删除等操作，单链表比顺序表灵活、方便。当在进行相加功能操作时，要比较当前指针所指结点的指数大小，如果不相等，就将较小的一个插入到pc所指结点后面，如果相等，就判断所指系数相加是否为零，如果为零就都删除，如果不为零就相加，将结果赋给要插入的结点系数。
void Add(Linklist &La,Linklist &Lb,Linklist &Lc){
Linklist pa,pb,pc,p,q;
pa=La->next;
pb=Lb->next;
pc=Lc=La; //pc和Lc指向La的头结点
while(pa&&pb){
if(pa->exp<pb->exp){
pc->next=pa;
pc=pa;
pa=pa->next;
}
else if(pa->exp>pb->exp){
pc->next=pb;
pc=pb;
pb=pb->next;
}
else if(pa->exp==pb->exp){
if(pa->coe+pb->coe==0){
p=pa;
pa=pa->next;
q=pb;
pb=pb->next;
delete p,q;
}
else{
pa->coe=pa->coe+pb->coe;
q=pb;
pb=pb->next;
delete q;
pc->next=pa;
pc=pa;
pa=pa->next;
}
}
}
pc->next=pa?pa:pb;
}
整体代码用C++实现，如下:
#include<iostream>
using namespace std;
typedef struct Polynomial{
float coe; // 多项式系数
int exp; //多项式指数
struct Polynomial *next;
}Polynomial,*Linklist;
void Create(Linklist &L,int n){ //顺序创建并插入多项式的系数和指数
L=new Polynomial;
L->next=NULL;
Linklist pre,p,s;
for(int i=0;i<n;i++){
s=new Polynomial;
cin>>s->coe>>s->exp;
pre=L;
p=L->next;
while(p&&(p->exp)<(s->exp)){
pre=p;
p=p->next;
}
s->next=p;
pre->next=s;
}
}
void Print(Linklist &L){
Linklist p;
p=L->next;
while(p){
if(p->next&&p->coe!=0){
cout<<p->coe<<'x'<<'^'<<p->exp;
if(p->next->coe<0){
cout<<p->next->coe<<'x'<<'^'<<p->next->exp;
p=p->next;
}
else
cout<<'+';
}
else if(p->next==0)
cout<<p->coe<<'x'<<'^'<<p->exp;
p=p->next;
}
}
void Add(Linklist &La,Linklist &Lb,Linklist &Lc){
Linklist pa,pb,pc,p,q;
pa=La->next;
pb=Lb->next;
pc=Lc=La;
while(pa&&pb){
if(pa->exp<pb->exp){
pc->next=pa;
pc=pa;
pa=pa->next;
}
else if(pa->exp>pb->exp){
pc->next=pb;
pc=pb;
pb=pb->next;
}
else if(pa->exp==pb->exp){
if(pa->coe+pb->coe==0){
p=pa;
pa=pa->next;
q=pb;
pb=pb->next;
delete p,q;
}
else{
pa->coe=pa->coe+pb->coe;
q=pb;
pb=pb->next;
delete q;
pc->next=pa;
pc=pa;
pa=pa->next;
}
}
}
pc->next=pa?pa:pb;
}
int main(){
Linklist L1,L2,L3;
int i;
cout<<"请输入第一个多项式的项数:";
cin>>i;
cout<<"请输入第一个多项式的各项系数和指数(以空格隔开):";
Create(L1,i);
cout<<"请输入第二个多项式的项数:";
cin>>i;
cout<<"请输入第二个多项式的各项系数和指数(以空格隔开):";
Create(L2,i);
cout<<"相加结果为:";
Add(L1,L2,L3);
Print(L3);
return 0;
}
加油，坚持！
