Posted on 2012-09-23 15:48
hoshelly 閱讀(1158)
評論(1) 編輯 收藏 引用 所屬分類:
DS && Algorithm
2.3x4+3.2x3+2x2+1.2x與5.6x5-2.3x4+3.4x3
相加結(jié)果為：5.6x5+6.6x3 +2x2+1.2x
首先考慮存儲結(jié)構(gòu)，多項式中的每一項包括“系數(shù)”和“指數(shù)”兩項，且相加運算可能會改變系數(shù)和指數(shù)，故應采用鏈式存儲結(jié)構(gòu)。在一個單鏈表結(jié)點中，存儲多項式一項的系數(shù)和指數(shù)。其次，考慮多項式的運算規(guī)則：對于兩個一元多項式中所有指數(shù)相同的項，對應系數(shù)相加，若和不為0，則構(gòu)成“和多項式”中的一項；對于兩個一元多項式中所有指數(shù)不同的項，則分別復抄到“和多項式”中去。
#include <iostream>
using namespace std;
typedef struct{
float coef; //系數(shù)
int expn; //指數(shù)
}DataType;
struct Node;
typedef struct Node *PNode;
struct Node{
DataType info;
PNode link;
};
typedef struct Node *LinkList;
typedef LinkList polynomial; //帶頭結(jié)點的單鏈表表示多項式
int cmp(DataType a,DataType b){
int flag;
if(a.expn<b.expn) flag=-1;
else if(a.expn==b.expn) flag=0;
else flag=1;
return flag;
}
//建立多項式單鏈表
void CreatPolyn(polynomial &P,int m){ //m為多項式項數(shù)
polynomial r,s;
P=new struct Node;
r=P;
for(int i=0;i<m;i++){
s=new struct Node;
cout<<"輸入系數(shù)和指數(shù)：";
cin>>s->info.coef>>s->info.expn;
r->link=s;
r=s;
}
r->link=NULL;
}
//多項式相加得到新的多項式
polynomial AddPolyn(polynomial &pa,polynomial &pb){
polynomial newp,p,q,s,r;
float sum;
p=pa->link;
q=pb->link;
newp=new struct Node;
r=newp;
while(p&&q){
switch(cmp(p->info,q->info)){ //比較兩個多項式的指數(shù)
case -1: //多項式pa當前結(jié)點的指數(shù)值小
s=new struct Node;
s->info.coef=q->info.coef;
s->info.expn=q->info.expn;
r->link=s;
r=s;
q=q->link;
break;
case 0: //兩個多項式指數(shù)值相等
sum=p->info.coef+q->info.coef;
if (sum!=0.0){
s=new struct Node;
s->info.coef=sum;
s->info.expn=p->info.expn;
r->link=s;
r=s;
}
p=p->link;
q=q->link;
break;
case 1: //多項式pb當前結(jié)點的指數(shù)值小
s=new struct Node;
s->info.coef=p->info.coef;
s->info.expn=p->info.expn;
r->link=s;
r=s;
p=p->link;
break;
}//switch
}//while
//鏈接pa剩余結(jié)點
while(p){
s=new struct Node;
s->info.coef=p->info.coef;
s->info.expn=p->info.expn;
r->link=s;
r=s;
p=p->link;
}
//鏈接pb剩余結(jié)點
while(q){
s=new struct Node;
s->info.coef=q->info.coef;
s->info.expn=q->info.expn;
r->link=s;
r=s;
q=q->link;
}
r->link=NULL;
return newp;
}
//輸出多項式單鏈表
void PrintPolyn(polynomial p){
polynomial s;
s=p->link;
while(s){
//輸出系數(shù)和指數(shù)
cout<<s->info.coef<<"("<<s->info.expn<<")";
s=s->link;
}
cout<<endl;
}
void main(){
int m,n;
polynomial p,q;
cout<<"請輸入多項式pa的項數(shù)：";
cin>>m;
CreatPolyn(p,m);
cout<<"請輸入多項式pb的項數(shù)：";
cin>>n;
CreatPolyn(q,n);
PrintPolyn(p);
PrintPolyn(q);
PrintPolyn(AddPolyn(p,q));
}