南郵數(shù)據(jù)結(jié)構(gòu)上機實驗一線性表的基本運算和多項式的基本運算資料

1、實驗報告2015 / 2016 學(xué)年 第二學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu) A實驗名稱線性表的基本運算和多項式的基本運算實驗時間2016年3月10 日指導(dǎo)單位計算機科學(xué)與技術(shù)系指導(dǎo)教師駱健學(xué)生姓名學(xué)院(系)管理學(xué)院班級學(xué)號專業(yè)信息管理與信息系統(tǒng)實習(xí)題名:線性表的基本運算班級姓名學(xué)號日期2016.03.10一、問題描述深入理解線性表數(shù)據(jù)結(jié)構(gòu), 熟練掌握順序表的各種基本操作。在順序表類SeqList中增加成員函數(shù)void Reverse()，實現(xiàn)順序表的逆置；在順序表類SeqList中增加成員函數(shù) bool DeleteX(const T &x),刪除表中所有元素值等于x 元素。若表中存在這樣的元素，則刪除

2、之，且函數(shù)返回true ，否則函數(shù)返回false 。二、概要設(shè)計文件 Inverse.cpp中定義了Linearlist類 , SeqList類繼承 Linearlist序表類 SeqList中通過函數(shù)void Reverse()實現(xiàn)順序表的逆置，通過函數(shù)DeleteX(const T &x),刪除表中所有元素值等于x 元素。類。在順bool三、詳細(xì)設(shè)計1.類和類的層次設(shè)計程序使用了兩個類,線性表 LinearlistLinearlist類里包括常見的線性表運算, 在類類和順序表SeqList類和一個主函數(shù)mian 。SeqList里面新增成員函數(shù)void Reverse()和bool Del

3、eteX(const T &x)。TLinearlist#int n+virtual bool IsEmpty() const = 0;+virtual int Length() const = 0;+virtual bool Find(int i,T& x) const = 0;+virtual int Search(T x) const = 0;+virtual bool Insert(int i,T x) = 0;+virtual bool Delete(int i) = 0;+virtual bool Update(int i,T x) = 0;+virtual void Output

4、(ostream& out) const = 0;TSeqList-int maxLength;-T *elements;+IsEmpty() const;+Length() const;+Find(int i,T& x) const;+Search(T x) const;+Insert(int i,T x);+Delete(int i);+Update(int i,T x);+Output(ostream& out) const;+Reverse();+DeleteX(const T& x);核心算法順序表 SeqList類中 , 私有段封裝了兩個私有數(shù)據(jù)成員maxLength 和 elem

5、ents,公有段封裝了構(gòu)造、析構(gòu)、查找、刪除、逆置等函數(shù)。實現(xiàn)要求的主要操作通過void Reverse()和bool DeleteX(const T &x)實現(xiàn)，void Reverse()通過前后互換實現(xiàn)逆置，boolDeleteX(constT &x) 使用hash數(shù)組標(biāo)記需要刪除的元素，然后將放在elements里面的數(shù)據(jù)刪除。兩個函數(shù)的流程圖如下。臨時變量存放數(shù)據(jù)int i=0Ni=n/2Y前后互換逆置i+void Reverse()int tmp=n,ii=0NitmpYhashi=0elementsi=xYNhashi+i+i=0NitmpYelementsn+=elements

6、ii+刪除 hashNn=tmpYreturn falsereturn falsebool DeleteX(const T &x)算法分析線性表的基本運算程序的主要算法的算法時間復(fù)雜度和空間復(fù)雜度為O（ n）四、程序代碼void SeqList:Reverse()T temp;/臨時變量存放數(shù)據(jù)for(int i = 0; i n / 2; i+)/ 前后互換逆置temp = elementsi;elementsi = elementsn - i - 1;elementsn - i - 1 = temp;templatebool SeqList:DeleteX(const T& x)int t

7、mp = n, i;/ 用于判斷是否有刪除數(shù)據(jù)n = 0;int *hash = new inttmp;for(i = 0; i tmp; i+)hashi = 0;if(elementsi = x)hashi+;for(i = 0; i expYNp-expexpYq1=qNp-exp=q-exYq-coef=q-coef+p-coeNq-coef=0Yq1=q重置 q 指針以 p 的系數(shù)和指數(shù)生成新結(jié)點插入 q1 后p=p-linkPolyAdd(Polynominal& r)定義相乘后的數(shù)據(jù)Np-exp=0Y存儲某段相乘后的數(shù)據(jù)Nq-exp=0Y生成新節(jié)點插入n 后將 temp 加到 r

8、esult 上指向表頭結(jié)點的后繼結(jié)點Nq!=NULLY刪除原對象的所有數(shù)據(jù)將 result 加到當(dāng)前對象上PolyMul(Polynominal& r)算法分析多項式的加法和乘法算術(shù)運算程序的主要算法的時間復(fù)雜程度和和空間復(fù)雜程度為 O（n）。四、程序代碼void Polynominal:PolyAdd(Polynominal& r)Term *q, *q1 = theList, *p;p = r.theList-link;q = q1-link;/q1 指向表頭結(jié)點/p 指向第一個要處理的結(jié)點/q1 是 q 的前驅(qū)， p 和 q 就指向兩個當(dāng)前進行比較的項while (p != NULL &

9、 p-exp = 0)/對 r 的單循環(huán)鏈表遍歷，知道全部結(jié)點都處理完while (p-exp exp)/ 跳過q-exp大的項q1 = q;q = q-link;if (p-exp = q-exp)/ 當(dāng)指數(shù)相等時，系數(shù)相加q-coef = q-coef + p-coef;if (q-coef = 0)/ 若相加后系數(shù)為0，則刪除qq1-link = q-link;delete(q);q = q1-link;/ 重置q 指針elseq1 = q;/若相加后系數(shù)不為0，則移動q1 和qq = q-link;else/pexpq-exp的情況q1 = q1-InsertAfter(p-coef,

10、 p-exp); /以 p 的系數(shù)和指數(shù)生成新結(jié)點，插入 q1 后p = p-link;void Polynominal:PolyMul(Polynominal& r)Polynominal result;Term *n = result.theList;/ 定義相乘后的數(shù)據(jù)/n 指向 result 的頭結(jié)點n = n-InsertAfter(0, 0);/在result的頭結(jié)點后插入新結(jié)點，系數(shù)指數(shù)均為0Term *p = r.theList-link;while(p-exp = 0)/p 指向第一個要處理的結(jié)點/對 r 的單循環(huán)鏈表遍歷Polynominal tmp;/ 存儲某段相乘后的數(shù)

11、據(jù)Term *m = tmp.theList;/m 指向 tmp 的頭結(jié)點Term *q = theList-link;/q 指向表頭結(jié)點的后繼結(jié)點while(q-exp = 0)/對當(dāng)前對象的單循環(huán)環(huán)鏈表遍歷m = m-InsertAfter(p-coef)*(q-coef), (p-exp) + (q-exp); /生成新結(jié)點插入n 后q = q-link;result.PolyAdd(tmp);/ 將 temp 加到 result 上p = p-link;Term *q = theList-link;/q 指向表頭結(jié)點的后繼結(jié)點while(q != NULL)/ 刪除原對象的所有數(shù)據(jù)th

12、eList-link = q-link;delete q;q = theList-link;q = theList;q = q-InsertAfter(0, 0);PolyAdd(result);/ 將 result 加到當(dāng)前對象上五、測試和調(diào)試測試用例和結(jié)果選擇 1, 計算多項式相加2)分別輸入系數(shù)和項數(shù)3 2,4 6,9 7,如圖所示得到相加的多項式如圖選擇 2, 計算多項式相乘5)輸入系數(shù)和項數(shù)4 2,6 3,得到多項式一 , 如圖再次輸入系數(shù)和項數(shù) 7 3, 得到多項式二以及多項一和多項式二的乘積結(jié)果分析程序能夠正確實現(xiàn)多項式的相加以及相乘但是程序無法實現(xiàn)不能加法乘法混用，下一步改進方

13、向是實現(xiàn)加法乘法混用，是計算更加簡便六、實習(xí)小結(jié)這個實驗的重難點都在于正確靈活使用，大部分代碼在書上都有提供，真正的操作重點在于理解這些代碼的意義和使用方法。通過這次課程設(shè)計，使我對數(shù)據(jù)結(jié)構(gòu)有了初步的清晰了解， 增強了程序的編寫能力，鞏固了專業(yè)知識，對程序的模塊化觀念也又模糊逐漸變的清晰了。 在程序的運行與調(diào)試過程中出現(xiàn)了很多錯誤，通過反復(fù)地復(fù)習(xí)課本上的相關(guān)知識，不停地修改與調(diào)試，終于完成了這段程序。在調(diào)試過程中， 我認(rèn)識到了數(shù)據(jù)結(jié)構(gòu)的靈活性與嚴(yán)謹(jǐn)性， 同一個功能可以由不同的語句來實現(xiàn)，但編寫程序時要特別注意細(xì)節(jié)方面的問題，因為一個小小的疏忽就能導(dǎo)致整個程序不能運行。我也認(rèn)識到了自己的薄弱之處

14、，如對c+ 和鏈表知識不夠熟悉，在以后的學(xué)習(xí)中我們要集中精力、端正態(tài)度，爭取把知識學(xué)得更扎實、更全面。經(jīng)過這次的實驗，我在各個方面都得到了不少的提高，我希望多幾次像這樣的實驗讓我們更好的鍛煉自己。附錄：線性表的基本運算#include using namespace std;int const LEN = 50;template class LinearListpublic:virtual bool IsEmpty() const = 0;virtual int Length() const = 0;virtual bool Find(int i,T& x) const = 0;virtual

15、 int Search(T x) const = 0;virtual bool Insert(int i,T x) = 0;virtual bool Delete(int i) = 0;virtual bool Update(int i,T x) = 0;virtual void Output(ostream& out) const = 0;protected:int n;/ 線性表的長度;template class SeqList: public LinearListprivate:int maxLength;T *elements;public:/線性表的最大長度/動態(tài)一維數(shù)組的指針Se

16、qList(int mSize);SeqList()deleteelements;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);template SeqList:SeqList(int mSi

17、ze)maxLength = mSize;elements = new TmaxLength; / 動態(tài)分配順序表的存儲空間 n = 0;template bool SeqList:IsEmpty() constreturn n = 0;template int SeqList:Length() constreturn n;template bool SeqList:Find(int i, T& x) constif(i n - 1)cout Out of Bounds endl;/對 i 進行越界檢查return false;x = elementsi;return true;templat

18、eint SeqList:Search(T x) constfor(int j = 0; j n; j+)if(elementsj = x)return j;return -1;templatebool SeqList:Insert(int i, T x)if(i n - 1)cout Out Of Bounds endl;return false;if(n = maxLength)cout OverFlow i; j-)elementsj + 1 = elementsj;elementsi + 1 = x;n+;return true;template bool SeqList:Delete

19、(int i)if(!n)cout UnderFlow endl;return false;if(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 bool SeqList:Update(int i,T x)if(i n - 1)coutOut Of Boundsendl;return false;elementsi = x;return true;template void SeqList:Outpu

20、t(ostream& out)constfor(int i = 0; i n; i+)out elementsi ;out endl;template void SeqList:Reverse()T temp;/臨時變量存放數(shù)據(jù)for(int i = 0; i n / 2; i+)/ 前后互換逆置temp = elementsi;elementsi = elementsn - i - 1;elementsn - i - 1 = temp;templatebool SeqList:DeleteX(const T& x)int tmp = n, i;/ 用于判斷是否有刪除數(shù)據(jù)n = 0;int *

21、hash = new inttmp;for(i = 0; i tmp; i+)hashi = 0;if(elementsi = x)hashi+;for(i = 0; i tmp; i+)if(!hashi)elementsn+ = elementsi;deletehash;if(n = tmp)/ 判斷是否有刪除的數(shù)據(jù)return false;elsereturn true;int main()int del_data, len ,num;SeqList A(LEN);cout len;cout nInput each element: ;for(int i = 0; i num;A.Ins

22、ert(i - 1, num);cout nInitial seqlist: ;A.Output(cout);A.Reverse();cout nResevered seqlist: ;A.Output(cout);cout del_data;if(A.DeleteX(del_data) = true)cout nSeqlist after being deleted: ;A.Output(cout);elsecout nNot found endl;return 0;多項式的基本運算#includeclass Termpublic:Term(int c, int e);Term(int c,

23、 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

24、 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&

25、 in);void Output(ostream& out)const;void PolyAdd(Polynominal& r);void PolyMul(Polynominal& r);private:Term* theList;friend ostream& operator(istream&, Polynominal &);friend Polynominal& operator+(Polynominal &, Polynominal &); friend Polynominal& operator*(Polynominal &, Polynominal &);Polynominal:P

26、olynominal()theList = new Term(0, -1);theList-link = NULL;/頭結(jié)點/單鏈表尾結(jié)點指針域為空Polynominal:Polynominal()Term* p = theList-link;while (p != NULL)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,ex

27、p):n c e;q = q-InsertAfter(c, e);if (0 e) break;void Polynominal:Output(ostream& out)constint first = 1;Term *p = theList-link;for (; p != NULL & p-exp = 0; p = p-link)if (!first & (p-coef0) out +;first = 0;out *p;cout link;q = q1-link;/p指向第一個要處理的結(jié)點/q1 是 q 的前驅(qū)， p 和 q 就指向兩個當(dāng)前進行比較的項while (p != NULL &

28、p-exp = 0)/對 r 的單循環(huán)鏈表遍歷，知道全部結(jié)點都處理完while (p-exp exp)/ 跳過q-exp大的項q1 = q;q = q-link;if (p-exp = q-exp)/ 當(dāng)指數(shù)相等時，系數(shù)相加q-coef = q-coef + p-coef;if (q-coef = 0)/ 若相加后系數(shù)為0，則刪除qq1-link = q-link;delete(q);q = q1-link;/ 重置q 指針elseq1 = q;/若相加后系數(shù)不為0，則移動q1 和qq = q-link;else/pexpq-exp的情況q1 = q1-InsertAfter(p-coef, p-exp); /以 p 的系數(shù)和指數(shù)生成新結(jié)點，插入 q1 后p = p-link;void Polynominal:PolyMul(Polynominal& r)Polynominal result;Term *n = result.theList;/ 定義相乘后的數(shù)據(jù)/n 指向 result 的頭結(jié)點n = n-I