多项式加法实验报告.doc_第1页
多项式加法实验报告.doc_第2页
多项式加法实验报告.doc_第3页
多项式加法实验报告.doc_第4页
多项式加法实验报告.doc_第5页
已阅读5页,还剩5页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

题 目: 多项式加法 多项式加法一、 课题概述线性表是一种最简单、最基本,也是最常用的数据结构,其用途十分广泛,例如,用带表头结点的单链表求解一元整系数多项式加法和乘法运算。现给两个一元整系数多项式,请求解两者之和。输入两组数据,每一组代表一个一元整系数多项式,有多行组成,其中每一行给出多项式每一项的系数和指数,这些行按指数递减次序排序,每一组结束行为0 -1。输出三组数据,前两组为一元整系数多项式,最后一组为两个多项式的和。一元整系数多项式输出形式如下:(1)多项式项4x输出为4X(2)多项式项4x2输出为4X2(3)第一项系数为正数时,加号不要输出(4)除常系数项外,项系数为1不显式输出,-1输出为-例如,4x3- x2+x-1正确输出形式为4X3-X2+X-1,错误输出形式为+4X3-1X2+1X-1二、 设计与实现1、类的层次关系及核心算法分析:项节点类Trem中定义了三个私有变量,系数coef、指数exp和指向下一个项节点的指针域link。多项式类Polynominal被声明成项节点类Trem类的友元类。公有函数InsertAfter构造一个新的项节点,其系数为c指数为e,并将新节点插入在调用该函数的项节点及后继节点之间。多项式类Polynominal中包含了3个公有成员函数:AddTerms,Output和 PolyAdd。AddTerms函数通过输入流in,输入多项式的各项构造一个多项式的单循环链表;Output函数将多项式按降幂方式送输出流;PolyAdd函数实现将多项式r加到指针this指示的多项式上。AddTerms函数从输入流in按降幂输入各项(c,e)来构造多项式的单循环链表,当输入(0,-1)是构造过程结束。Output函数遍历单循环链表将多项式按降幂方式送输出流,它调用项类Trem上重载的“expexp,则q指示的项应该为多项式结果中的一项,所以q 1和 q 右移一项,指针p不动。当多项式指数相等时(p-exp=q-exp),系数相加,即q-coef=q-coef+p-coef。加完之后如果系数为0,则删除节点,p右移一项,如果加完之后系数不为0,指针q 1和q均右移一个节点。当p-expq-exp,则复制p所指示的节点,并将其插入在q 1后;指针右移一个节点。2、关键函数流程图:一元多项式创建成功按降幂依次输入各项的系数和指数创建链表类型的 项多项式创建流程图: N输入“0 -1”开始 Y 多项式加法流程图: Output函数流程图:开始开始遍历单循环链表,统计统计单循环链表有几项(k),统计单循环链表前几项(i)为0。跳过系数大的项指数相等吗?N如果只有一项,并且为系数为0,则输出一个0。 Y系数相加如果全为0,则输出一个0。系数为0 N再遍历一次单循环链表,找到第一个不为0的节点,并把系数输出,不管正负号。 Y删除p,重置q指针。移动q1和q以p的系数和指数生成新节点,插入q1后.从第一个不为0的节点之后的节点开始遍历单循环链表。系数0指数大于等于0 Y 结束输出该项输出一个“+out*m结束 N Y3、源代码:#includeusing namespace std;class Polynominal; /向前引用 ,因为后面定义的Trem类中用到Polynominal类 class Term /定义项节点类Trem public: Term(int c,int e); Term(int c,int e,Term *nxt); Term* InsertAfter(int c,int e); /在this指针指示的节点后插入新节点 private: int coef; /系数 int exp; /指数 Term *link; friend ostream & operator(ostream &,const Term &); /重载”link的值填入新节点的相应域 link=new Term(c,e,link); return link;ostream & operator(ostream & out,const Term & val)/重载”,输出多项式的一项,用coef Xexp表示多项式的每一项 if(val.coef=0) return out; /如果系数为0,直接跳出 if(val.coef=1) /如果系数为1 ,再判断 switch (val.exp) case 0:out1;break; /如果在系数为1的前提下,指数为0,则输出“1 case 1:outX; break; /如果在系数为1的前提下,指数为1,则输出X default:outXval.exp; break; /如果在系数为1的前提下,不为0,也不为1,则输先出“X ,后面紧跟输出指数的值 return out; if( val.coef=-1)/如果系数为-1 ,再判断 switch (val.exp) case 0:out-1;break;/如果在系数为-1的前提下,指数为0,则输出“-1 case 1:out-X; break;/如果在系数为-1的前提下,指数为1,则输出“- default:out-Xval.exp; break; /如果在系数为-1的前提下,指数不为0,也不为1,则输出“-X,后面紧跟输出指数的值 return out; else /如果系数不满足以上所有情况,则执行else语句 outval.coef; /先输出系数,对于整数前面的+,在 Output中进行处理 switch (val.exp) case 0:break; /如果指数为0,则什么都不做,直接break case 1:outX; break;/如果指数为1的话,输出一个X default:outXval.exp; break;/如果指数不为0,也不为1,则输出“-X,后面紧跟输出指数的值 return out; class Polynominal /多项式类public: Polynominal(); /构造函数的声明 Polynominal(); /析构函数则输出“-X,后面紧跟输出指数 的值 void AddTerms(istream& in); /输入多项式的各项,构造多项式链表 void Output(ostream& out)const;/将多项式送输出流 void PolyAdd(Polynominal& r); /多项式相加 private:Term* theList; /单循环链表的表头指针 friend ostream & operator (istream &,Polynominal &); friend Polynominal & operator +(Polynominal &, Polynominal &);Polynominal:Polynominal() /创建多项式的空的单循环链表 theList=new Term(0,-1); /分配表头节点存储单元 theList-link=theList; /构成循环链表 Polynominal:Polynominal() /撤销多项式的单循环链表 Term* p=theList-link; while (p!=theList) theList-link=p-link; /删除p节点 delete p; /释放p之前的存储空间 p=theList-link; /p指向下一个待删除的节点 delete theList; /释放表头节点的存储单元 void Polynominal:AddTerms(istream & in) /按指数递减次序输入各项,构造单循环链表 int count=0; /定义一个变量,用作计数 Term *q=theList; /定义一个指针,指向表头节点 int c,e; /coef.exp for (;) cince; if (c=0&e=-1) /当输入”0,-1“的时候,构造过程结束 break; else q=q-InsertAfter(c,e);/将c,e插入表尾节点之后 count+; /统计输入项的个数 if(count=0) q=q-InsertAfter(0,0);coutlink; for(;m!=theList&m-coef=0;m=m-link)i+; /统计单循环链表前几项为0 m=theList-link; for(;m!=theList;m=m-link)k+; /统计单循环链表有几项 m=theList-link; if(k=1&(m-coef=0) cout0endl; return; /如果只有一项,并且为系数为0,则输出一个0 if(i=k) cout0endl; return; /如果全为0,则输出一个0 for(j=0;jlink; outlink; for(;m!=theList;m=m-link) /再遍历第一个不为0的节点之后的节点 if(m-coef0) /如果系数大于o out+; /输出一个“+ outcoef0) /如果系数小于0 out*m; /直接输出该项 coutlink; /p指向第一个要处理的节点 q=q1-link; /q1是q的前驱,p和Q就是指向当前要进行比较的项 while(p-exp=0) / 对r的单循环链表进行遍历, 直到全部节点处理完毕 while(p-expexp) / 跳过q-exp的项 q1=q; q=q-link; if(p-exp=q-exp) /当指数相等时相加 q-coef=q-coef+p-coef; if (q-coef=0) /若相加后系数为0,则删除p q1-link=q-link; delete (q); q=q1-link; / 重置q指针 else q1=q; q=q-link; /若相加后系数不为0,则移动q1和q else q1=q1-InsertAfter(p-coef,p-exp); /p-exp1-exp的情况 p=p-link; / 以p的系数和指数生成新节点,插入q1后 ostream & operator (istream &in,Polynominal &x) x.AddTerms(in); return in;Polynominal & operator +(Polynominal &a, Polynominal &b) a.PolyAdd(b); return a; int main( ) /主函数 Polynominal p,q,q1; cinp,coutq,coutq; q1=q+p; coutq1;三、 测试数据和结果分析 第一组: 第二组 第三组: 输

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论