数据结构实验报告66363.doc

实验报告实验名称：线性表的基本运算及多项式的算术运算 班级： 姓名： 学号: 日期：一、问题描述1.实验目的和要求a.掌握线性表的插入、删除、查找等基本操作设计与实现b.学习利用线性表提供的接口去求解实际问题c.熟悉线性表的的存储方法2.实验任务： a.实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。 b.能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。3. 实验内容：a.实现顺序表和单链表的基本运算b.输入并建立多项式；输出多项式；多项式相加.(可利用单链表或单循环链表实现之)。二 程序设计 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）。三 .程序代码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; q=q1-link; while (p-exp=0) while (p-expexp) q1=q; q=q-link; if(p-exp=q-exp) q-coef=q-coef+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:PolyMulti(Polynominal& r) Term *q,*q1=theList,*p; q=q1-link; while(q-exp=0) p=r.theList-link; 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;四、测试与调试1. 测试用例和结果2 .结果分析线性表的基本运算程序：通过程序可以进行查找某一个数据、插入