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

实 验 报 告（ / 学年 第 一 学期）课程名称数据结构A实验名称线性表的基本运算及多项式的算术计算实验时间年月日指导单位指导教师学生姓名班级学号学院(系)专 业实 验 报 告实验名称线性表的基本运算及多项式的算术计算指导教师实验类型上机实验学时2实验时间一、 实验目的和要求实验目的：1、深入理解线性表数据结构，掌握线性表的顺序和链接两种存储方式。2、熟练掌握顺序表的各种基本操作。3、学会使用线性表解决应用问题的方法。4、加深对抽象类模板、类的继承、代码重用等C+知识的理解和使用。内容和要求：1、在顺序表类中增加成员函数void Reverse（），实现顺序表逆置。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-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; 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; 流程图： （2） 完整代码：#include using namespace std;template class SeqListpublic: 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; int n;template SeqList:SeqList(int mSize) maxLength=mSize; elements=new TmaxLength; 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 -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)const for(int i=0;in;i+) outelementsi ; outendl;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; 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; SeqList 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-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); Polynominal& operator *(Polynominal &a,Polynominal &b) a.PolyMul(b);return a;实 验 报 告流程图： （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;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 PolyMul(Polynominal& r);private: Term* theList; friend ostream & operator(istream&,Polynominal &); friend Polynominal& operator +(Polynominal &,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 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&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: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 temp; 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& 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.PolyMul(b);return a;int main() Polynominal