实验一_一元稀疏多项式的表示及加法运算.doc

实验一 一元稀疏多项式的表示及加法运算一、 需求分析1. 程序的功能:l 多项式以指数递增的顺序输入。l 设计的数据结构应有利于表示任意一元稀释多项式。l 输出原始多项式及运算结果。l 附加功能：乱序输入计算表达式结果2. 输入输出要求：l 多项式以指数递增的方式输入l 输出原始多项式及其结果3. 测试数据(1) , (2)0 , (3) , -1附加功能测试数据：(4) ,二、 概要设计l 所用数据结构定义：struct Term/多项式结点的定义float coef;/系数int exp;/指数Term * link;Term(float c,int e,Term * next=NULL)coef=c;exp=e;link=next;Term *InsertAfter(float c,int e);Term & operator -=(Term & t)if(t.exp=exp) coef-=t.coef;return *this;Term & operator +=(Term & t)if(t.exp=exp) coef+=t.coef;return *this;friend ostream & operatorlink=first;/必须链成环Polynomal()makeEmpty();Polynomal(Polynomal & R);/复制构造函数Polynomal & operator=(const Polynomal & R);/重载复制赋值操作符 void insert(float c,int e,Polynomal& R);/对于二项式进行插入排序 Polynomal sort();/对于多项式进行排序Term * getHead() constreturn first;void makeEmpty();private:Term * first;friend ostream & operator(istream &,Polynomal&);friend Polynomal operator+(Polynomal&,Polynomal&);l 主程序的流程及各模块之间的层次关系：1) 主程序流程2) 模块之间层次关系三、 详细设计1、插入一个结点Term* Term:InsertAfter(float c,int e)/在当前由this指针指示的项(即调用此函数的对象)后面插入一个新项link=new Term(c,e,link);/创建一个新结点，自动链接return link;/插入到this结点后面2、重载各运算符（1）Polynomal & Polynomal:operator =(const Polynomal & R) makeEmpty();/先清空 first=new Term(0,-1); Term *destptr=first,*srcptr=R.first-link; while(srcptr!=R.first)destptr-InsertAfter(srcptr-coef,srcptr-exp);srcptr=srcptr-link;destptr=destptr-link; destptr-link=first;/必须链成环 return *this;#伪代码清空；动态创建节点first；创建节点指针*destptr指向first，创建节点指针*srcptr指向R.first-link；WHILE（R链未遍历结束） 将R链表中的结点一次插入到first之后；ENDWHILE将*destptr连成环；结束（2）istream& operator(istream& in,Polynomal& x)Term *rear=x.first;int e;float c;/定义尾指针rearwhile(1)cout输入：系数,指数（以、-1结束）:ce;if(c=0&e=-1)break;/用e小于控制输入结束rear=rear-InsertAfter(c,e);/链接到rear所指结点后return in;（3）ostream & operatorlink;coutThe polynomal is:coef0.0)outcoef=0)outlink;elseout*current;/调用term类的重载操作link;outlink；设置标志位hWHILE IF 打印符号+； 改变标志位； ELSE 打印该节点； 指向下一个节点；ENDIFENDWHILE（4）Polynomal operator+(Polynomal& A,Polynomal& B)Term *pa,*pb,*pc,*p,*last;float temp;Polynomal C;pc=C.first;pa=A.first-link;pb=B.first-link;while(pa!=A.first &pb!=B.first)/两两比较if(pa-exp=pb-exp)/对应项指数相等temp=pa-coef+pb-coef;/系数相加if(fabs(temp)!=0)pc=pc-InsertAfter(temp,pa-exp);pa=pa-link ;pb=pb-link;else if(pa-expexp)pc=pc-InsertAfter(pa-coef,pa-exp);/pa指数小 pa=pa-link;elsepc=pc-InsertAfter (pb-coef,pb-exp);pb=pb-link;/pb指数小，加入ah链if(pa!=A.first)p=pa;last=A.first;elsep=pb;last=B.first;while(p!=last)pc=pc-InsertAfter (p-coef,p-exp );p=p-link;return C;#伪代码*Pa=二项式a的当前节点;*pb=二项式b的当前节点;新建二项式c；WHILE IF IF 系数相加后将插入节点到c尾部； ENDIF 比较a,b的下一个节点 ELSEIF 将pa的当前节点复制到c尾部； Pa后移； ELSE 将Pb的当前节点复制到c尾部； Pb后移； ENDIFENDWHILEIF 将未遍历空的那一个所在的二项式剩余部分复制到c尾部；ENDIF返回合成多项式3、排序算法（1）Polynomal Polynomal:sort()Polynomal R; Term *p=first; p=p-link; while(p!=first)insert(p-coef,p-exp,R);p=p-link; return R;（2）void Polynomal:insert(float c, int e, Polynomal &R)Term *q=R.first,*p=R.first-link, *r;if(p=R.first) q-link=new Term(c,e);/c为空q-link-link=R.first;elsewhile(p!=R.first) if(p-exp=e)/指数相等p-coef+=c;if(p-coef!=0)break;if(p-coef=0)q-link=p-link;r=p;p=p-link;delete r;break;else if(p-expe)/e小于当前结点的指数q-link=new Term(c,e);q=q-link;q-link=p;break;elsep=p-link;q=q-link;if (p=R.first) /e大于R中每一项的指数，插在表尾q-link=new Term(c,e);q-link-link=p;四、 调试分析1、调试中的问题（1）在测试数据一时，出现带有常数项的多项式，常数项被构造为一次项，例如多项式被输出为解决办法：在重载运算符+中，当pa的指数小时，将程序由pc=pc-InsertAfter (pa-coef,pb-exp);pb=pb-link;改为pc=pc-InsertAfter (pb-coef,pb-exp);pb=pb-link;即可；（2）在调试问题二的过程中，出现的0被程序自动忽略，不能打印使得输出结果为解决办法：在重载输出运算符的程序模块中添加：if(current-coef=0)outlink;即可保证程序的输出正常，但是是以作为输出的。（3）由于程序的数据结构构造成一种环形链表，因而在编程侧时候比单链表更易出错，采取画图的方式容易解决问题。2、分析算法的时间复杂度和空间复杂度本实验所涉及算法基本采用顺序遍历方式，因而时间复杂度为o(m+n)，空间复杂度为o(m+n)。五、 使用说明及测试结果按照程序提示，依次输入多项式的各项，系数与指数以Enter隔开，整个多项式输入以0、-1结束。如下图所示：1、测试数据一2、测试数据二3、测试数据三4、测试数据四六、 源程序带注释#include#includeusing namespace std;struct Term/多项式结点的定义float coef;/系数int exp;/指数Term * link;Term(float c,int e,Term * next=NULL)coef=c;exp=e;link=next;Term *InsertAfter(float c,int e);Term & operator -=(Term & t)if(t.exp=exp) coef-=t.coef;return *this;Term & operator +=(Term & t)if(t.exp=exp) coef+=t.coef;return *this;friend ostream & operatorlink=first;/必须链成环Polynomal()makeEmpty();Polynomal(Polynomal & R);/复制构造函数Polynomal & operator=(const Polynomal & R);/重载复制赋值操作符 void insert(float c,int e,Polynomal& R);/对于二项式进行插入排序 Polynomal sort();/对于多项式进行排序Term * getHead() constreturn first;void makeEmpty();private:Term * first;friend ostream & operator(istream &,Polynomal&);friend Polynomal operator+(Polynomal&,Polynomal&);Term* Term:InsertAfter(float c,int e)/在当前由this指针指示的项(即调用此函数的对象)后面插入一个新项link=new Term(c,e,link);/创建一个新结点，自动链接return link;/插入到this结点后面ostream& operator(ostream& out,const Term& x)/Term的友元函数：输出一个项X的内容到输出流out中if(x.coef=0.0) return out;/0系数项不输出outx.coef;switch(x.exp)case 0:break;case 1:outX;break;default:outXlink, *r;if(p=R.first) q-link=new Term(c,e);/c为空q-link-link=R.first;elsewhile(p!=R.first) if(p-exp=e)/指数相等p-coef+=c;if(p-coef!=0)break;if(p-coef=0)q-link=p-link;r=p;p=p-link;delete r;break;else if(p-expe)/e小于当前结点的指数q-link=new Term(c,e);q=q-link;q-link=p;break;elsep=p-link;q=q-link;if (p=R.first) /e大于R中每一项的指数，插在表尾q-link=new Term(c,e);q-link-link=p;Polynomal Polynomal:sort()Polynomal R;Term *p=first;p=p-link;while(p!=first)insert(p-coef,p-exp,R);p=p-link;return R;Polynomal:Polynomal(Polynomal& R)/复制构造函数：用已有多项式初始化当前多项式对象first=new Term(0,-1);Term *destptr=first,*srcptr=R.first-link;while(srcptr!=R.first)destptr-InsertAfter(srcptr-coef,srcptr-exp);/在destptr所指结点后插入一新结点，再让destptr指到这个新结点srcptr=srcptr-link;destptr=destptr-link;destptr-link=first;/必须链成环Polynomal & Polynomal:operator =(const Polynomal & R)makeEmpty();/先清空first=new Term(0,-1);Term *destptr=first,*srcptr=R.first-link;while(srcptr!=R.first)destptr-InsertAfter(srcptr-coef,srcptr-exp);srcptr=srcptr-link;destptr=destptr-link;destptr-link=first;/必须链成环return *this;void Polynomal:makeEmpty()Term *q;while(first-link!=first)q=first-link;first-link=q-link;delete q;istream& operator(istream& in,Polynomal& x)Term *rear=x.first;int e;float c;/定义尾指针rearwhile(1)cout输入：系数,指数（以、-1结束）:ce;if(c=0&e=-1)break;/用e小于控制输入结束rear=rear-InsertAfter(c,e);/链接到rear所指结点后return in;ostream & operatorlink;coutThe polynomal is:coef0.0)outcoef=0)outlink;elseout*current;/调用term类的重载操作link