南邮数据结构实验一

实验报告（2014/2015学年第二学期）课程名称数据结构实验名称线性表的基本运算及多项式的算术运算实验时间2015年9月28日指导单位计算机科学与技术系指导教师黄海平学生姓名陈明阳班级学号Q14010119学院(系)贝尔英才专业信息科技强化班1实验报告实验名称线性表的基本运算及多项式的算术运算指导教师黄海平实验类型验证实验学时4实验时间9.28一、实验目的和要求内容：实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。要求：能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。二、实验环境(实验设备)VSUALSTUDIO20152三、实验原理及内容LinearlistseqlistLA,LB函数调用数据类型如下图源码：Linearlist.h:#includeiostreamusingnamespacestd;templateclassTclassLinearList{public:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolFind(inti,T&x)const=0;virtualintSearch(Tx)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;virtualboolUpdate(inti,Tx)=0;virtualvoidOutput(ostream&out)const=0;protected:intn;};Seqlist.h:#includelinearlist.htemplateclassT3classSeqList:publicLinearListT{public:SeqList(intmSize);~SeqList(){delete[]elements;}boolIsEmpty()const;intLength()const;boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);boolUpdate(inti,Tx);voidOutput(ostream&out)const;private:intmaxLength;T*elements;};templateclassTSeqListT::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];n=0;}templateclassTboolSeqListT::IsEmpty()const{returnn==0;}templateclassTintSeqListT::Length()const{returnn;}templateclassTboolSeqListT::Find(inti,T&x)const{if(i0||in-1){coutoutofboundsendl;returnfalse;}x=elements[i];returntrue;4}templateclassTintSeqListT::Search(Tx)const{for(intj=0;jn;j++)if(elements[j]==x)returnj;return-1;}templateclassTboolSeqListT::Insert(inti,Tx){if(i-1||in-1){coutoutofboundsendl;returnfalse;}if(n==maxLength){coutoverflowendl;returnfalse;}for(intj=n-1;ji;j--)elements[j+1]=elements[j];elements[i+1]=x;n++;returntrue;}templateclassTboolSeqListT::Delete(inti){if(i0||in-1){coutoutofboundsendl;returnfalse;}if(!n){coutoverflowendl;returnfalse;}for(intj=i+1;jn;j--)elements[j-1]=elements[j];n--;returntrue;}templateclassT5boolSeqListT::Update(inti,Tx){if(i0||in-1){coutoutofboundsendl;returnfalse;}elements[i]=x;returntrue;}templateclassTvoidSeqListT::Output(ostream&out)const{for(inti=0;in;i++)outelements[i];outendl;}源.cpp:#includeseqlist.hconstintSIZE=20;voidmain(){SeqListintLA(SIZE);inti=0;for(i=0;i5;i++)LA.Insert(i-1,i);LA.Insert(-1,10);LA.Output(cout);}实现在线性表LA中插入0-4然后在一开始插入10运行截图如下：6多项式实验：定义类如下7重构函数如下：源码：#includeiostreamusingnamespacestd;classTerm{public:Term(intc,inte);Term(intc,inte,Term*nxt);Term*InsertAfter(intc,inte);private:intcoef;intexp;Term*link;friendostream&operator(ostream&,constTerm&);friendclassPolynominal;};Term::Term(intc,inte):coef(c),exp(e){link=0;}Term::Term(intc,inte,Term*nxt):coef(c),exp(e){link=nxt;}Term*Term::InsertAfter(intc,inte){link=newTerm(c,e,link);returnlink;}ostream&operator(ostream&out,constTerm&val){if(0==val.coef)8returnout;if(1!=val.coef)outval.coef;switch(val.exp){case0:break;case1:outX;break;default:outX^val.exp;break;}returnout;}classPolynominal{public:Polynominal();~Polynominal();voidAddTerms(istream&in);voidOutput(ostream&out)const;voidPolyAdd(Polynominal&r);voidPolyMul(Polynominal&r);private:Term*theList;friendostream&operator(ostream&,constPolynominal&);friendistream&operator(istream&,Polynominal&);friendPolynominal&operator+(Polynominal&,Polynominal&);friendPolynominal&operator*(Polynominal&,Polynominal&);};Polynominal::Polynominal(){theList=newTerm(0,-1);//头结点theList-link=NULL;//单链表尾结点指针域为空}Polynominal::~Polynominal(){Term*p=theList-link;while(p!=NULL){theList-link=p-link;deletep;p=theList-link;}9deletetheList;}voidPolynominal::AddTerms(istream&in){Term*q=theList;intc,e;for(;;){coutInputaterm(coef,exp):\nendl;cince;q=q-InsertAfter(c,e);if(0=e)break;}}voidPolynominal::Output(ostream&out)const{intfirst=1;Term*p=theList-link;for(;p!=NULL&&p-exp=0;p=p-link){if(!first&&(p-coef0))out+;first=0;out*p;}coutendl;}voidPolynominal::PolyAdd(Polynominal&r){Term*q,*q1=theList,*p;//q1指向表头结点p=r.theList-link;//p指向第一个要处理的结点q=q1-link;//q1是q的前驱，p和q就指向两个当前进行比较的项while(p!=NULL&&p-exp=0)//对r的单循环链表遍历，知道全部结点都处理完{while(p-expq-exp)//跳过q-exp大的项{q1=q;q=q-link;}if(p-exp==q-exp)//当指数相等时，系数相加{q-coef=q-coef+p-coef;10if(q-coef==0)//若相加后系数为0，则删除q{q1-link=q-link;delete(q);q=q1-link;//重置q指针}else{q1=q;//若相加后系数不为0，则移动q1和qq=q-link;}}else//pexpq-exp的情况q1=q1-InsertAfter(p-coef,p-exp);//以p的系数和指数生成新结点，插入q1后p=p-link;}}voidPolynominal::PolyMul(Polynominal&r){Polynominalresult;//定义相乘后的数据Term*n=result.theList;//n指向result的头结点n=n-InsertAfter(0,0);//在result的头结点后插入新结点，系数指数均为0Term*p=r.theList-link;//p指向第一个要处理的结点while(p-exp=0)//对r的单循环链表遍历{Polynominaltmp;//存储某段相乘后的数据Term*m=tmp.theList;//m指向tmp的头结点Term*q=theList-link;//q指向表头结点的后继结点while(q-exp=0)//对当前对象的单循环环链表遍历{m=m-InsertAfter((p-coef)*(q-coef),(p-exp)+(q-exp));//生成新结点插入n后q=q-link;}result.PolyAdd(tmp);//将temp加到result上p=p-link;}Term*q=theList-link;//q指向表头结点的后继结点while(q!=NULL)//删除原对象的所有数据{theList-link=q-link;deleteq;q=theList-link;11}q=theList;q=q-InsertAfter(0,0);PolyAdd(result);//将result加到当前对象上}ostream&operator(ostream