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

1、实验报告（ 学年第学期）课程名称数据结构A实验名称 实验一 线性表的基本运算及多项式的算术运算 实验时间年月日指导单位指导教师学生姓名班级学号学院（系）专 业实验报告实验名称实验一线性表的基本运算及 多项式的算术运算指导教师实验类型验证实验学时实验时间一、实验目的和要求(1) 深入理解线性表数据结构，掌握线性表的顺序和链接两种存储表示方法。(2) 熟练掌握顺序表的各种基本操作。(3) 学会使用线性表解决应用问题的方法。(4) 加深对抽象模板类。类的继承、代码重用、重载等C+语言机制的理解和使用。二、实验环境(实验设备)硬件：微型计算机软件：Microsoft Visual C+6.0二、实验原

2、理及内容实验题一：线性表操作(1) 在顺序表类SeqList中增加成员函数 void Reverse()，实现顺序表的逆置。(2) 在顺序表类SeqList中增加成员函数 bool DeleteX(const T &x)，删除表中所有兀素值等于x的元素。若表中存在这样的元素则删除之，且函数返回true ;否则函数返回false。(3) 编写ma in函数，调用上述函数测试其功能。源代码：#in elude template class Lin earListpublic:virtual bool lsEmpty() con st=0;virtual int Len gth() con st=0

3、;virtual bool Fi nd(int i,T& X) con st=0;virtual int Search(T x) con st=0;virtual bool Insert(int i,T x)=0;virtual bool Delete(int i)=0;virtual bool Update(i nt i,T x)=0;virtual void Output(ostrea m& out) con st=0;virtual void Reverse()=0;virtual bool DeleteX(co nst T& x)=0; protected:int n;template

4、 class Seqlist:public Lin earListpublic:Seqlist(i nt mSize);Seqlist() delete eleme nts;bool IsEmpty() con st;int Len gth() con st;bool Fi nd(i nt i,T& X) con st;int Search(T x) con st;bool In sert(i nt i,T x);bool Delete(i nt i);bool Update(int i,T x);void Output(ostream& out) con st;void Reverse。；b

5、ool DeleteX(const T&x);private:int maxLe ngth;T *eleme nts;template Seqlist:Seqlist(i nt mSize)maxLe ngth=mSize;eleme nts=new TmaxLe ngth;n=0;template bool Seqlist:lsEmpty() constretur n n=0;template int Seqlist:Le ngth() constreturn n;template bool Seqlist:Find(int i,T& x) constif(i n-1)coutOut of

6、Boun dse ndl; retur n false;x=eleme ntsi;return true;template int Seqlist:Search(T x) constfor(i nt j=O;j n;j+)if(eleme ntsj=x) retur n j;return -1;template bool Seqlist:I nsert(i nt i,T x)if(i n-1)coutOut of Boun dse ndl; retur n false;if(n=maxLe ngth)coutOverFlowi;j-) eleme ntsj+1=eleme ntsj; elem

7、e ntsi+1=x;n+; retur n true;template bool Seqlist:Delete(int i) if(!n)cout Un derFlowe ndl; retur n false;if(i n-1)coutOut of Boun dse ndl; retur n false;for(i nt j=i+1;j n;j+) eleme ntsj-1=eleme ntsj;n-;return true;template bool Seqlist:Update(int i,T x)if(i n-1)coutOut of Boun dse ndl; retur n fal

8、se;eleme ntsi=x;return true;template void Seqlist:Output(ostrea m& out) constfor(i nt i=0;i n;i+) outeleme ntsi;oute ndl;template 对线性表进行逆置void Seqlist:Reverse()T t;for(i nt i=0;i n/2;i+)(第一个和最后一个交换，以此类推对线性表进行逆置)t=eleme ntsi;eleme ntsi=eleme nts n-i-1;eleme nts n-i-1= =t;template bool Seqlist:DeleteX

9、(co nst T&x)if(Search(x)=-1)return false;for(i nt i=0;i n ;i+)if(eleme ntsi=x)Delete(i);i-;(这样才能保证删除所有相同的元素)return true;template void Un io n(Seqlist &LA,Seqlist LB)T x;for(int i=0;iLB.Length();i+)LB.Fi nd(i,x);if(LA.Search(x)=-1)LA.I nsert(LA .L e ngth()-1,x);const int SIZE=20;void main()主函数用于测试对线性

10、表的各种操作Seqlist LA(SIZE);/Seqlist LB(SIZE);for(i nt i=0;i10;i+)LA.I nsert(i-1,i);LA.Output(cout);LA.I nsert(2,2);LA.I nsert(2,2);LA.I nsert(2,2); LA.Output(cout);LA.DeleteX(2);LA.Output(cout);LA.Reverse();for(i=3;i8;i+) LB.Insert(i-4,i);/LB.I nsert(-1,0);/LB.I nsert(3,2);/LB.I nsert(LB.Le ngth()-1,4);

11、Un io n(LA, LB); LA.Output(cout);测试结果2 2 3 7 Ills 0 03 4 5 6 7 8 9 22234567894 5 6 7 8 ?G 5 4 3 1 0any ley 七。centinue实验题二：一元多项式的相加和相乘(1) 设计带表头结点的单链表表示的多项式类，结点类单独定义；(2) 在多项式类中定义和实现： 多项式的逐项输入，再重载输入流cin ； 多项式的相加运算，再重载加法运算符：operator + ； 多项式的相乘运算，增加成员函数void PolyMul(Polynominal &r),再重载乘法运算符：operator *； 多项

12、式的输出，再重载输出流cout。(3) 实现菜单驱动的 main函数，测试多项式加法和乘法运算，要求能： 定义多项式对象，并调用 cin建立一个多项式； 调用cout打印(显示)一个多项式； 实现两个多项式相加，将相加后的结果输出； 实现两个多项式相乘，将相乘后的结果输出1. 类的层次结构：线性表的基本运算程序中包括三个文件，分别为：lin earlist.h ，seqlist.h ，LinearListMain.cpp。其中顺序表类 seqlist.h 中，私有段圭寸装了两个私有数据成员 maxLenght和elements，同时继承了 LinearList类中的n,分别存储表中元素最多个数

13、，元素和元素的实际个数。多项式的加法和乘法算术运算程序中包括了三个文件，分别为 Polynomin al.h , Term.h, ma in .cpp。其中项结点类 Team中定义了三个私有 数据域，即系数coef、指数exp和指向下一个项结点的指针域link并且 polynominal被声明成了项结点类Team的友元。多项式加法Omy Ifoty * 聃 *gp, *hp.t*.r-maxpY 4M-Jto；iMm hlplcir-rlhp-tl;rerurtiJi;多项式乘法2. 实验原理:以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时

14、指数高的结点列于指数 低的 结点之后，即线性表的元素按指数递增有序排列。3. 思想算法：以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。4. 算法分析：线性表的基本运算程序的主要算法的算法时间复杂度和空间复杂度为0(n)，多项式的加法和乘法算术运算程序的主要算法的时间复杂程度和和空 间复杂程度为0(n)。5.源代码a.多项式基本运算template class SeqList:public Lin earList public:SeqList(i nt mSize);SeqL

15、ist() delete eleme nts; bool lsEmpty() con st;int Len gth() con st;bool Fin d(i nt i,T& x) con st;int Search(T x) con st;bool In sert(i nt i,T x);bool Delete(i nt i);bool Update(int i,T x);void Output(ostrea m& out)c onst ;private:int maxLe ngth;T *eleme nts;SeqList LObj(SIZE);template SeqList:SeqLi

16、st(i nt mSize)maxLe ngth=mSize;eleme nts=new TmaxLe ngth;n=0;template bool SeqList:IsEmpty() constretur n n=0实验报告template int SeqList:Le ngth() constreturn n;template bool SeqList:Find(int i,T& x) constif (in-1)coutOut Of Bou ntse ndl; return false;x=eleme ntsi;return true;templateint SeqList:Search

17、(T x) constfor(i nt j=O;j n;j+)if (eleme ntsj=x) return j;return -1;templatebool SeqList:I nsert(i nt i,T x)if (in-1)coutOut Of Boundsendl; return false;if (n=maxLe ngth)coutOverFlowi;j-)eleme ntsj+1=eleme ntsj;eleme ntsi+1=x; n+;return true;templatebool SeqList:Delete(int i)if(!n)cout Un derFlowe n

18、dl; retur n false;if (i n-1)coutOut Of Bou ndse ndl; return false;for (int j=i+1;j n ;j+)eleme ntsj-1=eleme ntsj;n-;return true;templatebool SeqList:Update(int i,T x)if (i n-1)coutOut Of Boundsendl; return false;eleme ntsi=x;return true;templatevoid SeqList:Output(ostrea m& out) constfor (int i=0;i

19、n ;i+)outeleme ntsi; oute ndl;B.多项式的加法和乘法#in clude class Term public:Term(i nt c,i nt e);Term(i nt c,i nt e,Term *n xt);Term *1 nsertAfter(i nt c, i nt e);private:int coef;int exp;Term *li nk;friend ostream & operator(ostream &, const Term &); frie nd class Polynomin al;Term:Term(i nt c,int e):coef(

20、c),exp(e)lin k=0;Term:Term(i nt c,i nt e,Term *n xt):coef(c),exp(e)link=n xt;Term *Term:I nsertAfter(i nt c, i nt e)link=new Term(c, e, li nk);return link;ostream & operator(ostream & out, const Term & val)if(val.coef=0) retur n out;outval.coef;switch(val.exp)case 0:break;case 1:outx;break; default:

21、outxAval.exp;break;return out;class Polynominalpublic:Polynomin al();Po lynomin al();void AddTerms(istream & in);void Output(ostream & out)c on st;void PolyAdd(Polynominal & r);void PolyMulti(Poly nominal & r);private:Term *theList;friend ostream & operatorli nk=theList;Polynomin al:Po lynomin al()

22、Term *p=theList-li nk;while(p!=theList)theList-li nk=p-li nk;delete p; p=theList-li nk;delete theList;void Poly no mi nal:AddTerms(istream & in) Term *q=theList;int c,e;for(;) coutl nput a term(coef,exp):n ce;if (eI nsertAfter(c,e);void Polynomin al:Output(ostrea m& out)c onstint first=1;Term *p=the

23、List-li nk;coutThe polynominal is:nli nk) 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-li nk;if(p-exp=q-exp) /当指数相等时，系数相加 q_coef=q_coef+p_coef;if(q-coef=0)若相加后系数为 0,则删

24、除qq1-li nk=q-li nk; delete(q);q=q1-link; 重置 q 指针else q1=q; q=q-link; /若相加后系数不为 0，则移动q1和qElse/p-expq-exp 的情况q1后q仁q1-lnsertAfter(p-coef,p-exp);以p的系数和指数生产新结点，插入 p=p-li nk;void Poly nomi nal:PolyMulti(Poly nomi nal& r)Term *q,*q1=theList,*p; /q1指向表头结点q=q1-link; /q1是q的前驱，p和q就指向两个当前进行比较的项while(q-exp=0) /对

25、r的单循环链表遍历，直到全部结点处理完p=r.theList-link; /p指向第一个要处理的结点while (p-exp=0)q1=q1- In sertAfter(q-coef*p-coef,q-exp+p-exp); p=p-li nk;q1-li nk=q-li nk;delete(q);q=q1-li nk;ostream& operator (istream& in. Polynominal &x) x.AddTerms(i n);return in;Polynominal & operator+(Po nominal &a, Polynominal &b) a.P olyAdd(b);return a;Polynominal & operator