Posted on 2012-09-23 15:48
hoshelly 閱讀(1156)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
DS && Algorithm
2.3x4+3.2x3+2x2+1.2x與5.6x5-2.3x4+3.4x3
相加結(jié)果為：5.6x5+6.6x3 +2x2+1.2x
首先考慮存儲(chǔ)結(jié)構(gòu)，多項(xiàng)式中的每一項(xiàng)包括“系數(shù)”和“指數(shù)”兩項(xiàng)，且相加運(yùn)算可能會(huì)改變系數(shù)和指數(shù)，故應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在一個(gè)單鏈表結(jié)點(diǎn)中，存儲(chǔ)多項(xiàng)式一項(xiàng)的系數(shù)和指數(shù)。其次，考慮多項(xiàng)式的運(yùn)算規(guī)則：對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對(duì)應(yīng)系數(shù)相加，若和不為0，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)不同的項(xiàng)，則分別復(fù)抄到“和多項(xiàng)式”中去。
#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é)點(diǎn)的單鏈表表示多項(xiàng)式
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;
}
//建立多項(xiàng)式單鏈表
void CreatPolyn(polynomial &P,int m){ //m為多項(xiàng)式項(xiàng)數(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;
}
//多項(xiàng)式相加得到新的多項(xiàng)式
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)){ //比較兩個(gè)多項(xiàng)式的指數(shù)
case -1: //多項(xiàng)式pa當(dāng)前結(jié)點(diǎn)的指數(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: //兩個(gè)多項(xiàng)式指數(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: //多項(xiàng)式pb當(dāng)前結(jié)點(diǎn)的指數(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é)點(diǎn)
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é)點(diǎn)
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;
}
//輸出多項(xiàng)式單鏈表
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<<"請(qǐng)輸入多項(xiàng)式pa的項(xiàng)數(shù)：";
cin>>m;
CreatPolyn(p,m);
cout<<"請(qǐng)輸入多項(xiàng)式pb的項(xiàng)數(shù)：";
cin>>n;
CreatPolyn(q,n);
PrintPolyn(p);
PrintPolyn(q);
PrintPolyn(AddPolyn(p,q));
}