《实验一_一元稀疏多项式的表示及加法运算.doc》由会员分享，可在线阅读，更多相关《实验一_一元稀疏多项式的表示及加法运算.doc（17页珍藏版）》请在三一文库上搜索。
1、实验一 一元稀疏多项式的表示及加法运算需求分析1.程序的功能:多项式以指数递增的顺序输入。设计的数据结构应有利于表示任意一元稀释多项式。输出原始多项式及运算结果。附加功能：舌力;输入汁算表达式结果2.输入输出要求:多项式以指数递增的方式输入输出原始多项式及其结果3.测试数据(1)7 + 3x + 9x8+5x178x +22x7-9x8(3) 8x,0+22x7-9x8-1附加功能测试数据:概要设计所用数据结构定义：/多项式结点的左义/系数/指数(4) 8x5 + 6x3 一 7x6 一 2a-5 , -8x2-x6struct Termfloat coef;int exp;Term * li
2、nk;Term(float c,int e, Term * next=NULL)coef=c;exp=e;link=next;Term *1nsertAfter(float c,int e);Term & operator -=(Term & t)if=exp) coef-=;return *this;Term & operator +=(Term & t) if二二exp) coef+=;return *this;friend ostream & opegtor< (ostream &, const Tern>&);clas
3、s Polynomal public：/多项式的类泄义Polynomal0 构造函数，建立空链表first二new Term(0, T);f ir st-> 1 ink=f ir s t;/必须链成环Polynomal () makeEmpty 0 ;Polynomal (Polynomal & R) ;/复制构造函数Polynomal & operator= (const Polynomal & R); /重载复制賦值操作符 void insert (float c, int e, Polynomalft R): /对于二项式进行插入排序 Polynomal s
4、ort0 ;/对于多项式进行排序Term * getHeadO constreturn first;void makeEmpty0 ;private:Term * first;friend ostream & opewtor<(ostream &, const Polynomal&);friend istream & ope wto:r>> (i stream &, Poly noma 1&);friend Polynomal operator+(Polynomal&, Polynoma1&);； 主程序的流程及
5、各模块之间的层次关系:1）主程序流程三、详细设计1、插入一个结点Term* Term:：InsertAfter(float c, int e)在当前由this指针指示的项(即调用此函数的对象)后面插入一个新项link二new Term(c, e, link) ;/创建一个新结点,自动链接return 1 ink;7插入到thi s结点后而2、重载各运算符(1) Polynomal & Polynomal:operator =(const Polynomal & R) makeEmpty ();/先淸空first=new Term(0, -1);Term *destptr=fir
6、st, *srcptr=>link;while (srcptr! = destptr->InsertAfter(srcptr->coef, srcptr->exp);srcptr=srcptr->link; destptr=destptr->link;des tptr-> 1 ink=f ir s t;/必须链成环return *this;#伪代码清空；动态创建节点first；创建节点指针*destptr指向first,创建节点指针*srcptr指向>link；WHILE (R链未遍历结束)将R链表中的结点一次插入到first之后；ENDWHIL
7、E将*destptr连成环；结束(2 ) istream& operator» (istream& in, Polynomal& x) Term *rear=; int e;float c; /定义尾指针rear while(1) cout<<"输入：系数，指数(以、T结束):*«endl;in»c»e;if (c=0&&e=-l) break;/用e小于控制输入结束rear=rear->InsertAfter(c, e);'链接到:rear所指结点后return in;(3 )
8、 ostream & operator« (ostream& out, const Polynomal & x) 八输出到附加头结点的多项式链表xTerm *current=>link;cout«"The polynomal is: *<<endl: bool h=true;while(current!=if (,h=false&¤t->coef >out«"+"h=false;if (current">coef=0) out<&l
9、t;0;current=current->link;elseout«*current;/调用term类的重载操作current=current->link;out<<endl;return out:#伪代码创建指针*current指向当前节点link： 设置标志位hWILE遍历多项式IF标志位h为假，当前指向节点指数为0 打印符号+;改变标志位；ELSE打印该节点；指向下一个节点；ENDIFENDWHILE(4 ) Polynomal operator-*- (Polynoma 1& A, Polynomal& B) Term *pa,*pb,
10、*pc, *p, *last;float temp;Polynomal C;pa=>link;pb=>link;while(pa!= &&pb!=/两两比较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">exp<pb">exp) pc=pc-&g
11、t;InsertAfter (pa">coef, pa->exp):/ pa#彳数小pa=pa">link;elsepc=pc">InsertAfter (pb">coef, pb">exp);pb=pb->link;pb指数小,加入ahif(pa!=tp=pa;last=;else p=pb;last=;while(p!=last)pc=pc>InsertAfter (p->coef,p->exp );p=p*>link;return C;#伪代码*Pa二二项式a的当前节点;杠
12、2二项式b的当前节点； 新建二项式c；WHILE遍历二项式IF<pa, pb的指数相等IF指数之和不为0>系数相加后将插入节点到c尾部；ENDIF比较a, b的下一个节点ELSEIF<pa的指数小于pb的将"的当前节点复制到c尾部；Pa后移;ELSE将Pb的当前节点复制到c尾部；Pb后移；ENDIFENDWHILEIF<pa, pb中某一多项式未遍历结束将未遍历空的那一个所在的二项式剩余部分复制到c尾部;ENDIF返回合成多项式3、排序算法(1) Polynomal Polynomal:sort()Polynomal R;Term *p=first;p=p-&
13、gt;link;while(p!=first) insert(p->coef, p->exp, R);p=p->link;return R;(2 ) void Polynomal: insert (float c, mt e, Polynomal &R) Term *q=,*p=>link, *r;if(P=(q->link=new Term(c, e);八 c为空q->link->link=;elsewhile(p!=if(p->exp=e)/«l 数相等p->coef+=c;if(p->coef!=0)break
14、;if (p->coef=0)q->link=p->link;r=P；p=p->link;delete r;break;else if(p->exp>e) e小厂打前牯点的拆数q->link=new Term(c, e): q=q*>link;q->link=p;break;elsep=p->link;q=q*>link;if (p= e大于R中每一项的指数，插在表尾q->link=new Term(c, e); q->link->link=p;四、调试分析1、调试中的问题(1) 在测试数据一时，出现带有常数项
15、的多项式，常数项被构造为一次项，例如多项式 7 + 3x + 9xs + 5x17 被输出为 7x + 3x + 9_? + 5x17 解决办法：在重载运算符+中，”Ipa的指数小时，将程序ill pc=pc->InsertAfter (pa>coef, pb>exp) ; pb二pb->1 ink;改为pc=pc->InsertAfter(pb>coef, pb>exp) ;pb=pb->link;即可；(2) 在调试问题二的过程中，出现的0被程序自动忽略，不能打印使得输出结果为+ 8x +22x7 -9x8解决办法：在重载输出运算符的程序模块
16、中添加：if (current->coef0) current=current->link;即可保证程序的输出正常，但是是以0 +张+22x7-9x8作为输出的。(3) III于程序的数据结构构造成一种环形链表，因而在编程侧时候比单链表更 易出错，采取画图的方式容易解决问题。2、分析算法的时间复杂度和空间复杂度本实验所涉及算法基本采用顺序遍历方式，因而时间复杂度为o(m+n), 空间复杂度为o (m+n) o五、使用说明及测试结果按照程序提示，依次输入多项式的各项，系数与指数以Enter隔开，整个多 项式输入以0、-1结束。如下图所示：1、测试数据一2、测试数据二 C: WIHDO
17、WSsyst oM32ca<L exe输入：系数，扌旨数0 1输人：8 1输头：22 7输入：9 8输入0 1如、霓数，指数（以0、 系数，指数（以0、 奚数指数（以0、“结東）:-1结束）：7结束）：7结束）:进行插入摊序后的多迥式f <x>=The poliinomal is :0f(<x>=The pol«nonal ie: ;8X*22X7-9X8怡按f <x>构造后得到:CThe po lynonal is : bC-f <x>*y<x>Tlie pulnoniAl is : 0*8X *22X7-9X8请按
18、任意犍继续3、测试数据三品 C ; ¥IHDO¥Ssyst cm32o<1. exeBa：糸数讨旨数（以0、 ,22 7輪入：系数指数（以風_9 8BA：系数指数（以0 -1憤输入多项式= <r<x>：1a=系数指教（以乩系数指数（以氐a -1忆行插入推序后的多项式* <x）=The polynonal22X7-9X8*8X10结来:结束）： -1结東：T结束）: T结束）:is：!</<x)=The po lynonal1-1is :怡按"x构造后得到,22X7-9X8 <8X10CThc pol</nona
19、l is -C-f <x><x>Thc polynomal Is: i izxv-xstSKie4、测试数据四e： C:Hin）0¥Ssy3t obl32cbl<1. exe 输入：炙数走数（以臥-1结耒j"： -2 5输入：系数抬数（以臥7结東）: 熬嗦谿毅陆_1纟諌）: 常兑系数指数（以0、7结東）: 1 6输人系数指数（以0、-1结東）: 进石插入琳序后的多珂式F<x>=rhe poliinomal is:g<x> =The polnonal i©: -8XA2-1X6C按f<x构造后得到：C-Th
20、c po lynomal is : 6X37X6k)-f Cx> 3<x>TJie polynomal is : 8H26M3加5*6旷6六、源程序带注释3include<iostream>include<cmath>using namespace std;struct Term /多项式结点的定义float coef;八係数int exp;指数Term * link;Term(float c, int e, Term * next=NULL)coef=c;exp=e;1ink=next:Term *InsertAfter (float c, mt e
21、):Term & operator "=(Term & t)if=exp) coef=;return *this;Term & opemor +=(Term & t) if=exp) coef+=;return *this; friend ostream & operator<<(ostream const Termi);；class Polynomal/多项式的类定义/构造函数，建立空链表/必须链成环public:Polynomal0(first=new Term(0, 1);first>link=first;Polynom
22、al()makeEmpty();Polynomal (Polynomal & R) ;/父制构适函数/重载复制賦值操作符Polynomal & operator=(const Polynomal & R);void insert (float c, int e, PolynomalS R) ; 7对干二项式进行插入排序Polynomal sort () ;/对于多项式进行排序Term * getHeadO const return first;void makeEmpty ();private：Term * first;friend ostream & oper
23、ator*(ostream &,const Polynoma1&);friend istream & operator>>(istream &,Polynoma1&);friend Polynomal operator4-(Polynomalfi, Polyoma 1&);Term* Term：InsertAfter(float c, int e)/在十前由this指针指示的项(即调用此函数的对象)后面插入一个新项link=new Term(c, e, link);/创建一个新结点,自动链接return link;，/插入到this结
24、点后ifilostream& operator«(ostreamfc out, const Term& x) /Term的友元函数:输出个项X的内容到输出流 out中if= return out;0系数项不输出out«switch!case 0：break;case 1 ：out«'X" break;default:out<<"X*"<<break;return out:void Polynomal:insert(float c, int e, Polynomal &R)Term
25、 *q=,*p=>link, *r;if(P=(q->link=new Term(c, e)c为空q->link->link=;elsewhile(p!=if(p->exp=e)/«l 数相等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->exp>e) e小厂T前结点的描数q">link=new Term (c, e);
26、q=q">link;q">link=p;break;elsep=p">link;q=q">link;if(P= /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>lmk;return R;Po
27、lynomal:Polynomal (Polynomal& R) /复制构造函数：用已有多项式初始化'勺前多项式对象first=new Term(0, 1);Term *destptr=first,*srcptr=>link;while(srcptr!=destptr->InsertAfter(srcptr">coef,srcptr>exp);/在destptr所扌旨结点后插入一新结点.再让destpur扌&到这个新结点 srcptr=srcptr">link: destptr=destptr->link;dest
28、ptr>l ink=f irst;，'必须链成坏Polynomal & Polynomal:：operator = (const Polynomal & R)makeEmpty 0 ;. /先清空first=new Term(0, 1);Term *destptr=first,*srcptr=>link;while(srcptr!=destptr->InsertAfter(srcptr->coef, srcptr->exp);srcptr=srcptr>link;destptr=destptr->link;destptr>
29、l ink=f irst;'必须链成环return *this;void Polynomal:makeEmpty() Term *q;while(first">link!=first) q=first">link;first->link=q->link;delete q;istreams： operator>>(istream$： in, Polynomal& x)(Term *rear=;int e;float c; /定义圧扌斤针“arwhile(l)(cout«?z输入：系数指数(以、T结4l) ：'
30、;«endl;in»c»e;if (c=O&&e=-l) break:/用e小于控制输入结束rear =rear->InsertAfter (c, e) ;/链接到rear所扌H结点后return in;ostream & operator« (ostreaicA out, const Polynomal & x) /输出到附加头结点的多项式链表x Term *current=>link;cout«"The polynomal is: "<<endl;bool h=tr
31、ue;while(current!=(if (h=false&¤t">coef>out« ;h=false;if (current">coef=0) out«W;current=current->link;elseout«*current;涮用term类的重载操作"殳current=current->link;out<<endl;return out:Polynomal operator(Polynomal& A, Polynoma1& B)Term
32、 *pa,*pb,*pc, *p, *last;float temp;Polynomal C;pc二；pa=>link;pb=>link;while(pa!= &&pb! = /两两比较/对应项扌斤数/系数相加/pa指数小/pb指数小，加入ahif(pa->exp=pb">exp)相等temp=pa">coef+pb->coef;if(fabs(temp)!=O)pc=pc">InsertAfter (temp, pa->exp); pa=pa>link ;pb=pb>link;else
33、if(pa->exp<pb">exp)pc=pc->InsertAfter(pa->coef, pa->exp); pa=pa->link;elsepc=pc->InsertAfter (pb">coef, pb->exp);pb=pb->link;链if(pa!=tp=pa;last=;else p=pb;last=;)while(p!=last)pc=pc>InsertAfter (p->coef, p->exp );p=p*>link;return C;int mamO Poly
34、nomal A» B;cout«"请输入女项式：f (x):"<<endl;cin»A;cout«"请输入幺项式：g(x) ："«endl;cin»B;cout«*进行插入排序后的多项式"«endl;Polynomal Al=();Polynomal Bl=();Polynomal C(A1);/将Al賦值给Ccout«*f (x)="<<Al«endl;cout«*，g(x)=ZF<<Bl<<endl;cout«*C按f(k)构造后得到：C=v«C«endl;C=A1+B1;cout« *C=f (x)十 g (x) "<<C«endl;return 0;