#include <iostream> 
using namespace std; 
typedef struct LNode 
{int coef; //多項式系數(shù) 
int expn; //多項式指數(shù) 
struct LNode *next; 
}LNode,*linklist; 
//---------創(chuàng)建帶頭結(jié)點的多項式鏈表-------- 
linklist creat() 
{ linklist head,s,p,pre; 
int coef; 
int expn; 
head=new LNode; //表頭結(jié)點 
head->next=NULL; 
cout<<"輸入系數(shù)："<<endl; 
cin>>coef; 
cout<<"輸入指數(shù)："<<endl; 
cin>>expn; 
while (coef!=0) 
{ 
cout<<"當(dāng)系數(shù)等于零的時候結(jié)束！"<<endl; 
s=new LNode; //生成新結(jié)點 
s->coef=coef; 
s->expn=expn; 
s->next=NULL; 
pre=head; //插入到有序的多項式鏈表中去 
p=head->next; 
while (p!=NULL && p->expn >s->expn) 
{ 
pre=p; 
p=p->next;//pre 和p分別后移 
} 
s->next=p; 
pre->next=s;//s插入到pre與p之間，生成降序。 
cout<<"讀下一項"<<endl; 
cout<<"輸入系數(shù):"<<endl; 
cin>>coef; 
cout<<"輸入指數(shù):"<<endl; 
cin>>expn; 
} 
return head; 
} 
//-----------輸出多項式鏈表------------- 
void print(linklist head) 
{ linklist p; 
p=head->next; 
while (p) 
{ cout<<p->coef<<"X^"<<p->expn<<"+"; 
p=p->next;//一個一個往下走 
} 
} 
//-------------多項式相加---------------- 
linklist add(linklist pa,linklist pb) 
{linklist p,q,pre,r,y,head; 
int x; 
head=pa; 
p=pa->next; //p,q 指向頭接點的下一個接點，即多項式的第一個接點 
q=pb->next; 
pre=pa; //pre指向p的前驅(qū) 
while((p!=NULL)&&(q!=NULL)) //處理多項式的相加的問題 
{ 
if (p->expn > q->expn) 
{ pre=p; 
p=p->next;//后移 
} 
else if (p->expn==q->expn) 
{ x=p->coef+q->coef; 
if(x!=0) //系數(shù)相加不為0的情況 
{ 
p->coef=x; 
pre=p; 
p=p->next; 
} 
else //系數(shù)相加為0的情況 
{ 
pre->next=p->next; 
delete p; 
p=pre->next; 
} 
r=q; 
q=q->next; 
delete r; 
} 
else //p->expn < q->expn 的情況 
{ 
y=q->next;//q->next保存到y(tǒng) 
q->next=p; 
pre->next=q; 
pre=q; 
q=y; 
} 
} 
if(q!=NULL) 
pre->next=q; 
delete pb; 
return head; 
} 

linklist qufu()//取負(fù)函數(shù) 
{linklist t; 
while(t) 
{t->coef=-t->coef; 
t=t->next; 
} 
return t; 
} 



//----主程序------ 
void main() 
{ 
linklist a,b,c,d; 
cout<<"請輸入第一個多項式："<<endl; 
a=creat(); //創(chuàng)建多項式鏈表a 
cout<<"請輸入第二個多項式："<<endl; 
b=creat(); //創(chuàng)建多項式鏈表b 
cout<<"您輸入的第一個多項式為："<<endl; 
print(a); 
cout<<endl; 
cout<<"您輸入的第二個多項式為："<<endl; 
print(b); 
cout<<endl; 
cout<<"兩多項式相減加后為："<<endl; 
c=add(a,b); //計算多項式a+b 
print(c); 
cout<<endl; 
cout<<"兩多項式相減后為："<<endl; 
b=qufu();//先對b取負(fù)，再相加，相當(dāng)于相減 
d=add(a,b); 
print(d); 
}