线性表的基本运算及多项式的算术计算重点讲义资料(共33页).doc

《线性表的基本运算及多项式的算术计算重点讲义资料(共33页).doc》由会员分享，可在线阅读，更多相关《线性表的基本运算及多项式的算术计算重点讲义资料(共33页).doc（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上实 验 报 告（ / 学年 第 一 学期）课程名称数据结构A实验名称线性表的基本运算及多项式的算术计算实验时间年月日指导单位指导教师学生姓名班级学号学院(系)专 业专心-专注-专业实 验 报 告实验名称线性表的基本运算及多项式的算术计算指导教师实验类型上机实验学时2实验时间一、 实验目的和要求实验目的：1、深入理解线性表数据结构，掌握线性表的顺序和链接两种存储方式。2、熟练掌握顺序表的各种基本操作。3、学会使用线性表解决应用问题的方法。4、加深对抽象类模板、类的继承、代码重用等C+知识的理解和使用。内容和要求：1、在顺序表类中增加成员函数void Reverse（），

2、实现顺序表逆置。2、在顺序表类中增加成员函数bool DeleteX(const T &x),删除表中所有元素值等于x的元素。若存在则删除之且返回true，否则返回false。3、编写main函数，调用上述新增函数。4、设计带表头结点的单链表表示的多项式类，实现各个运算。5、增加成员函数void PolyMul(Polynominal &r),并重载*运算符。6、编写main函数，测试多项式类的各个运算。二、实验环境(实验设备)硬件：PC软件：Code:Blocks (C+)三、实验原理及内容1、线性表的基本运算（1）核心算法及流程图顺序表逆置：思路：将顺序表中第j个结点中的元素与第（n-1-

3、j）个结点中的元素替换，从第一个结点开始，共进行（n/2取整）次。代码：template void SeqList:Reverse() int m=n/2; for(int j=0;jm;j+) T temp=elementsj; elementsj=elementsn-1-j; elementsn-1-j=temp; 流程图： 删除表中所有元素值等于x的元素：思路：遍历顺序表，没搜索到一次x，就将其后所有结点前移，考虑到x连续存在的情况，将所有结点前移之后，i自减，再循环进行。代码：template bool SeqList:DeleteX(const T &x) int flag=n; f

4、or(int i=0;in;i+) if(elementsi=x) for(int j=i+1;jn;j+) elementsj-1=elementsj; i-; n-; if(flagn) return true; else return false; 流程图： （2） 完整代码：#include using namespace std;template class SeqListpublic: SeqList(int mSize); SeqList() delete elements; bool IsEmpty()const; int Length()const; bool Find(in

5、t 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; int n;template SeqList:SeqList(int mSize) maxLength=mSize; elements=new TmaxLength;

6、n=0;template bool SeqList:IsEmpty()const return n=0;template int SeqList:Length()const return n;template bool SeqList:Find(int i,T& x)const if(in-1) coutOut of Boundsendl; return false; x=elementsi; return true;template int SeqList:Search(T x)const for(int j=0;jn;j+) if(elementsj=x) return j; return

7、 -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;

8、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)const for(int i=0;in;i+) outelementsi ; outendl;template void SeqList:Reverse() int m=n

9、/2; for(int j=0;jm;j+) T temp=elementsj; elementsj=elementsn-1-j; elementsn-1-j=temp; template bool SeqList:DeleteX(const T &x) int flag=n; for(int i=0;in;i+) if(elementsi=x) for(int j=i+1;jn;j+) elementsj-1=elementsj; i-; n-; if(flagn) return true; else return false; int main() int n,m,k; coutn; Se

10、qList a(n); cout请输入各个元素：; for(int i=0;im; a.Insert(i-1,m); coutk; coutendl起始: ; a.Output(cout); a.Reverse(); cout逆置后：; a.Output(cout); a.DeleteX(k); coutInsertAfter(0,0); Term *q,*p; for(q=theList-link;q;q=q-link) Polynominal temp; Term *s=temp.theList; for(p=r.theList-link;p;p=p-link) s=s-InsertAft

11、er(q-coef*p-coef,q-exp+p-exp); result.PolyAdd(temp); q=theList-link; while(q) theList-link=q-link; delete q; 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);return a;实 验 报

12、告流程图： （2）完整代码：#include using namespace std;class Termpublic: 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

13、;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; retu

14、rn out;class Polynominalpublic: Polynominal(); Polynominal(); void AddTerms(istream& in); void Output(ostream& out)const; void PolyAdd(Polynominal& r); void PolyMul(Polynominal& r);private: Term* theList; friend ostream & operator(istream&,Polynominal &); friend Polynominal& operator +(Polynominal &

15、,Polynominal &);Polynominal:Polynominal() theList=new Term(0,-1); theList-link=NULL;/修改部分Polynominal:Polynominal() Term* p=theList-link; while(p)/修改部分 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 te

16、rm(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; q=q1-link; while(p&p-exp=0)/修改部分 while(p-expexp) q1=q; q=q-link; if(p-exp=q-exp) q-coef=q-coef

17、+p-coef; if(q-coef=0) q1-link=q-link; delete(q); q=q1-link; else q1=q; q=q-link; else q1=q1-InsertAfter(p-coef,p-exp); p=p-link; void Polynominal:PolyMul(Polynominal &r) Polynominal result; Term *res=result.theList; res=res-InsertAfter(0,0); Term *q,*p; for(q=theList-link;q;q=q-link) Polynominal tem

18、p; Term *s=temp.theList; for(p=r.theList-link;p;p=p-link) s=s-InsertAfter(q-coef*p-coef,q-exp+p-exp); result.PolyAdd(temp); q=theList-link; while(q) theList-link=q-link; delete q; q=theList-link; q=theList; for(res=result.theList-link;res;res=res-link) q=q-InsertAfter(res-coef,res-exp); ostream& ope

19、rator (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.PolyMul(b);return a;int main() Polynominal p,q; int a; couta; switch(a) case 1: cinp; coutq; coutq; q=q+p;

20、 coutp; coutq; coutq; q=q*p; coutq; break; return 0;（3）测试用例及结果： 选择多项式相加功能： 输入5x5+4x3： 输 输入4x5+2x3，并求出多项式的和：选择多项式相乘的功能：输入4x3+3x2:输入5x5+6x3+2x2, 输出多项式的乘积： 四、实验小结（包括问题和解决方法、心得体会、意见与建议等）这次实验可以被分为两个问题，线性表的基本运算和多项式的算术运算。主要是要求编写出三个函数，其中，顺序表的逆置非常简单，删除顺序表中所有的x这一函数只要注意到x可能连续存在的情况也就没什么问题了。在编写多项式乘法的函数时，由于最初听课时没有将多项式运算那一部分作为重点去学习，在对带表头的非循环链表的知识使用时总是出错，但是我在静下心来仔细阅读理解从头到尾的完整代码之后，终于理清了这些知识的关系，并成功地编写出了多项式相乘的代码。这次实验让我明白了学过的知识要经常复习，遇到问题不能急躁，要静下心来解决，也让我更加深入地理解了线性表数据结构，更加清楚了线性表的顺序和链接两种存储的方式，体会到了线性表功能的强大，加深了对重载等C+语言的理解和使用。以后我将更加认真学习数据结构，并且更多地将数据结构的知识运用起来。 五、指导教师评语 成 绩批阅人日 期