线性表的基本运算及多项式的算术计算重点讲义资料

实验报告（/学年第一学期）课程名称数据结构A实验名称线性表的基本运算及多项式的算术计算实验时间年月日指导单位指导教师学生姓名班级学号学院(系)专业2实验报告实验名称线性表的基本运算及多项式的算术计算指导教师实验类型上机实验学时2实验时间一、实验目的和要求实验目的：1、深入理解线性表数据结构，掌握线性表的顺序和链接两种存储方式。2、熟练掌握顺序表的各种基本操作。3、学会使用线性表解决应用问题的方法。4、加深对抽象类模板、类的继承、代码重用等C++知识的理解和使用。内容和要求：1、在顺序表类中增加成员函数voidReverse（），实现顺序表逆置。2、在顺序表类中增加成员函数boolDeleteX(constT&x),删除表中所有元素值等于x的元素。若存在则删除之且返回true，否则返回false。3、编写main函数，调用上述新增函数。4、设计带表头结点的单链表表示的多项式类，实现各个运算。5、增加成员函数voidPolyMul(Polynominal&r),并重载*运算符。6、编写main函数，测试多项式类的各个运算。二、实验环境(实验设备)硬件：PC软件：Code::Blocks(C++)3三、实验原理及内容1、线性表的基本运算（1）核心算法及流程图○1顺序表逆置：思路：将顺序表中第j个结点中的元素与第（n-1-j）个结点中的元素替换，从第一个结点开始，共进行（n/2取整）次。代码：templateclassTvoidSeqListT::Reverse(){intm=n/2;for(intj=0;jm;j++){Ttemp=elements[j];elements[j]=elements[n-1-j];elements[n-1-j]=temp;}}流程图：4○2删除表中所有元素值等于x的元素：思路：遍历顺序表，没搜索到一次x，就将其后所有结点前移，考虑到x连续存在的情况，将所有结点前移之后，i自减，再循环进行。代码：templateclassTboolSeqListT::DeleteX(constT&x)5{intflag=n;for(inti=0;in;i++){if(elements[i]==x){for(intj=i+1;jn;j++){elements[j-1]=elements[j];}i--;n--;}}if(flagn){returntrue;}else{returnfalse;}6}流程图：7（2）完整代码：#includeiostreamusingnamespacestd;templateclassTclassSeqList{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);private:intmaxLength;T*elements;8intn;};templateclassTSeqListT::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];n=0;}templateclassTboolSeqListT::IsEmpty()const{returnn==0;}templateclassTintSeqListT::Length()const{returnn;}templateclassTboolSeqListT::Find(inti,T&x)const{9if(i0||in-1){coutOutofBoundsendl;returnfalse;}x=elements[i];returntrue;}templateclassTintSeqListT::Search(Tx)const{for(intj=0;jn;j++){if(elements[j]==x){returnj;}}return-1;}templateclassTboolSeqListT::Insert(inti,Tx)10{if(i-1||in-1){coutOutofBoundsendl;returnfalse;}if(n==maxLength){coutOverFlowendl;returnfalse;}for(intj=n-1;ji;j--){elements[j+1]=elements[j];}elements[i+1]=x;n++;returntrue;}templateclassTboolSeqListT::Delete(inti){11if(!n){coutUnderFlowendl;returnfalse;}if(i0||in-1){coutOutofBoundsendl;returnfalse;}for(intj=i+1;jn;j++){elements[j-1]=elements[j];}n--;returntrue;}templateclassTboolSeqListT::Update(inti,Tx){if(i0||in-1){12coutOutofBoundsendl;returnfalse;}elements[i]=x;returntrue;}templateclassTvoidSeqListT::Output(ostream&out)const{for(inti=0;in;i++){outelements[i]'';}outendl;}templateclassTvoidSeqListT::Reverse(){intm=n/2;for(intj=0;jm;j++){Ttemp=elements[j];13elements[j]=elements[n-1-j];elements[n-1-j]=temp;}}templateclassTboolSeqListT::DeleteX(constT&x){intflag=n;for(inti=0;in;i++){if(elements[i]==x){for(intj=i+1;jn;j++){elements[j-1]=elements[j];}i--;n--;}}if(flagn){14returntrue;}else{returnfalse;}}intmain(){intn,m,k;cout请输入元素个数：;cinn;SeqListinta(n);cout请输入各个元素：;for(inti=0;in;i++){cinm;a.Insert(i-1,m);}cout请输入您想删除的元素：;cink;15coutendl起始:;a.Output(cout);a.Reverse();cout逆置后：;a.Output(cout);a.DeleteX(k);cout删除后：;a.Output(cout);return0;}（3）测试用例和结果：输入顺序表长度为10：16输入十个数分别为1355684259：输入要删除的元素5：172、多项式的算术运算（1）核心算法及流程图○1设计带表头的单链表表示的多项式类，实现书本上的各个运算：思路：在书本上的带表头的循环单链表的代码基础上进行一些修改。代码的修改部分已在“完整代码”中注释了出来○2增加成员函数voidPolyMul(Polynominal&r)，并重载*运算符思路：将乘数多项式的每一项分别与被乘数多项式的所有项分别相乘（系数相乘，指数相加），得到中间多项式，再调用多项式相加的函数将这些中间多项式全部加起来形成结果多项式。代码：voidPolynominal::PolyMul(Polynominal&r){Polynominalresult;Term*res=result.theList;res=res-InsertAfter(0,0);Term*q,*p;for(q=theList-link;q;q=q-link){Polynominaltemp;Term*s=temp.theList;for(p=r.theList-link;p;p=p-link)18{s=s-InsertAfter(q-coef*p-coef,q-exp+p-exp);}result.PolyAdd(temp);}q=theList-link;while(q){theList-link=q-link;deleteq;q=theList-link;}q=theList;for(res=result.theList-link;res;res=res-link){q=q-InsertAfter(res-coef,res-exp);}}Polynominal&operator*(Polynominal&a,Polynominal&b){a.PolyMul(b);returna;}19实验报告流程图：（2）完整代码：#includeiostreamusingnamespacestd;classTerm{20public: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;}Term::Term(intc,inte,Term*nxt){coef=c;exp=e;link=nxt;21}Term*Term::InsertAfter(intc,inte){link=newTerm(c,e,link);returnlink;}ostream&operator(ostream&out,constTerm&val){if(val.coef==0){returnout;}outval.coef;switch(val.exp){case0:break;case1:outX;break;default:outXval.exp;break;}returnout;}classPolynominal22{public:Polynominal();~Polynominal();voidAddTerms(istream&in);voidOutput(ostream&out)const;voidPolyAdd(Polynominal&r);voidPolyMul(Polynominal&r);private:Term*theList;friendostream&operator(ostream&,constPolynominal&);friendistream&operator(istream&,Polynominal&);friendPolynominal&operator+(Polynominal&,Polynominal&);};Polynominal::Polynominal(){theList=newTerm(0,-1);theList-link=NULL;//修改部分}Polynominal::~Polynominal(){Term*p=theList-