數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告66363.doc

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