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

实验报告（2014/2015学年第二学期）课程名称数据结构A实验名称实验时间2015年03月27日指导单位计算机学院计算机科学与技术系指导教师学生姓名班级学号学院(系)专业1实验报告实验名称指导教师实验类型设计实验学时2实验时间2015.03.27一、实验目的和要求（1）线性表操作①在顺序表类SeqList中增加成员函数voidReverse()，实现顺序表的逆置。②在顺序表类SeqList中增加成员函数boolDelete(constT&x)，删除表中所有元素值等于x的元素。若表中存在这样的元素，则删除之，且函数返回true；否则函数返回false。③编写main函数，调用上述新增函数。提示：创建LinearList.h，SeqList.h文件包含程序2.1和程序2.2的代码。在其中新增上述两个函数。（2）一元多项式的相加和相乘①设计带表头结点的单链表表示的多项式类，在该类上定义和实现教材第2.4节中程序2.7的多项式类上的各个运算。②在该类上增加成员函数voidPolyMul(Polynominal&r)，并重载*运算符。③实现菜单驱动的main函数，测试多项式类上各个运算：输入多项式、显示多项式、多项式加法和乘法运算。二、实验环境(实验设备)硬件：微型计算机软件：Windows操作系统、MicrosoftVisualC++6.02三、实验原理及内容1、类和类的层次结构（1）线性表操作：LinearList{abstract}#in+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+virtualboolOutput(ostream&out)const=0父类：子类：继承关系(2)一元多项式的加法与乘法SeqList-T*elements-intmaxLength+SeqList(intmSize)+~SeqList()+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()+boolDeletevalue(constT&x)Term-intcoef-intexp-Term*link-friendclassPolynominal+Term(intc,inte)+Term(intc,inte,Term*nxt)+Term*insertAfter(intc,inte)TLinearListSeqList3实验报告2、算法与数据结构(1)线性表操作Deletevalue()函数调用情况顺序表SeqList的结构示意Polynominal+Term*theList+Polynominal()+~Polynominal()+voidsortPolynominal(Polynominal&r)+voidaddTerms(istream&in)+voidoutput(ostream&out)const+voidpolyAdd(Polynominal&r)+voidpolyMult(Polynominal&r)+voidequivalent(Polynominal&r)+friendostream&operator(ostream&out,Polynominal&x)+friendistream&operator(istream&in,Polynominal&x)+friendPolynominal&operator+(Polynominal&a,Polynominal&b)+friendPolynominal&operator*(Polynominal&a,Polynominal&b)…an-1…a1maxLengthintaintiLA：SeqList.DeletevalueLA:SeqList.Deleaten栈顶4实验报告（2）多项式的加法与乘法多项式Polynominal对象的结构示意乘法函数polyMult()调用关系加法函数polyAdd()调用关系重载输入函数的调用关系赋值函数equivalent()的调用关系Polynominal&rPolynominal&ristream&inPolynominal&aPolynominal&bPolynominal&aPolynominal&b...0-1LinkcoefexpLinktheListcoefexpLinkx:Polynominal&operator*()x:Polynominal.polyMult()x:Polynominal&operator+()x:Polynominal.polyAdd()istream&inPolynominal&xaddTerms()x:Polynominal.polyAdd()x:Polynominal.equivalent()x:istream&operator()53、核心算法C++代码（1）多项式乘法函数polyMult()voidpolyMult(Polynominal&r){Term*q,*q1=theList,*p,*m;//声明Term类指针，q1指向当前对象的theListq=q1-link;//q指针指向theList的下一个节点，即当前对象的第一个节点Polynominalt;m=t.theList-link;//新建Polynominal对象t用于存储乘法运算的结果intcoef=0;intexp=0;while(q-exp=0){//q的指数大于0才继续p=r.theList-link;//每遍历对象r的链表后，p重新指向链表开头while(p-exp=0){//遍历对象r的链表coef=p-coef*q-coef;//当前对象与对象r的节点中的系数相乘，结果赋值给coefexp=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;6exp=p-exp;q-insertAfter(coef,exp);//如果移动到当前对象最后节点，新建节点并存t中的结果}p=p-link;}}（2）多项式加法运算polyAdd()函数voidpolyAdd(Polynominal&r){//将r中链表中的数据与插入当前对象的链表中Term*q,*q1=theList,*q2,*p;p=r.theList-link;q=q1-link;while(p-exp=0){while(p-expq-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中的数据7q1=q1-insertAfter(p-coef,p-exp);p=p-link;}//else}//while}//PolyAdd（3）多项式中的主函数main()，实现菜单驱动功能intmain()//主函数，进行选择{inta=0;Polynominalx,y,x1,y1,add,mult;menu();//调用menu()函数，显示菜单SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED);system(color2F);while(a!=5){cina;switch(a)//输入数字，选择功能{case1://输入多项式cinx;x.sortPolynominal();//将输入的多项式降幂排序ciny;y.sortPolynominal();x1.equivalent(x);//x1以及随后的y1用于存储输入的多项式，可重复使用coutx1endl;y1.equivalent(y);couty1endl;system(cls);menu();break;//跳出循环，重新选择功能case2://输出多项式coutx:xendl;couty:yendl;system(cls);8menu();break;case3://多项式加法运算功能x.equivalent(x1);//避免多项式x不断增大y.equivalent(y1);add.equivalent((x+y));//使用赋值函数而非“=”为避免地址冲突coutX+Y=endladdendl;system(cls);menu();break;case4://多项式乘法运算功能x.equivalent(x1);y.equivalent(y1);mult.equivalent(x*y);coutX*Y=endlmultendl;system(cls);menu();break;case5://结束功能，终止循环printf(\n结束!\n);break;default://未按要求选择功能，重新输入选择printf(\n请再次输入!\n);system(cls);menu();break;}}return0;}9（4）多项式中的实现对象之间赋值的equivalent()函数//该函数主要解决菜单功能下输入一组数据重复进行运算时避免数据累加的情况//解决因使用“=”进行对象之间赋值，导致对象被析构后出现访问地址冲突的问题voidequivalent(Polynominal&r)//对象调用该函数后，具有和参数对象r同样的多项式{Term*p,*q;intcoef=0;intexp=0;p=r.theList-link;//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