南邮数据结构上机试验一线性表的基本运算和多项式的基本运算

1、实验报告（2015/2016学年第二学期）课程名称数据名构A实验名称线性表的基本运算和多项式的基本运算实验时间2016年3月10日指导单位计算机科学与技术系指导教师骆健学生姓名学院（系）班级学号管理学院专业信息管理与信息系统实习题名：线性表的基本运算班级姓名学号日期2016.03.10一、问题描述深入理解线性表数据结构，熟练掌握顺序表的各种基本操作。在顺序表类SeqList中增加成员函数voidReverse(),实现顺序表的逆置；在顺序表类SeqList中增加成员函数boolDeleteX(constT&x),删除表中所有元素值等于x元素。若表中存在这样的元素，则删除之，且函数返回t

2、rue,否则函数返回false。二、概要设计文件Inverse.cpp中定义了Linearlist类，SeqList类继承Linearlist类。在顺序表类SeqList中通过函数voidReverse()实现顺序表的逆置，通过函数boolDeleteX(constT&x),删除表中所有元素值等于x元素。三、详细设计1 .类和类的层次设计程序使用了两个类，线性表Linearlist类和顺序表SeqList类和一个主函数mian。Linearlist类里包括常见的线性表运算，在类SeqList里面新增成员函数voidReverse()和boolDeleteX(constT&x)。

3、Linearlist#intn+virtualboolIsEmpty()const=0;+virtualintLength()const=0;+virtualboolFind(inti,T&x)const=0;+virtualintSearch(Tx)const=0;+virtualboolInsert(inti,Tx)=0;+virtualboolDelete(inti)=0;+virtualboolUpdate(inti,Tx)=0;+virtualvoidOutput(ostream&out)const=0;TISeqList-intmaxLength;-T*elemen

4、ts;+IsEmpty()const;+Length()const;+Find(inti,T&x)const;+Search(Tx)const;+Insert(inti,Tx);+Delete(inti);+Update(inti,Tx);+Output(ostream&out)const;+Reverse();+DeleteX(constT&x);2 .核心算法顺序表SeqList类中，私有段封装了两个私有数据成员maxLength和elements,公有段封装了构造、析构、查找、删除、逆置等函数。实现要求的主要操作通过voidReverse()和boolDelete

5、X(constT&x)实现，voidReverse()通过前后互换实现逆置，boolDeleteX(constT&x)使用hash数组标记需要删除的元素，然后将放在elements里面的数据删除。两个函数的流程图如下。临时变量存放数据i<=n/2前后互换逆置YNinti=0i+voidReverse()inttmp=n,iboolDeleteX(constT&x)3 .算法分析线性表的基本运算程序的主要算法的算法时间复杂度和空间复杂度为O(n)四、程序代码voidSeqList<T>:Reverse()Ttemp;临时变量存放数据for(inti=0;

6、i<n/2;i+)前后互换逆置temp=elementsi;elementsi=elementsn-i-1;elementsn-i-1=temp;template<classT>boolSeqList<T>:DeleteX(constT&x)(inttmp=n,i;用于判断是否有删除数据n=0;int*hash=newinttmp;for(i=0;i<tmp;i+)(hashi=0;if(elementsi=x)hashi+;for(i=0;i<tmp;i+)if(!hashi)elementsn+=elements1;delete口hash;

7、if(n=tmp)判断是否有删除的数据returnfalse;elsereturntrue;五、测试和调试1.测试用例和结果1)输入顺序表的长度为10'D:VC+XDebugnverid?1eKe"I同科(t-hwLsfi-ffthofthve1.朝In3putftAeh雁I无星正力上；2) 输入10个元素分别为1,3,7,8,4,6,24,15,22,9"D:VC+*登上寓上.Inputt-hal-HTifTtcfthve10InputftACh熊l喷zgE;13) 输出创建好的表：1,3,7,8,4,6,24,15,22,9以及逆置后的表：9,22,15,24,

8、6,4,8,7,3,14）输入要删除的数据22,接着输出删除该数据后的5）重新输入需要删除的数据4,24,如图所示只删除了4241532Initialoq|119E；13?B4t24224Ftesevtrtdseqlist$9221E24&4fi71Inputthesloncinttobedele-tcdl=424Seqllvt-t-9rMi町曰dm：?S31524ts7312.结果分析1）程序能够正确的实现顺序表的逆置以及删除特定值的元素2）由测试结果来看，数据无法实现两个数的同时删除，还有改进的空问六、实验小结通过这次课程设计，使我对数据结构有了初步的清晰了解，增强了程序的编写能力

9、，在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，终于完成了这段程序。在调试过程中，我认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致整个程序不能运行。我也认识到了自己的薄弱之处，如对C+和链表知识不够熟悉，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、更全面。实习题名：多项式的基本运算班级姓名学号日期2016.03.10一、问题描述设计带表头结点的单链表表示的多项式类，在该类上定义和实现教材2.4节中程序2.7的多项式类上的各个运算，在该类上增加成员函

10、数voidPolyMul(Polynominal&r),并重载*运算符，实现菜单驱动的main函数，测试多项式类上各个运算：输入多项式，显示多项式，多项式加法和乘法运算。二、概要设计文件polynominal.cpp中定义了两个类，分别是多项式结点类Term和多项式类polynominal。三、详细设计1 .类和类的层次结构为实现多项式的算术运算，在polynominal类之前定义了Term类。Term-intcoef;-intexp;-Term*link;Polynomina-Term*theList+voidAddTerms(istream&in);+voidOutput(

11、ostream&out)const;+voidPolyAdd(Polynominal&r);+voidPolyMul(Polynominal&r);+Term(intc,inte);+Term(intc,inte,Term*nxt);+Term*InsertAfter(intc,inte);2 .核心算法项结点类中定义了三个私有数据域分别为coef、指数exp和指向下一个项结点的指针域link,多项式polynominal被声明成结点类的友元类。多项式polynominal其中包括了三个公有成员函数：AddTerms,Output,PolyAdd,PolyMul,分别实

12、现多项式的输入、输出、相加、相乘。PolyAdd(Polynominal&r)函数和PolyMul(Polynominal&r)函数的流程图如下。PolyAdd(Polynominal&r)3.算法分析PolyMul(Polynominal&r)多项式的加法和乘法算术运算程序的主要算法的时间复杂程度和和空间复杂程度为O(n)。四、程序代码voidPolynominal:PolyAdd(Polynominal&r)(Term*q,*q1=theList,*p;/q1指向表头结点p=r.theList->link;/p指向第一个要处理的结点q=q1-&

13、gt;link;/q1是q的前驱，p和q就指向两个当前进行比较的项while(p!=NULL&&p->exp>=0)/对r的单循环链表遍历，知道全部结点都处理完while(p->exp<q->exp)跳过q->exp大的项(q1=q;q=q->link;if(p->exp=q->exp)当指数相等时，系数相加(q->coef=q->coef+p->coef;if(q->coef=0)若相加后系数为0,贝U删除q(q1->link=q->link;delete(q);q=q1->lin

14、k;/重置q指针else(q1=q;若相加后系数不为0,则移动q1和qq=q->link;voidPolynominal:PolyMul(Polynominal&r)(Polynominalresult;Term*n=result.theList;定义相乘后的数据/n指向result的头结点在result的头结点后插入新结点，系数指数均为n=n->InsertAfter(0,0);0Term*p=r.theList->link;/p指向第一个要处理的结点while(p->exp>=0)/对r的单循环链表遍历(Polynominaltmp;存储某段相乘后的数

15、据Term*m=tmp.theList;/m指向tmp的头结点Term*q=theList->link;/q指向表头结点的后继结点while(q->exp>=0)/对当前对象的单循环环链表遍历(生成新m=m->InsertAfter(p->coef)*(q->coef),(p->exp)+(q->exp);/结点插入n后q=q->link;result.PolyAdd(tmp);将temp力口至Uresult上p=p->link;Term*q=theList->link;/q指向表头结点的后继结点while(q!=NULL)删除

16、原对象的所有数据(theList->link=q->link;deleteq;q=theList->link;q=theList;q=q->InsertAfter(0,0);PolyAdd(result);将result加到当前对象上五、1.测试和调试测试用例和结果1）选才¥1,计算多项式相加2）分别输入系数和项数32,46,97,如图所示3)4)5)得到相加的多项式如图选才¥2,计算多项式相乘输入系数和项数42,63,得到多项式一,如图6）再次输入系数和项数73,得到多项式二以及多项一和多项式二的乘2.结果分析1）程序能够正确实现多项式的相加以及相

17、乘2）但是程序无法实现不能加法乘法混用，下一步改进方向是实现加法乘法混用，是计算更加简便六、实习小结这个实验的重难点都在于正确灵活使用，大部分代码在书上都有提供，真正的操作重点在于理解这些代码的意义和使用方法。通过这次课程设计，使我对数据结构有了初步的清晰了解，增强了程序的编写能力，巩固了专业知识，对程序的模块化观念也又模糊逐渐变的清晰了。在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，终于完成了这段程序。在调试过程中，我认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致

18、整个程序不能运行。我也认识到了自己的薄弱之处，如对C+和链表知识不够熟悉，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、更全面。经过这次的实验，我在各个方面都得到了不少的提高，我希望多几次像这样的实验让我们更好的锻炼自己。附录：1 .线性表的基本运算#include<iostream>usingnamespacestd;intconstLEN=50;template<classT>classLinearListpublic:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolF

19、ind(inti,T&x)const=0;virtualintSearch(Tx)const=0;virtualboolInsert(inti,Tx)=0;|virtualboolDelete(inti)=0;virtualboolUpdate(inti,Tx)=0;virtualvoidOutput(ostream&out)const=0;protected:intn;/线性表的长度;template<classT>classSeqList:publicLinearList<T>private:intmaxLength;/线性表的最大长度T*eleme

20、nts;动态一维数组的指针public:SeqList(intmSize);SeqList()delete口elements;boolIsEmpty()const;intLength()const;boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);boolUpdate(inti,Tx);voidOutput(ostream&out)const;voidReverse();boolDeleteX(constT&x);template<classT>Se

21、qList<T>:SeqList(intmSize)maxLength=mSize;elements=newTmaxLength;动态分配顺序表的存储空间n=0;)template<classT>boolSeqList<T>:IsEmpty()const(returnn=0;)template<classT>intSeqList<T>:Length()const(returnn;)template<classT>boolSeqList<T>:Find(inti,T&x)const(if(i<0|i

22、>n-1)(cout<<"OutofBounds"<<endl;/对i进行越界检查returnfalse;)x=elementsi;returntrue;)template<classT>intSeqList<T>:Search(Tx)const(for(intj=0;j<n;j+)if(elementsj=x)returnj;return-1;)template<classT>boolSeqList<T>:Insert(inti,Tx)(if(i<-1|i>n-1)(cout&

23、lt;<"OutOfBounds"<<endl;|returnfalse;)if(n=maxLength)(cout<<"OverFlow"<<endl;returnfalse;)for(intj=n-1;j>i;j-)elementsj+1=elementsj;elementsi+1=x;|n+;returntrue;)template<classT>boolSeqList<T>:Delete(inti)if(!n)cout<<"UnderFlow"

24、<<endl;returnfalse;)if(i<0|i>n-1)cout<<"OutOfBounds"<<endl;returnfalse;)for(intj=i+1;j<n;j+)elementsj-1=elementsj;n-;returntrue;)template<classT>boolSeqList<T>:Update(inti,Tx)if(i<0|i>n-1)cout<<"OutOfBounds"<<endl;returnfal

25、se;)elementsi=x;returntrue;)template<classT>voidSeqList<T>:Output(ostream&out)constfor(inti=0;i<n;i+)out<<elementsi<<''out<<endl;)template<classT>voidSeqList<T>:Reverse()(Ttemp;临时变量存放数据for(inti=0;i<n/2;i+)前后互换逆置(temp=elementsi;elementsi=ele

26、mentsn-i-1;elementsn-i-1=temp;)template<classT>boolSeqList<T>:DeleteX(constT&x)inttmp=n,i;用于判断是否有删除数据n=0;int*hash=newinttmp;for(i=0;i<tmp;i+)(hashi=0;if(elementsi=x)hashi+;)for(i=0;i<tmp;i+)if(!hashi)elementsn+=elementsi;deletehash;if(n=tmp)判断是否有删除的数据returnfalse;elsereturntrue;

27、)intmain()(intdeldata,len,num;SeqList<int>A(LEN);cout<<"Inputthelengthoftheseqlist:"cin>>len;cout<<"nInputeachelement:"for(inti=0;i<len;i+)(cin>>num;A.Insert(i-1,num);)cout<<"nInitialseqlist:"A.Output(cout);A.Reverse();cout<<

28、"nReseveredseqlist:"A.Output(cout);cout<<"nInputtheelementtobedeleted:"cin>>del_data;if(A.DeleteX(deldata)=true)cout<<"nSeqlistafterbeingdeleted:"A.Output(cout);)elsecout<<"nNotfound"<<endl;return0;)2 .多项式的基本运算#include<iostream

29、.h>classTerm(public:Term(intc,inte);Term(intc,inte,Term*nxt);Term*InsertAfter(intc,inte);private:intcoef;intexp;Term*link;friendostream&operator<<(ostream&,constTerm&);friendclassPolynominal;);Term:Term(intc,inte):coef(c),exp(e)(link=0;_l)Term:Term(intc,inte,Term*nxt):coef(c),ex

30、p(e)(link=nxt;Term*Term:InsertAfter(intc,inte)(link=newTerm(c,e,link);returnlink;)ostream&operator<<(ostream&out,constTerm&val)(if(val.coef=0)returnout;out<<val.coef;switch(val.exp)(case0:break;case1:out<<"X"break;default:out<<"XA"<<val.e

31、xp;break;|)returnout;)classPolynominal(public:Polynominal();Polynominal();voidAddTerms(istream&in);voidOutput(ostream&out)const;voidPolyAdd(Polynominal&r);voidPolyMul(Polynominal&r);private:Term*theList;friendostream&operator<<(ostream&,constPolynominal&);friendistr

32、eam&operator>>(istream&,Polynominal&);friendPolynominal&operator+(Polynominal&,Polynominal&);friendPolynominal&operator*(Polynominal&,Polynominal&););Polynominal:Polynominal()(theList=newTerm(0,-1);头结点theList->link=NULL;单链表尾结点指针域为空Polynominal:Polynominal(

33、)(Term*p=theList->link;while(p!=NULL)(theList->link=p->link;deletep;p=theList->link;deletetheList;voidPolynominal:AddTerms(istream&in)(Term*q=theList;intc,e;for(;)(cout<<"Inputaterm(coef,exp):n"<<endl;cin>>c>>e;q=q->InsertAfter(c,e);if(0>e)brea

34、k;voidPolynominal:Output(ostream&out)const(intfirst=1;Term*p=theList->link;for(;p!=NULL&&p->exp>=0;p=p->link)(if(!first&&(p->coef>0)out<<"+"first=0;out<<*p;cout<<endl;voidPolynominal:PolyAdd(Polynominal&r)(Term*q,*q1=theList,*p;q1

35、指向表头结点p=r.theList->link;/p指向第一个要处理的结点q=q1->link;/q1是q的前驱，p和q就指向两个当前进行比较的项while(p!=NULL&&p->exp>=0)/对r的单循环链表遍历，知道全部结点都处while(p->exp<q->exp)跳过q->exp大的项(qi=q;q=q->link;if(p->exp=q->exp)当指数相等时，系数相加(q->coef=q->coef+p->coef;if(q->coef=0)若相加后系数为0,贝U删除q(q

36、1->link=q->link;delete(q);q=q1->link;/重置q指针else(q1=q;若相加后系数不为0,则移动q1和qq=q->link;else/p>exp>q->exp的情况q1=q1->InsertAfter(p->coef,p->exp);/以p的系数和指数生成新结点，插入q1后p=p->link;voidPolynominal:PolyMul(Polynominal&r)(Polynominalresult;定义相乘后的数据Term*n=result.theList;/n指向result的头结点n=n->InsertAfter(0