數(shù)據(jù)結構實驗報告66363.doc

實驗報告實驗名稱：線性表的基本運算及多項式的算術運算 班級： 姓名： 學號: 日期：一、問題描述1.實驗目的和要求a.掌握線性表的插入、刪除、查找等基本操作設計與實現(xiàn)b.學習利用線性表提供的接口去求解實際問題c.熟悉線性表的的存儲方法2.實驗任務： a.實現(xiàn)順序表和單鏈表的基本運算，多項式的加法和乘法算術運算。 b.能夠正確演示線性表的查找、插入、刪除運算。實現(xiàn)多項式的加法和乘法運算操作。3. 實驗內容：a.實現(xiàn)順序表和單鏈表的基本運算b.輸入并建立多項式；輸出多項式；多項式相加.(可利用單鏈表或單循環(huán)鏈表實現(xiàn)之)。二 程序設計 1.類的層次結構：線性表的基本運算程序中包括三個文件，分別為： linearlist.h，seqlist.h，LinearListMain.cpp。其中順序表類seqlist.h中，私有段封裝了兩個私有數(shù)據(jù)成員maxLenght和elements，同時繼承了LinearList類中的n，分別存儲表中元素最多個數(shù)，元素和元素的實際個數(shù)。多項式的加法和乘法算術運算程序中包括了三個文件，分別為Polynominal.h，Term.h，main.cpp。其中項結點類Team中定義了三個私有數(shù)據(jù)域，即系數(shù)coef、指數(shù)exp和指向下一個項結點的指針域link并且polynominal被聲明成了項結點類Team的友元。多項式加法 多項式乘法2.實驗原理： 以線性表來描述一元多項式，存儲結構采用單鏈表，每個結點存儲的多項式中某一項的系數(shù)和指數(shù)，建立單鏈表時指數(shù)高的結點列于指數(shù)低的 結點之后，即線性表的元素按指數(shù)遞增有序排列。 3.思想算法：以線性表來描述一元多項式，存儲結構采用單鏈表，每個結點存儲的多項式中某一項的系數(shù)和指數(shù)，建立單鏈表時指數(shù)高的結點列于指數(shù)低的結點之后，即線性表的元素按指數(shù)遞增有序排列。 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 .結果分析線性表的基本運算程序：通過程序可以進行查找某一個數(shù)據(jù)、插入