多项式加法实验报告

1、题 目： 多项式加法 8 / 10文档可自由编辑打印多项式加法一、 课题概述线性表是一种最简单、最基本，也是最常用的数据结构，其用途十分广泛，例如，用带表头结点的单链表求解一元整系数多项式加法和乘法运算。现给两个一元整系数多项式，请求解两者之和。输入两组数据，每一组代表一个一元整系数多项式，有多行组成，其中每一行给出多项式每一项的系数和指数，这些行按指数递减次序排序，每一组结束行为0 -1。输出三组数据，前两组为一元整系数多项式，最后一组为两个多项式的和。一元整系数多项式输出形式如下：（1）多项式项4x输出为4X（2）多项式项4x2输出为4X2（3）第一项系数为正数时，加号不要输出（4）除常系

2、数项外，项系数为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。Ad

3、dTerms函数通过输入流in,输入多项式的各项构造一个多项式的单循环链表；Output函数将多项式按降幂方式送输出流；PolyAdd函数实现将多项式r加到指针this指示的多项式上。AddTerms函数从输入流in按降幂输入各项（c,e）来构造多项式的单循环链表，当输入（0，-1）是构造过程结束。Output函数遍历单循环链表将多项式按降幂方式送输出流，它调用项类Trem上重载的“<<”操作符实现按项输出。多项式加法，设有多项式p(x)和q(x),分别用单循环链表表示。设p和q分别指向多项式p(x)和q(x)的当前正进行比较的项节点，初始时分别指向两多项式中最高幂次的项节点。q

4、1指向q的前驱节点。对p(x)进行遍历。直到处理完所有节点。当p->exp<q->exp，则q指示的项应该为多项式结果中的一项，所以q 1和 q 右移一项，指针p不动。当多项式指数相等时（p->exp=q->exp），系数相加，即q->coef=q->coef+p->coef。加完之后如果系数为0，则删除节点，p右移一项，如果加完之后系数不为0，指针q 1和q均右移一个节点。当p->exp>q->exp，则复制p所指示的节点，并将其插入在q 1后；指针右移一个节点。2、关键函数流程图：一元多项式创建成功按降幂依次输入各项的系数和

5、指数创建链表类型的 项多项式创建流程图： 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&

6、lt;<*m结束 N Y3、源代码：#include<iostream>using 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; fr

7、iend ostream & operator<<(ostream &,const Term &); /重载”<<“，输出多项式的一项 friend class Polynominal; /类Polynominal作为类Term的友元类 ;Term:Term(int c,int e):coef(c),exp(e) link=0;Term:Term(int c,int e,Term *nxt):coef(c),exp(e)link=nxt;Term* Term:InsertAfter(int c,int e)/为新项申请节点的存储单元，并用Term

8、函数将c,e和this->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:out<<1;break; /

9、如果在系数为1的前提下，指数为0，则输出“1" case 1:out<<"X" break; /如果在系数为1的前提下，指数为1，则输出"X" default:out<<"X"<<val.exp; break; /如果在系数为1的前提下，不为0，也不为1，则输先出“X" ,后面紧跟输出指数的值 return out; if( val.coef=-1)/如果系数为-1 ，再判断 switch (val.exp) case 0:out<<-1;break;/如果在系数为-

10、1的前提下，指数为0，则输出“-1" case 1:out<<"-X" break;/如果在系数为-1的前提下，指数为1，则输出“-" default:out<<"-X"<<val.exp; break; /如果在系数为-1的前提下，指数不为0，也不为1，则输出“-X",后面紧跟输出指数的值 return out; else /如果系数不满足以上所有情况，则执行else语句 out<<val.coef; /先输出系数，对于整数前面的"+"，在 Output中

11、进行处理 switch (val.exp) case 0:break; /如果指数为0，则什么都不做，直接break case 1:out<<"X" break;/如果指数为1的话，输出一个"X" default:out<<"X"<<val.exp; break;/如果指数不为0，也不为1，则输出“-X",后面紧跟输出指数的值 return out; class Polynominal /多项式类public: Polynominal(); /构造函数的声明 Polynominal();

12、/析构函数则输出“-X",后面紧跟输出指数 的值 void AddTerms(istream& in); /输入多项式的各项，构造多项式链表 void Output(ostream& out)const;/将多项式送输出流 void PolyAdd(Polynominal& r); /多项式相加 private:Term* theList; /单循环链表的表头指针 friend ostream & operator <<(ostream &,const Polynominal&); friend istream &

13、operator >>(istream &,Polynominal &); friend Polynominal & operator +(Polynominal &, Polynominal &);Polynominal:Polynominal() /创建多项式的空的单循环链表 theList=new Term(0,-1); /分配表头节点存储单元 theList->link=theList; /构成循环链表 Polynominal:Polynominal() /撤销多项式的单循环链表 Term* p=theList->link

14、; 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 (;) cin>&

15、gt;c>>e; 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);cout<<0;/如果计数器为0，即刚开始就输入了”0，-1“，则输出”0“ void Polynominal:Output(ostream& out)const int j,k=0,i=0; Term *m=theList->link; fo

16、r(;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) cout<<0<<endl; return; /如果只有一项，并且为系数为0，则输出一个0 if(i=k) cout<<0<<endl; return; /如果全为0，则输出一个0 fo

17、r(j=0;j<i;j+) /找到第一个不为0的项，并输出 m=m->link; out<<*m; m=m->link; for(;m!=theList;m=m->link) /再遍历第一个不为0的节点之后的节点 if(m->coef>0) /如果系数大于o out<<"+" /输出一个“+" out<<*m; /然后输出该项 else if(m->coef<0) /如果系数小于0 out<<*m; /直接输出该项 cout<<endl; /换行 void

18、Polynominal:PolyAdd(Polynominal &r) /将多项式r加到多项式this上 Term *q,*q1=theList,*p; /q1指向表头节点 p=r.theList->link; /p指向第一个要处理的节点 q=q1->link; /q1是q的前驱，p和Q就是指向当前要进行比较的项 while(p->exp>=0) / 对r的单循环链表进行遍历， 直到全部节点处理完毕 while(p->exp<q->exp) / 跳过q->exp的项 q1=q; q=q->link; if(p->exp=q-&

19、gt;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->exp>1->exp的情况 p=p->link; / 以p的系数和指数生成新节点，插入q1后 ostream & operator <