Posted on 2012-09-23 15:48
hoshelly 阅读(1147)
评论(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));
}