數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--雙向循環(huán)鏈表的實(shí)現(xiàn)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：20 大?。?93.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--雙向循環(huán)鏈表的實(shí)現(xiàn)_第1頁(yè)

已閱讀1頁(yè)，還剩19頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　課程設(shè)計(jì)說明書　　題目：雙向循環(huán)鏈表　　基于鄰接表的圖的實(shí)現(xiàn)　　課程：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)　　院（部）：計(jì)算機(jī)科學(xué)與技術(shù)　　專

2、業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)　　班級(jí)： 　　學(xué)生姓名： 　　學(xué) 號(hào)： 　　指導(dǎo)教師： 　　完成

3、日期： 　　目錄　　課程設(shè)計(jì)任務(wù)書I　　課程設(shè)計(jì)任務(wù)書II　　雙向循環(huán)鏈表的實(shí)現(xiàn)3　　一、問題描述3

4、　　二、數(shù)據(jù)結(jié)構(gòu)4　　三、邏輯設(shè)計(jì)5　　四、編碼7　　五、測(cè)試數(shù)據(jù)9

5、　　六、測(cè)試情況11　　基于鄰接表的圖的實(shí)現(xiàn)12　　一、問題描述12　　二、數(shù)據(jù)結(jié)構(gòu)13　　三、邏輯設(shè)計(jì)13&l

6、t;/b>　　四、編碼15　　五、測(cè)試數(shù)據(jù)16　　六、測(cè)試情況16　　結(jié) 論17&

7、lt;p>　　參考文獻(xiàn)18　　課程設(shè)計(jì)指導(dǎo)教師評(píng)語19　　課程設(shè)計(jì)任務(wù)書I　　課程設(shè)計(jì)任務(wù)書II　　指導(dǎo)教師（簽字）：教研室

8、主任（簽字）：　　雙向循環(huán)鏈表的實(shí)現(xiàn)　　一、問題描述　　用圖示的方法描述所處理的雙向循環(huán)鏈表的建立，以及插入刪除操作前后鏈表的狀態(tài)　　只有有頭節(jié)點(diǎn)的雙向循環(huán)鏈表<p&

9、gt;　　有頭節(jié)點(diǎn)的雙向循環(huán)鏈表　　雙向循環(huán)鏈表的插入 　　雙向循環(huán)鏈表的刪除　　二、數(shù)據(jù)結(jié)構(gòu)　　template <class T><

10、p>　　struct chainNode 　　{　　// data members　　T element;　　chainNode<T> *right;　　chainNode&

11、lt;T> *left;　　// methods　　chainNode() {　　left=NULL;　　right=NULL;　　}　　cha

12、inNode(const T& element)　　{　　this->element = element;　　left=NULL;　　right=NULL;

13、}　　chainNode(const T& element,chainNode<T> * left,chainNode<T>* right)　　{　　this->element = element;

14、　　this->left = left;　　this->right = right;　　}　　};　　三、邏輯設(shè)計(jì)</

15、p>　　1、總體思路　　(1)存儲(chǔ)結(jié)構(gòu)　　基于鄰接表，繼承l(wèi)inerlist類，具體實(shí)現(xiàn)雙向循環(huán)鏈表的存儲(chǔ)　　(2)基本函數(shù)　　雙

16、向循環(huán)鏈表的插入，刪除　　2、模塊劃分(圖示的方法)　　(1)erase（刪除）　　Yes　　No　　Yes<

17、/p>　　(2)insert（插入）　　No　　Yes　　No　　Yes

18、　　函數(shù)或類的具體定義和功能　　bool empty() const {return listSize == 0;}//是否為空　　int size() const {return listSize;}　　T& get(int theIndex) const;

19、　　int indexOf(const T& theElement) const;　　void erase(int theIndex);　　void insert(int theIndex, const T& theElement);　　void right_output(ost

20、ream& out) const;　　void left_output(ostream& out) const;　　四、編碼　　template<class T>　　void doublechain<

21、T>::checkIndex(int theIndex) const　　{// Verify that theIndex is between 0 and listSize - 1.　　if (theIndex < 0 || theIndex >= listSize)　　{ostringstre

22、am s;　　s << "index = " << theIndex << " size = " << listSize;　　throw illegalIndex(s.str());　　}

23、　　}　　template<class T>　　T& doublechain<T>::get(int theIndex) const　　{// 返回索引為theIndex的元素.

24、　　//checkIndex(theIndex);　　if(theIndex<0||theIndex>=listSize){　　T a=0;　　return a;}　　// move to desired

25、 node　　chainNode<T>* currentNode = headerNode->right;　　for (int i = 0; i < theIndex; i++)　　currentNode = currentNode->right;<p&

26、gt;　　return currentNode->element;　　}　　template<class T>　　int doublechain<T>::indexOf(const T& theElement) const</p&g

27、t;　　{// 返回元素theElement首次出現(xiàn)時(shí)的索引.　　// Return -1 if theElement not in list.　　chainNode<T>* currentNode = headerNode->right;　　int index = -1;

28、 // 當(dāng)前節(jié)點(diǎn)的索引　　while (++index <listSize &&　　currentNode->element != theElement)　　{　　// move to next node

29、　　currentNode = currentNode->right;　　}　　// make sure we found matching element　　if (index == listSize)

30、　　return -1;　　else　　return index;　　}　　template<class T>　　void

31、doublechain<T>::erase(int theIndex)　　{// Delete the element whose index is theIndex.　　// Throw illegalIndex exception if no such element.　　//checkIndex

32、(theIndex);　　if (theIndex < 0 || theIndex > listSize)　　{　　cout<<"元素不存在"<<endl;

33、return;　　}　　// valid index, locate node with element to delete　　chainNode<T>* deleteNode;　　chainNode&

34、lt;T>* p = headerNode;　　for (int i = 0; i < theIndex; i++)　　p = p->right;　　deleteNode = p->right;　　p->right=deleteNode-&g

35、t;right;　　deleteNode->right->left=p;　　listSize--;　　delete deleteNode;　　}　　template<clas

36、s T>　　void doublechain<T>::insert(int theIndex, const T& theElement)　　{// Insert theElement so that its index is theIndex.　　if (theIndex < 0

37、|| theIndex > listSize)　　{　　cout<<"Insert index must be between 0 to listSize"<<endl;　　//ostringstream s;</p&g

38、t;　　//s << "index = " << theIndex << " size = " << listSize;　　//throw illegalIndex(s.str());　　}

39、;　　chainNode<T>* q= new chainNode<T>(theElement);　　chainNode<T>* p = headerNode;　　for (int i = 0; i < theIndex; i++)　　p = p-&

40、gt;right;　　q->right=p->right;　　q->left=p;　　p->right=q;　　q->right->left=q;　　listSize++;

41、　　}　　template<class T>　　void doublechain<T>::right_output(ostream& out) const　　{// Put the list into the stream

42、out.　　chainNode<T>* currentNode = headerNode->right;　　for (int i = 0;i < listSize;i++){　　out << currentNode->element << " &q

43、uot;;　　currentNode = currentNode->right;　　}　　}　　template<class T>　　v

44、oid doublechain<T>::left_output(ostream& out) const　　{// Put the list into the stream out.　　chainNode<T>* currentNode = headerNode->left;

45、　for (int i = 0;i < listSize;i++){　　out << currentNode->element << " ";　　currentNode = currentNode->left;　　}</b&g

46、t;　　}　　五、測(cè)試數(shù)據(jù)　　1、對(duì)每個(gè)函數(shù)的測(cè)試數(shù)據(jù)　　(1)新建一個(gè)鏈表　　y.insert(0, 2);<

47、;/p>　　y.insert(1, 6);　　y.insert(0, 1);　　y.insert(2, 4);　　y.insert(3, 5);　　y.insert(2, 3);　　insert的異常測(cè)

48、試y.insert(7,4);　　(2)刪除元素　　異常條件測(cè)試　　y.erase(7);　　正常條件測(cè)試　　y.e

49、rase(1);　　y.erase(0);　　y.erase(2);　　邊緣條件測(cè)試(將剩余的元素刪除)　　y.erase(0);　　y.erase(0);　　y.erase(0);<

50、;/p>　　2、對(duì)程序整體的測(cè)試數(shù)據(jù)　　(1)判斷鏈表是否為空　　y.empty();　　(2)測(cè)試鏈表長(zhǎng)度　　y.size();<p&g

51、t;　　(3)通過索引查找值　　y.get(-1);　　y.get(3);　　(4)通過值查找索引　　y.indexOf(7);　　y.indexOf(4);<p

52、>　　六、測(cè)試情況　　1.新建一個(gè)鏈表　　測(cè)試indexOf　　3.測(cè)試get　　4測(cè)試eras

53、e　　插入（insert）（theIndex>listSize）　　基于鄰接表的圖的實(shí)現(xiàn)(insertEdge)　　問題描述　　鄰接表的形態(tài)<

54、;p>　　aList 　　11　　2　　圖　　3&l

55、t;p>　　22　　1　　4　　插入一條邊　　3&

56、lt;p>　　21　　2　　4　　1　　二．?dāng)?shù)據(jù)結(jié)構(gòu)

57、　　template <class T>　　struct wEdge　　{// vertex and weight pair　　int vertex;　　T weight;<

58、;p>　　wEdge(int theVertex = 0, T theWeight = 0)　　{vertex = theVertex; weight = theWeight;}　　operator int() const {return vertex;}　　};<

59、;/p>　　三、邏輯設(shè)計(jì)　　1.基本函數(shù)　　圖的邊插入　　2.模塊劃分

60、(1)插入一條邊　　開　　No　　Yes　　3、函數(shù)或類的具體定義和功能　　int number

61、OfVertices() const;//返回圖的頂點(diǎn)數(shù)　　int numberOfEdges() const;//返回圖的邊數(shù)　　bool existsEdge(int, int) const;//if 邊（ ,）存在，返回true，否則返回false　　void insertEdge(edge<T>

62、; *theEdge);//插入邊（i，j）　　void eraseEdge(int, int);//刪除邊　　int degree(int) const;//返回頂點(diǎn)的度，只用于無向圖　　int inDegree(int) const;//返回頂點(diǎn)的入度　　int ou

63、tDegree(int) const;//返回頂點(diǎn)的出度　　bool directed() const;//有向圖　　bool weighted() const;//加權(quán)圖　　void checkVertex(int theVertex) const;　　void out

64、put(ostream& out) const;　　編碼　　template<class T>　　int graph<T>::numberOfVertices() const{　　re

65、turn n;　　}　　template<class T>　　int graph<T>::numberOfEdges() const{　　return e;</b&g

66、t;　　}　　template<class T>　　bool graph<T>::directed() const{　　return false;

67、}　　template<class T>　　bool graph<T>::weighted() const{　　return true;　　}　　t

68、emplate<class T>　　void graph<T>::insertEdge(edge<T> *theEdge){　　int v1 = theEdge->vertex1();　　int v2 = theEdge->vertex2();

69、　　if ( existsEdge(v1,v2) )　　{　　return;　　}　　aList[v1].push_back( wEdge

70、<T>(v2, theEdge->weight()) );//vector里面的一個(gè)push函數(shù)　　aList[v2].push_back( wEdge<T>(v1, theEdge->weight()) );　　e++;

71、　　}　　template<class T>　　void graph<T>::output(ostream& out) const　　{// Output the adjacency matrix.　　typename

72、std::list<wEdge<T> >::iterator p;　　for (int i = 1; i <= n; i++){　　for(p = aList[i].begin(); p != aList[i].end(); p++)　　out <<*p <<

73、 " ";　　cout<<endl;　　}　　}　　五、測(cè)試數(shù)據(jù)

74、　　新建一個(gè)鄰接表　　a.insertEdge(new weightedEdge<int>(1, 3, 2));　　a.insertEdge(new weightedEdge<int>(2, 3, 1));　　a.insertEdge(new weightedEdge&

75、lt;int>(1, 2, 3));　　a.insertEdge(new weightedEdge<int>(2, 4, 2));　　a.insertEdge(new weightedEdge<int>(3, 4, 4));　　六、測(cè)試情況<

76、;/p>　　結(jié) 論　　參考文獻(xiàn)　　[1] 數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用：c++語言描述/（美）薩尼（Sahni，S）著；王立柱等譯，北京：機(jī)械工業(yè)出版社 2015.1　　[2] 金遠(yuǎn)平.《數(shù)據(jù)結(jié)構(gòu)(c++描述).北京：清

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--雙向循環(huán)鏈表的實(shí)現(xiàn)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--雙向循環(huán)鏈表的實(shí)現(xiàn)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載