实验报告1线性表及表达式

实 验 报 告（ 学年 第学期）课程名称数据结构A 实验名称 实验一 线性表的基本运算及多项式的算术运算实验时间年月日指导单位指导教师学生姓名班级学号学院(系)专 业实 验 报 告实验名称 实验一 线性表的基本运算及多项式的算术运算指导教师实验类型 验证实验学时 实验时间一、 实验目的和要求（1）深入理解线性表数据结构，掌握线性表的顺序和链接两种存储表示方法。（2）熟练掌握顺序表的各种基本操作。（3）学会使用线性表解决应用问题的方法。（4）加深对抽象模板类。类的继承、代码重用、重载等C+语言机制的理解和使用。二、实验环境(实验设备) 硬件: 微型计算机 软件: Microsoft Visual C+6.0三、实验原理及内容 实验题一：线性表操作（1）在顺序表类SeqList中增加成员函数void Reverse( )，实现顺序表的逆置。（2）在顺序表类SeqList中增加成员函数bool DeleteX(const T &x)，删除表中所有元素值等于x的元素。若表中存在这样的元素则删除之，且函数返回true；否则函数返回false。（3）编写main函数，调用上述函数测试其功能。源代码：实 验 报 告#include template class LinearListpublic: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 void Output(ostream& out) const=0; virtual void Reverse()=0;virtual bool DeleteX(const T&x)=0;protected:int n;template class Seqlist:public LinearListpublic:Seqlist(int mSize);Seqlist() delete elements; 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 DeleteX(const T&x);private:int maxLength;T *elements;template Seqlist:Seqlist(int mSize)maxLength=mSize;elements=new TmaxLength;n=0;template bool Seqlist:IsEmpty() constreturn n=0;template int Seqlist:Length() constreturn n;template bool Seqlist:Find(int i,T& x) constif(in-1)coutOut of Boundsendl; return false; x=elementsi; return true; 实 验 报 告template int Seqlist:Search(T x) constfor(int j=0;jn;j+)if(elementsj=x) return j;return -1;template bool Seqlist:Insert(int i,T x)if(in-1)coutOut of Boundsendl; return false;if(n=maxLength)coutOverFlowi;j-) elementsj+1=elementsj;elementsi+1=x;n+; return true;template bool Seqlist:Delete(int i) if(!n)coutUnderFlowendl; return false;if(in-1)coutOut of Boundsendl; return false;实 验 报 告for(int j=i+1;jn;j+) elementsj-1=elementsj;n-;return true;template bool Seqlist:Update(int i,T x)if(in-1)coutOut of Boundsendl; return false;elementsi=x;return true;template void Seqlist:Output(ostream& out) constfor(int i=0;in;i+) outelementsi ;outendl;template /对线性表进行逆置void Seqlist:Reverse()T t;for(int i=0;in/2;i+)（第一个和最后一个交换，以此类推对线性表进行逆置）t=elementsi;elementsi=elementsn-i-1; elementsn-i-1= =t;template bool Seqlist:DeleteX(const T&x)实 验 报 告if(Search(x)=-1)return false;for(int i=0;in;i+)if(elementsi=x)Delete(i);i-;（这样才能保证删除所有相同的元素）return true;template void Union(Seqlist &LA,Seqlist LB)T x;for(int i=0;iLB.Length();i+)LB.Find(i,x);if(LA.Search(x)=-1)LA.Insert(LA.Length()-1,x);const int SIZE=20;void main()/主函数用于测试对线性表的各种操作Seqlist LA(SIZE);/Seqlist LB(SIZE);for(int i=0;i10;i+) LA.Insert(i-1,i); LA.Output(cout);实 验 报 告LA.Insert(2,2); LA.Insert(2,2); LA.Insert(2,2); LA.Output(cout); LA.DeleteX(2); LA.Output(cout);LA.Reverse();/for(i=3;i8;i+) LB.Insert(i-4,i); /LB.Insert(-1,0); /LB.Insert(3,2); /LB.Insert(LB.Length()-1,4); /Union(LA,LB); LA.Output(cout);测试结果实 验 报 告实验题二：一元多项式的相加和相乘（1）设计带表头结点的单链表表示的多项式类，结点类单独定义；（2）在多项式类中定义和实现： 多项式的逐项输入，再重载输入流cin； 多项式的相加运算，再重载加法运算符： operator +； 多项式的相乘运算，增加成员函数void PolyMul(Polynominal &r),再重载乘法运算符： operator *； 多项式的输出，再重载输出流cout。（3）实现菜单驱动的main函数，测试多项式加法和乘法运算，要求能： 定义多项式对象，并调用cin建立一个多项式； 调用cout打印(显示)一个多项式； 实现两个多项式相加，将相加后的结果输出； 实现两个多项式相乘，将相乘后的结果输出1.类的层次结构：线性表的基本运算程序中包括三个文件，分别为： linearlist.h，seqlist.h，LinearListMain.cpp。其中顺序表类seqlist.h中，私有段封装了两个私有数据成员maxLenght和elements，同时继承了LinearList类中的n，分别存储表中元素最多个数，元素和元素的实际个数。多项式的加法和乘法算术运算程序中包括了三个文件，分别为Polynominal.h，Term.h，main.cpp。其中项结点类Team中定义了三个私有数据域，即系数coef、指数exp和指向下一个项结点的指针域link并且polynominal被声明成了项结点类Team的友元。 实 验 报 告多项式加法 多项式乘法实 验 报 告2.实验原理： 以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的 结点之后，即线性表的元素按指数递增有序排列。 3.思想算法：以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。 4.算法分析：线性表的基本运算程序的主要算法的算法时间复杂度和空间复杂度为O（n），多项式的加法和乘法算术运算程序的主要算法的时间复杂程度和和空间复杂程度为O（n）。实 验 报 告5.源代码a. 多项式基本运算template class SeqList:public LinearList public: SeqList(int mSize); SeqList() delete elements; 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 ; private: int maxLength; T *elements;SeqList LObj(SIZE);template SeqList:SeqList(int mSize) maxLength=mSize; elements=new TmaxLength; n=0;template bool SeqList:IsEmpty() constreturn n=0实 验 报 告template int SeqList:Length() constreturn n;template bool SeqList:Find(int i,T& x) constif (in-1)coutOut Of Bountsendl; return false;x=elementsi;return true;templateint SeqList:Search(T x) constfor(int j=0;jn;j+)if (elementsj=x) return j;return -1;templatebool SeqList:Insert(int i,T x)if (in-1)coutOut Of Boundsendl; return false; if (n=maxLength)coutOverFlowi;j-)elementsj+1=elementsj;elementsi+1=x; n+;return true;实 验 报 告templatebool SeqList:Delete(int i)if(!n)coutUnderFlowendl; return false;if (in-1)coutOut Of Boundsendl; return false;for (int j=i+1;jn;j+)elementsj-1=elementsj;n-;return true;templatebool SeqList:Update(int i,T x)if (in-1)coutOut Of Boundsendl; return false;elementsi=x;return true;templatevoid SeqList:Output(ostream& out) constfor (int i=0;in;i+)outelementsi ;outendl;B.多项式的加法和乘法#include class Term实 验 报 告public:Term(int c,int e);Term(int c,int e,Term *nxt);Term *InsertAfter(int c, int e);private:int coef; int exp;Term *link;friend ostream & operator(ostream &, const Term &);friend class Polynominal;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)link=new Term(c, e, link);return link;ostream & operator(ostream & out, const Term & val)if(val.coef=0) return out;outval.coef;switch(val.exp)case 0:break;case 1:outx;break;default:outxval.exp;break;实 验 报 告return out;class Polynominalpublic:Polynominal();Polynominal();void AddTerms(istream & in);void Output(ostream & out)const;void PolyAdd(Polynominal & r);void PolyMulti(Polynominal & r);private:Term *theList;friend ostream & operator(istream &, Polynominal &);friend Polynominal & operator+(Polynominal &,Polynominal &); friend Polynominal & operator*(Polynominal &,Polynominal &); ;Polynominal:Polynominal() theList=new Term(0,-1); theList-link=theList; Polynominal:Polynominal() Term *p=theList-link;while(p!=theList)theList-link=p-link;delete p;p=theList-link;delete theList;实 验 报 告void Polynominal:AddTerms(istream & in) Term *q=theList;int c,e;for(;) coutInput a term(coef,exp):nce; if (eInsertAfter(c,e); void Polynominal:Output(ostream& out)const int first=1; Term *p=theList-link; coutThe polynominal is:nlink) if (!first & (p-coef0) out+; first=0; out*p; coutnlink;/p指向第一个要处理的结点 q=q1-link;/q1是q的前驱，p和q就指向两个当前进行比较的项 while (p-exp=0)/对r的单循环链表遍历，直到全部结点处理完 while (p-expexp)/t跳过q-exp大的项 q1=q; q=q-link; if(p-exp=q-exp) /当指数相等时，系数相加实 验 报 告 q-coef=q-coef+p-coef; if(q-coef=0)/若相加后系数为0，则删除q q1-link=q-link; delete(q); q=q1-link;/重置q指针 else q1=q; q=q-link; /若相加后系数不为0，则移动q1和q Else/p-expq-exp的情况 q1=q1-InsertAfter(p-coef,p-exp);/以p的系数和指数生产新结点，插入q1后 p=p-link; void Polynominal:PolyMulti(Polynominal& r) Term *q,*q1=theList,*p; /q1指向表头结点 q=q1-link; /q1是q的前驱，p和q就指向两个当前进行比较的项while(q-exp=0) /对r的单循环链表遍历，直到全部结点处理完 p=r.theList-link; /p指向第一个要处理的结点 while (p-exp=0) q1=q1-InsertAfter(q-coef*p-coef,q-exp+p-exp); p=p-link; q1-link=q-link; delete(q); q=q1-link;ostream& operator (istream& in, Polynominal &x) x.AddTerms(in); return in;Polynominal & operator+(Polynominal &a, Polynominal &b) a.PolyAdd(b); return a;Polynominal & operator*(Polynominal &a, Polynominal &b) a.PolyMulti(b); return a;void main() Polynominal p,q,w; cinp; coutq; coutw; coutw; q=q+p; coutq; w=w*p; coutw;6. 测试用例和结果实 验 报 告实验报告四、实验小结（包括问题和解决方法、心得体会、意见与建议等）1.在实验一中实现线性表的逆置没有多大问题； 删除顺序表中所有元素值等于X的元素时对X的删除可以直接调用已经定义的delete函数而不必再写执行删除的具体代码题目中要求的是删除所有与X相同的元素，没有增加i；时只能删除第一个与X相同的元素，加i-；即简单游方便。在编程时应尽量考虑简单方便的代码。2.关键在于理解整个加法和乘法过程，各个指针的用法，各种情况的分析。还有重載*，和+的重載差不多。五、指导教师评语成 绩批阅人日 期20