线性表的基本运算及多项式的算术计算重点讲义资料(共33页).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 <class T>void SeqList<T>:Reverse() int m=n/2; for(int j=0;j<m;j+) T temp=elementsj; elementsj=elementsn-1-j; elementsn-1-j=temp; 流程图： 删除表中所有元素值等于x的元素：思路：遍历顺序表，没搜索到一次x，就将其后所有结点前移，考虑到x连续存在的情况，将所有结点前移之后，i自减，再循环进行。代码：template <class T>bool SeqList<T>:DeleteX(const T &x) int flag=n; for(int i=0;i<n;i+) if(elementsi=x) for(int j=i+1;j<n;j+) elementsj-1=elementsj; i-; n-; if(flag<n) return true; else return false; 流程图： （2） 完整代码：#include <iostream>using namespace std;template <class T>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 <class T>SeqList<T>:SeqList(int mSize) maxLength=mSize; elements=new TmaxLength; n=0;template <class T>bool SeqList<T>:IsEmpty()const return n=0;template <class T>int SeqList<T>:Length()const return n;template <class T>bool SeqList<T>:Find(int i,T& x)const if(i<0|i>n-1) cout<<"Out of Bounds"<<endl; return false; x=elementsi; return true;template <class T>int SeqList<T>:Search(T x)const for(int j=0;j<n;j+) if(elementsj=x) return j; return -1;template <class T>bool SeqList<T>:Insert(int i,T x) if(i<-1|i>n-1) cout<<"Out of Bounds"<<endl; return false; if(n=maxLength) cout<<"OverFlow"<<endl; return false; for(int j=n-1;j>i;j-) elementsj+1=elementsj; elementsi+1=x; n+; return true;template <class T>bool SeqList<T>:Delete(int i) if(!n) cout<<"UnderFlow"<<endl; return false; if(i<0|i>n-1) cout<<"Out of Bounds"<<endl; return false; for(int j=i+1;j<n;j+) elementsj-1=elementsj; n-; return true;template <class T>bool SeqList<T>:Update(int i,T x) if(i<0|i>n-1) cout<<"Out of Bounds"<<endl; return false; elementsi=x; return true;template <class T>void SeqList<T>:Output(ostream& out)const for(int i=0;i<n;i+) out<<elementsi<<' ' out<<endl;template <class T>void SeqList<T>:Reverse() int m=n/2; for(int j=0;j<m;j+) T temp=elementsj; elementsj=elementsn-1-j; elementsn-1-j=temp; template <class T>bool SeqList<T>:DeleteX(const T &x) int flag=n; for(int i=0;i<n;i+) if(elementsi=x) for(int j=i+1;j<n;j+) elementsj-1=elementsj; i-; n-; if(flag<n) return true; else return false; int main() int n,m,k; cout<<"请输入元素个数：" cin>>n; SeqList<int> a(n); cout<<"请输入各个元素：" for(int i=0;i<n;i+) cin>>m; a.Insert(i-1,m); cout<<"请输入您想删除的元素：" cin>>k; cout<<endl<<"起始: " a.Output(cout); a.Reverse(); cout<<"逆置后：" a.Output(cout); a.DeleteX(k); cout<<"删除后：" a.Output(cout); return 0;（3）测试用例和结果： 输入顺序表长度为10： 输入十个数分别为1 3 5 5 6 8 4 2 5 9 ：输入要删除的元素 5 ：2、多项式的算术运算（1）核心算法及流程图设计带表头的单链表表示的多项式类，实现书本上的各个运算： 思路：在书本上的带表头的循环单链表的代码基础上进行一些修改。代码的修改部分已在“完整代码”中注释了出来增加成员函数void PolyMul(Polynominal& r)，并重载*运算符思路：将乘数多项式的每一项分别与被乘数多项式的所有项分别相乘（系数相乘，指数相加），得到中间多项式，再调用多项式相加的函数将这些中间多项式全部加起来形成结果多项式。代码：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); Polynominal& operator *(Polynominal &a,Polynominal &b) a.PolyMul(b);return a;实 验 报 告流程图： （2）完整代码：#include <iostream>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; out<<val.coef; switch(val.exp) case 0:break; case 1:out<<"X"break; default:out<<"X"<<val.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<<(ostream &,const Polynominal &); friend istream& 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(;) cout<<"Input a term(coef,exp):n"<<endl; cin>>c>>e; if(e<0)break; q=q->InsertAfter(c,e); void Polynominal:Output(ostream& out)const int first=1; Term *p=theList->link; cout<<"The polynominal is:n"<<endl; for(;p;p=p->link)/修改部分 if(!first&&(p->coef>0) out<<"+" first=0; out<<*p; cout<<"n"<<endl;void Polynominal:PolyAdd(Polynominal& r) Term *q,*q1=theList,*p; p=r.theList->link; q=q1->link; while(p&&p->exp>=0)/修改部分 while(p->exp<q->exp) 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 <<(ostream &out,const Polynominal &x) x.Output(out);return out;istream& 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 p,q; int a; cout<<"1、多项式相加 2、多项式相乘 请选择功能：" cin>>a; switch(a) case 1: cin>>p; cout<<p; cin>>q; cout<<q; q=q+p; cout<<q; break; case 2: cin>>p; cout<<p; cin>>q; cout<<q; q=q*p; cout<<q; break; return 0;（3）测试用例及结果： 选择多项式相加功能： 输入5x5+4x3： 输 输入4x5+2x3，并求出多项式的和：选择多项式相乘的功能：输入4x3+3x2:输入5x5+6x3+2x2, 输出多项式的乘积： 四、实验小结（包括问题和解决方法、心得体会、意见与建议等）这次实验可以被分为两个问题，线性表的基本运算和多项式的算术运算。主要是要求编写出三个函数，其中，顺序表的逆置非常简单，删除顺序表中所有的x这一函数只要注意到x可能连续存在的情况也就没什么问题了。在编写多项式乘法的函数时，由于最初听课时没有将多项式运算那一部分作为重点去学习，在对带表头的非循环链表的知识使用时总是出错，但是我在静下心来仔细阅读理解从头到尾的完整代码之后，终于理清了这些知识的关系，并成功地编写出了多项式相乘的代码。这次实验让我明白了学过的知识要经常复习，遇到问题不能急躁，要静下心来解决，也让我更加深入地理解了线性表数据结构，更加清楚了线性表的顺序和链接两种存储的方式，体会到了线性表功能的强大，加深了对重载等C+语言的理解和使用。以后我将更加认真学习数据结构，并且更多地将数据结构的知识运用起来。 五、指导教师评语 成 绩批阅人日 期