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