數(shù)據(jù)結(jié)構(gòu)實驗報告66363.doc

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