数据结构A第一次实验报告.doc

实 验 报 告（2014 / 2015 学年 第 二 学期）课程名称数据结构A实验名称实验时间2015年03月27日指导单位计算机学院计算机科学与技术系指导教师学生姓名班级学号学院(系)专 业 实 验 报 告实验名称指导教师实验类型设计实验学时2实验时间2015.03.27一、 实验目的和要求（1）线性表操作在顺序表类SeqList中增加成员函数void Reverse()，实现顺序表的逆置。 在顺序表类SeqList中增加成员函数bool Delete(const T &x)，删除表中所有元素值等于x的元素。若表中存在这样的元素，则删除之，且函数返回true；否则函数返回false。编写main函数，调用上述新增函数。提示：创建LinearList.h，SeqList.h文件包含程序2.1和程序2.2的代码。在其中新增上述两个函数。（2）一元多项式的相加和相乘设计带表头结点的单链表表示的多项式类，在该类上定义和实现教材第2.4节中程序2.7的多项式类上的各个运算。在该类上增加成员函数void PolyMul(Polynominal& r)，并重载*运算符。实现菜单驱动的main函数，测试多项式类上各个运算：输入多项式、显示多项式、多项式加法和乘法运算。二、实验环境(实验设备)硬件：微型计算机软件：Windows 操作系统、Microsoft Visual C+6.0三、实验原理及内容1、类和类的层次结构（1）线性表操作：TLinearListabstract# in + virtual bool IsEmpty() const=0+ virtual int Length() const=0+ virtual bool Find(int i, T& x)const=0+ virtual int Search(T x)const=0+ virtual bool Insert(int i, T x)=0+ virtual bool Delete(int i)=0+ virtual bool Update(int i, T x)=0+ virtual bool Output(ostream& out)const=0LinearList父类：SeqListSeqList- T* elements- int maxLength+ SeqList(int mSize)+ SeqList()+ bool IsEmpty()const+ int Length()const+ bool Find(int i, T& x)const+ int Search(T x)const+ bool Insert(int i, T x)+ bool Delete(int i)+ bool Update(int i, T x)+ void Output(ostream& out)const+ void Reverse()+ bool Deletevalue(const T &x)子类： 继承关系(2)一元多项式的加法与乘法Term- int coef- int exp- Term* link- friend class Polynominal+ Term(int c, int e)+ Term(int c, int e, Term* nxt)+ Term* insertAfter(int c, int e)实 验 报 告Polynominal+ Term* theList+ Polynominal()+ Polynominal()+ void sortPolynominal(Polynominal &r)+ void addTerms(istream& in)+ void output(ostream& out) const+ void polyAdd(Polynominal& r)+ void polyMult(Polynominal& r)+ void equivalent(Polynominal& r)+ friend ostream& operator(istream& in, Polynominal& x)+ friend Polynominal& operator+(Polynominal& a, Polynominal& b)+ friend Polynominal& operator*(Polynominal& a,Polynominal& b)2、算法与数据结构(1)线性表操作an-1a1LA：SeqList.Deletevalueint iint aLA:SeqList.Deleate Deletevalue()函数调用情况maxLengthn 栈顶 顺序表SeqList的结构示意实 验 报 告（2）多项式的加法与乘法. . .coef exp Linkcoef exp LinktheList0 -1 Link多项式Polynominal对象的结构示意x: Polynominal& operator+()x: Polynominal& operator*()Polynominal& aPolynominal& bPolynominal& aPolynominal& bx:Polynominal.polyAdd()x:Polynominal.polyMult() 乘法函数polyMult()调用关系 加法函数polyAdd()调用关系x:Polynominal.polyAdd()x:istream& operator()Polynominal& ristream& inPolynominal& ristream& in Polynominal& xx:Polynominal.equivalent()addTerms() 重载输入函数的调用关系 赋值函数equivalent()的调用关系3、核心算法C+代码（1）多项式乘法函数polyMult()void polyMult(Polynominal& r) Term* q, *q1 = theList, *p,*m; /声明Term类指针，q1指向当前对象的theList q = q1-link; /q指针指向theList的下一个节点，即当前对象的第一个节点 Polynominal t; m=t.theList-link; /新建Polynominal对象t用于存储乘法运算的结果 int coef=0; int exp=0; while(q-exp=0) /q的指数大于0才继续 p = r.theList-link; /每遍历对象r的链表后，p重新指向链表开头 while(p-exp=0) /遍历对象r的链表 coef=p-coef*q-coef; /当前对象与对象r的节点中的系数相乘，结果赋值给coef exp=p-exp+q-exp; /时间复杂度O(n) m-insertAfter(coef,exp); /将乘法结果存入新的对象链表中，时间复杂度为O(n) p=p-link; /移向对象r的下一节点 q=q-link; /移向当前对象的下一节点 p=t.theList-link; q=this-theList-link; while(p-exp=0) /遍历新建的对象t的链表 if(q-exp=0) /如果点前对象存在节点，将t的节点中存的结果赋给当前对象 q-coef=p-coef; q-exp=p-exp; q=q-link; /指针q向后移动，指向链表下一节点 else coef=p-coef; exp=p-exp; q-insertAfter(coef,exp); /如果移动到当前对象最后节点，新建节点并存t中的结果 p=p-link; （2）多项式加法运算polyAdd()函数void polyAdd(Polynominal& r) /将r中链表中的数据与插入当前对象的链表中 Term* q, *q1 = theList, *q2, *p; p = r.theList-link; q = q1-link; while(p-exp = 0) while(p-exp exp) /如果q指向的当前节点中的指数大于p中的指数，q、q1后移 q1 = q; q = q-link; if(p-exp = q-exp) /如果p中的指数与q中的指数相等，则系数相加 q-coef = q-coef + p-coef; if(q-coef = 0) /如果相加后的系数为0，删除q指向的此节点 q2 = q; q1-link = q-link; q = q-link; delete(q2); p = p-link; else /相加后系数不为0，q1,q后移分别指向下一节点 q1 = q; q = q-link; p = p-link; else /如果q中的指数小于p中的指数，将新建节点插入q1后，并存入p中的数据 q1 = q1-insertAfter(p-coef, p-exp); p = p-link; /else /while /PolyAdd（3）多项式中的主函数main()，实现菜单驱动功能int main() /主函数，进行选择 int a=0;Polynominal x, y,x1,y1,add,mult;menu(); /调用menu()函数，显示菜单SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED);system(color 2F);while (a!=5) cina;switch(a) /输入数字，选择功能case 1: /输入多项式cinx;x.sortPolynominal(); /将输入的多项式降幂排序ciny;y.sortPolynominal();x1.equivalent(x); /x1以及随后的y1用于存储输入的多项式，可重复使用coutx1endl;y1.equivalent(y);couty1endl;system(cls); menu(); break; /跳出循环，重新选择功能case 2: /输出多项式coutx:xendl;couty:yendl;system(cls);menu();break;case 3: /多项式加法运算功能x.equivalent(x1); /避免多项式x不断增大y.equivalent(y1);add.equivalent(x+y); /使用赋值函数而非“=”为避免地址冲突coutX+Y=endladdendl;system(cls); menu(); break; case 4: /多项式乘法运算功能x.equivalent(x1);y.equivalent(y1);mult.equivalent(x*y);coutX*Y=endlmultlink; /p指向参数r的第一个节点q1=theList;q=this-theList-link; /q指向当前对象的第一个节点while(p-exp=0) /遍历对象r的链表if(q-exp=0) /q-coef=p-coef;q-exp=p-exp; q1=q;q=q-link;else /如果当前对象节点少于r的节点，则在链尾添加节点coef=p-coef;exp=p-exp;q1=q1-insertAfter(coef,exp);p=p-link;if(q-exp=0) /如果当前对象节点多与r，则删除多余的节点 q1-link=theList; delete(q);（5）多项式中对链表进行降幂排序sortPolynominal()函数（可合并系数相同项）void sortPolynominal() Term* q=theList-link; Term t(0,0); Term* p=&t; int length=0; while(q!=theList) /遍历对象的链表，求取链表的节点个数 q=q-link; length+; for(int i=length;i0;i-) /采用冒泡法对链表进行降幂排序 q=theList-link; for(int j=1;jexplink-exp) /时间复杂度为O(n2) p-coef=q-coef; p-exp=q-exp; q-coef=q-link-coef; q-exp=q-link-exp; q-link-coef=p-coef; q-link-exp=p-exp; else if(q-exp=q-link-exp) /如果相邻两个节点指数相等，则进行系数相加 q-coef=q-coef+q-link-coef; q-link=q-link-link; q=q-link; （6）顺序表的逆置函数Reverse()void SeqList:Reverse()if(n=1) /判断线性表是否少于两个元素，coutThe elements are too less!endl;return false;elseT *element= new T maxLength; /新建一个T类型数组，定义T类型指针指向所建数组for(int i=0;in;i+)elementi=elementsn-i-1; /循环遍历原数组，并从后往前讲数组元素赋值给新的数组 /时间复杂度为O(n)delete elements; /删除原有指针elements=element; /指针指向新建的数组（7）SeqList中的删除相同元素函数Deletevalue()templatebool SeqList:Deletevalue(const T &x)for(int i=0;in;i+) /遍历数组if(x=elementsi) /如果数组某一个元素值与函数的输入参数值相等，则删除元素Delete(i);i-; /不遗漏遍历，时间复杂度为O(n)return true;4、调试结果（1）对顺序表逆置操作结果：（2）对顺序表进行删除元素的操作结果：相关描述：顺序表中原有数据为0,1,2,3,4,5,6,7,8,9,5，输入要删除的数字：5，结果顺序表中的两个元素数字5都被删除。（3）多项式的菜单驱动功能显示：（4）多项式的输入：（5）多项式的输出：（6）多项式加法：（7）多项式乘法：注：当只输入一组数据时，可重复2、3、4操作，输出相同结果可多次重新输入多项式，进行相关运算实 验 报 告实 验 报 告四、实验小结（包括问题和解决方法、心得体会、意见与建议等） (一)实验中遇到的主要问题及解决方法在题目二编译正确运行时，出现了如下几个问题以及相关解决方法：（1）源程序输入多项式时，要求输入多项式按照降幂方式输入，如果输入的具有相同指数的项则在加法运算时不能合并计算。为了解决这个问题，简化输入要求，添加了一个实现降幂排序函数sortPolynominal()，该函数可以对输入的多项式各项进行降幂排序，并将指数相同的项合并，使加法运算结果更加准确合理，且输入时不需要按照降幂输入。同时，也解决了在乘法运算时可能发生的项与项的相乘结果出现指数相同时不能合并的问题。（2）实现乘法运算时，采用的方法是新建一个多项式对象t用于存储乘法结果，运行后结果正确。但是在将多项式的结果赋值给x时，出现了错误。经逐步调试发现，直接用等号赋值出现错误。解决方法是改动x和t的链表：将x的theList指向t的第一个节点，将t的末尾节点指向x的theList，重新构造x的链表。调试发现，在该函数体内x的链表确实为乘法运算正确的结果。但运行时又出现了访问地址冲突的错误，错误显示为在执行析构函数时节点指针内容为空即指向了未知区域。猜想是因为x取代t的链表，造成x和t对象同时指向同一地址，结束时析构函数无法正常执行。于是用了一个循环函数，将t中的节点值取出，再用节点类的插入函数insertAfter(int c, int e)重新构造了x的链表，最终输出结果正确。（3）在实现菜单功能时，出现一次输入数据，多次进行多项式运算，结果不断增大的问题。思考后发现加法和乘法运算，都是将结果赋