數(shù)據(jù)結構課程設計-----圖的遍歷

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：23 大?。?85.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩22頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　本科生課程設計論文　　題目：C++課程設計　　-------圖的遍歷　　課程設計任務書　　一、前言<

2、;p>　　1.1課程設計的目的與意義………………………………………………4　　1.2對課程設計功能的需求分析…………………………………………4　　二、算法思想…………………………………………………………………5　　三、數(shù)據(jù)結構…………………………………………………………………5<

3、;p>　　四、模塊劃分…………………………………………………………………6　　node* creategraph()//建立鄰接表，完成無向圖的輸入　　void DepthFirstSearch(node *list)//深度優(yōu)先搜索　　void BreadthFirstSearth(node *list)

4、//廣度優(yōu)先搜索　　void PathSearth(node *list)//路徑搜索　　void AdjacencyListDelete(node *list)//釋放鄰接表的空間　　AdjacencyListDelete(list);//釋放鄰接表空間

5、;　　五、系統(tǒng)的概要設計　　1、系統(tǒng)功能模塊圖…………………………………………………………9　　六、源程序……………………………………………………………………10　　七、程序的調試分析以及測試結果　　1、程序的調試測試結果………………………………………

6、…………………20　　八、附錄　　1、附錄一　　心得……………………………………………………………………………21　　2、參考文獻…………………………………………………………………22</p

7、>　　一、前言　　1.1課程設計的目的與意義　　上學期我們對《數(shù)據(jù)結構》這門課程進行了學習。這門課程是一門實踐性非常強的課程，為了讓大家更好地理解與運用所學知識，提高動手能力，我們進行了此次課程設計實習。這次課程設計不但要求我們掌握《數(shù)據(jù)結構》中的各方面知識，還要求我們具備一定的C++語言

8、基礎和編程能力。　　通過實踐我們掌握《數(shù)據(jù)結構》中的知識。對于《圖的遍歷》這一課題來說，所要求我們掌握的數(shù)據(jù)結構知識主要有：圖的存儲結構、隊列的基本運算實現(xiàn)、圖的深度優(yōu)先遍歷算法實現(xiàn)、圖的廣度優(yōu)先遍歷算法實現(xiàn)。　　對于我們學生來講，此次課程設計是為了讓我們訓練自己的實際設計能力，通過設計實踐，去真正獲得此項目管理和團隊協(xié)作等方面的基本訓練和工作經驗。&l

9、t;/p>　　通過課程設計的一系列訓練，我們能提高如何綜合運用所學知識解決實際問題的能力，以及獲得此項目管理和團隊協(xié)作等等眾多方面的具體經驗，增強對相關課程具體內容的理解和掌握能力，培養(yǎng)對整體課程知識綜合運用和融會貫通能力。　　1.2對課程設計功能的需求分析　　圖的遍歷并不需要是一個過于復雜的工作環(huán)境，一般來說：最合適的才是最

10、好的。軟件設計必須符合我們使用實際情況的需要。根據(jù)要求，圖的遍歷主要功能如下： 1、用戶可以隨時建立一個有向圖或無向圖；　　2、用戶可以根據(jù)自己的需要，對圖進行深度遍歷或廣度遍歷；　　3、用戶可以根據(jù)自己的需要對圖進行修改；　　4、在整個程序中,用戶可以不斷的按照不同的方式對圖進行遍歷,若不繼續(xù),用戶也可

11、以隨時跳出程序,同時,如果用戶輸入的序號錯誤,程序會提示用戶重新輸入序號;　　二、算法思想　　本課題本人所采用的是鄰接表的方式存儲圖，實現(xiàn)圖的深度、廣度兩種遍歷，并將每種遍歷結果輸出來。并且能尋找路徑。2.1.1圖的鄰接矩陣的建立對任意給定的圖（頂點數(shù)和邊數(shù)自定），，根據(jù)鄰接表的存儲結構建立圖的鄰接表。

12、2.1.2 圖的遍歷的實現(xiàn) 鄰接表是圖的一種鏈式存儲結構，在鄰接表中，對圖中的每一個頂點建立一個單鏈表，通常以順序結構存儲，以便隨機訪問任意一頂點。　　圖的深度遍歷，假設初始狀態(tài)是圖中所有頂點都未曾被訪問，則深度優(yōu)先遍歷可從圖中的某個頂點v出發(fā)，訪問此頂點，依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中和v有路徑想通的頂點都被訪問到；若此時圖中尚有未被訪問的節(jié)點，則另選圖中一

13、個未被訪問的頂點做起始點，直至所有節(jié)點都被訪問。　　圖的廣度優(yōu)先遍歷，是以v為起始點，由近及遠，依次訪問和v有路徑相通且路徑長度為1、2、…的頂點。　　三、數(shù)據(jù)結構　　#define t true　　#define f false&l

14、t;/p>　　#include<iostream.h>　　struct node//定義一個結構作為節(jié)點類型　　{　　int data;　　bool sig

15、n;//標志位,用來標示是否遍歷過　　node *next;　　};　　四、模塊劃分　　node* creategraph()//建立鄰接表，完成無向圖的輸入<p&g

16、t;　　};　　表4.1鄰接表的建立　　void DepthFirstSearch(node *list)//深度優(yōu)先搜索　　真　　非零零<p

17、>　　圖4.2 深度優(yōu)先遍歷流程圖　　void BreadthFirstSearth(node *list)//廣度優(yōu)先搜索　　真 　　表4.3圖的廣度遍歷　　void PathSearth(node *list)//路徑搜索</

18、p>　　void AdjacencyListDelete(node *list)//釋放鄰接表的空間　　AdjacencyListDelete(list);//釋放鄰接表空間　　五、系統(tǒng)的概要設計　　main() /*包含一些調用和控制語句*/&

19、lt;/p>　　圖5.1系統(tǒng)功能模塊圖　　六、部分源程序　　#define t true　　#define f false　　#include<iostream.h>&l

20、t;p>　　struct node//定義一個結構作為節(jié)點類型　　{　　int data;　　bool sign;//標志位,用來標示是否遍歷過　　node *next;

21、　　};　　node* creategraph()//建立鄰接表，完成無向圖的輸入　　{　　int l,m,n;　　bool g;<

22、;/p>　　cout<<"請輸入節(jié)點數(shù): ";　　cin>>n;　　node *adjacencylist=new node[n+1];//動態(tài)分配節(jié)點數(shù)組內存　　adjacencylist[0].dat

23、a=n;//0地址存放的為節(jié)點數(shù)　　adjacencylist[0].next=NULL;　　for(int i=1;i<=n;i++)//給各頂點域賦初值　　{　　adjacencylist[i].data=0;</p&

24、gt;　　adjacencylist[i].next=NULL;　　adjacencylist[i].sign=f;//表示未遍歷 　　}　　cout<<"請依次輸入各條邊的始點和尾點:（以0表示結束）"<<

25、;endl;　　cin>>l;　　if(l!=0)//判斷輸入邊是否結束　　g=t;　　while(g==t)　　{<

26、/b>　　cin>>m;　　if((l>0)&&(l<=n)&&(m>0)&&(m<=n))//判斷輸入頂點是否正確　　{&

27、lt;p>　　node *p,*q,*top;　　p=(node *)new(node);//分配邊的一個頂點內存　　p->data=m;　　p->next=NULL;　　if(adjacencylist[l].next==NULL)//為每個節(jié)點創(chuàng)建鄰

28、接鏈表　　adjacencylist[l].next=p;　　else　　{　　top=adjacencylist[l].next;　　while(top

29、->next!=NULL)　　top=top->next;　　top->next=p;　　}　　adjacencylist[l].data++;//統(tǒng)計鄰接點的個數(shù)　　q=(

30、node *)new(node);//分配邊的另一個頂點內存　　q->data=l;　　q->next=NULL;　　if(adjacencylist[m].next==NULL)//構建鄰接表　　adjacencylist[m].next=q;</p&

31、gt;　　else　　{　　top=adjacencylist[m].next;　　while(top->next!=NULL)　　top=top->next;&

32、lt;/p>　　top->next=q;　　}　　adjacencylist[m].data++;//統(tǒng)計鄰接點的個數(shù)　　}　　else<

33、/b>　　cout<<"邊"<<l<<"--"<<m<<"輸入錯誤！"<<endl;//錯誤輸入標識　　cin>>l;　　if

34、(l==0)//邊的輸入結束　　g=f;　　}　　return adjacencylist;//返回鄰接表　　};

35、　void DepthFirstSearch(node *list)//深度優(yōu)先搜索　　{　　int m,n=list[0].data,k,*a=new int[n];//設置一個數(shù)組用于存放節(jié)點　　node *p;

36、　　cout<<"采用深度優(yōu)先搜索："<<endl;　　cout<<"請輸入搜索起始節(jié)點：";　　cin>>k;　　for(int i=0;i<n;i++)<

37、;/p>　　{　　a[i]=k;　　list[k].sign=t;　　if(i==n-1)　　break;

38、　　m=0;　　while(list[k].sign==t)　　{　　p=list[k].next;　　while(p!=NULL)//找出list[k]鏈表中的未遍歷節(jié)點<

39、;/p>　　{ 　　k=p->data;　　p=p->next;　　if(list[k].sign==f)　　break;<p

40、>　　}　　m++;　　if(list[k].sign!=f)//判斷是否是p=NULL跳出while循環(huán)的　　{　　if(i<m)//無節(jié)點可回

41、溯　　{　　cout<<"該圖為非連通圖!"<<endl;　　break; 　　}

42、　　else　　k=a[i-m]; //回溯 　　}　　}　　} 　　for(i=1;i<

43、=n;i++)//恢復原鄰接表　　list[i].sign=f;　　cout<<"深度優(yōu)先搜索遍歷順序為:";　　for(i=0;i<n;i++)//輸出遍歷結果　　cout<<a[i]<<" &qu

44、ot;;　　cout<<endl;　　delete a;//釋放動態(tài)數(shù)組內存　　};　　void BreadthFirstSearth(node *list)//廣度優(yōu)先搜索<

45、;b>　　{　　int m,r,k,n=list[0].data,*a=new int[n+1];//設置數(shù)組存放節(jié)點　　node *p;　　cout<<"采用廣度優(yōu)先搜索："<<endl;</p&g

46、t;　　cout<<"請輸入搜索起始節(jié)點：";　　cin>>k;　　a[0]=n;　　a[1]=k;<p

47、>　　list[k].sign=t;//標識遍歷的第一個節(jié)點　　m=0;　　r=1;　　while(m!=r)　　{<p&

48、gt;　　m++;　　p=list[a[m]].next;　　while(p!=NULL)　　{　　k=p->data;　　if(list[k].s

49、ign==f)　　{　　r++;　　a[r]=k;//遍歷到的節(jié)點存入數(shù)組　　list[k].sign=t;//標識已經遍歷過的節(jié)點

50、}　　p=p->next; 　　}　　}　　for(int i=1;i<=n;i++)//恢復原鄰接表　　list[i]

51、.sign=f;　　cout<<"廣度優(yōu)先搜索遍歷順序為: ";　　for(i=1;i<=n;i++)//輸出遍歷　　cout<<a[i]<<" ";　　cout<<endl;&

52、lt;/p>　　delete a;//釋放動態(tài)數(shù)組內存　　};　　void PathSearth(node *list)//路徑搜索　　{　　int *a,c,d,m,

53、k,n=list[0].data;　　cout<<"請輸入起始點：";　　cin>>k;　　cout<<"請輸入尾節(jié)點：";　　cin>

54、;>c;　　cout<<"請輸入要找的路徑長度：";　　cin>>d;　　d=d+1;　　if(d>n

55、)　　cout<<"不存在這樣的簡單路徑！"<<endl;　　else　　{　　a=new int[d];//動態(tài)分配數(shù)組內存存放路

56、徑上的節(jié)點　　for(int i=0;i<d;i++)　　a[i]=0;　　a[0]=k;　　node *p;

57、　　int x;　　list[a[0]].sign=t;　　i=1;　　while(a[d-1]!=c)　　{ <p&g

58、t;　　while(i<d)　　{　　x=1;　　p=list[a[i-1]].next;　　while(p!=NULL)　　{&

59、lt;/b>　　m=p->data;　　if(i==d-1&&m==a[0]&&a[0]==c)//路徑存在且為回路　　{　　cout<<"該路徑為一條回路！"

60、;<<endl;　　a[i]=m;　　i++;　　break;　　}

61、;　　if(list[m].sign==f)　　{　　if(a[i]!=0)　　{ 　　if(x==0)//是否為已經判斷過的錯誤路徑<b&g

62、t;　　{　　a[i]=m;　　list[a[i]].sign=t;//標識走過節(jié)點　　i++;　　break;&

63、lt;p>　　}　　if(a[i]==m)//設置錯誤路徑標識　　x=0;　　}　　else

64、　　{　　a[i]=m;　　list[a[i]].sign=t;//標識走過節(jié)點　　i++;　　break;</b

65、>　　}　　}　　p=p->next; 　　}　　if(p==NULL)</p&

66、gt;　　{　　a[i]=0;　　i--;//由此節(jié)點往下的路徑不存在,回溯　　list[a[i]].sign=f; //還原標識符 　　}

67、　　if(i==0)//無法回溯,路徑不存在,跳出循環(huán)　　{　　cout<<"不存在這樣的簡單路徑！"<<endl;　　break; </b&

68、gt;　　}　　}　　if(i==0)//無法回溯,路徑不存在,跳出循環(huán)　　break;　　if(a[d-1]!=c

69、)//路徑不是所要找的　　{ 　　i--; //回溯　　if(i>=0)　　list[a[i]].sign=f;//還原標識符&

70、lt;p>　　}　　}　　if(a[d-1]==c)//判斷路徑是否找到并輸出　　{　　cout<<"從節(jié)點"<&

71、lt;k<<"到節(jié)點"<<c<<"的一條路徑為：";　　for(i=0;i<d-1;i++)//輸出路徑　　cout<<a[i]<<"--> ";　　cout<<a[d-

72、1]<<endl;　　}　　delete a;　　}　　for(int i=1;i<=n;i++)//恢復原鄰接表&

73、lt;p>　　list[i].sign=f; 　　};　　void AdjacencyListDelete(node *list)//釋放鄰接表的空間　　{　　node *p,*q

74、;　　int n=list[0].data;　　for(int i=1;i<=n;i++)　　{　　p=list[i].next;　　while(p!=NULL)

75、　　{　　q=p->next;　　delete p;//釋放鏈表節(jié)點空間　　p=q;　　}

76、　　}　　delete list;//釋放鄰接表空間　　};　　void main()　　{　　node *list

77、;　　list=creategraph();//以鄰接表的形式建立一個無向圖　　char a,b;　　cout<<"請選擇遍歷方法：（d:深度優(yōu)先搜索;b:廣度優(yōu)先搜索）";　　for(int i=1;

78、i<2;i++)　　{　　cin>>a;　　switch(a)　　{<p

79、>　　case 'd':　　case 'D': DepthFirstSearch(list);　　cout<<"是否采用廣度優(yōu)先搜索重新遍歷？（y:是;n:否）";　　cin>&g

80、t;b;　　if((b=='y')||(b=='Y'))　　BreadthFirstSearth(list);　　break;　　case 'b':

81、　　case 'B': BreadthFirstSearth(list);　　cout<<"是否采用深度優(yōu)先搜索重新遍歷？（y:是;n:否）";　　cin>>b;<

82、p>　　if((b=='y')||(b=='Y'))　　DepthFirstSearch(list);　　break;　　default: cout<<"輸入錯誤！請重新輸入！"<<endl

83、;　　i--;　　}　　}　　while(1)　　{<

84、/b>　　cout<<"是否搜索路徑？（y:是;n:否）";　　cin>>a;　　if((a=='y')||(a=='Y'))　　PathSearth(

85、list);　　else if((a=='n')||(a=='N'))　　break;　　else　　cout<<"輸入錯誤！"&l

86、t;<endl;　　}　　AdjacencyListDelete(list);//釋放鄰接表空間　　}　　七、程序的調試分析以及測試結果　　7.1程

87、序的調試分析　　程序的調試是一個很重要的方面，本題目有個創(chuàng)建鄰接表函數(shù)這是個基礎，如果這里出了差錯當然后面的模塊也就無法進行了。所以在調試程序的時候，我是先進行了對創(chuàng)建鄰接表的函數(shù)進行調試。再確保無誤的情況下在進行了后面模塊的調試，在調試中間經常會出現(xiàn)一些小問題，這是我會經常的采用“隔離”的方法進行逐步的排查。最后還得對整個程序進行總體的調試，不斷完善一些細節(jié)方面，并對輸入的參數(shù)進行多方面的改變

88、，以確保程序的正確性。　　在整個程序運行無誤的基礎上，在盡力對一些函數(shù)進行優(yōu)化，加強程序的可讀性，方便性。　　經過這次課程設計讓我收獲了不少東西，只要有以下幾個方面。　　1）對于基于C++語言的數(shù)據(jù)結構，C++語言的掌握情況是能否學好這么課程的一個重要因素，所以在進行課程設計的時候又對C++語言進行了部分復習。&

89、lt;/p>　　2）在調試過程中懂得了，學習的嚴謹性，特別對于編程題目?！安钪晾澹囍Ю铩?。當然這也不僅僅在學習方面，生活中也是樣。　　3）在這個項目中也提醒了自己在平時除了自己的專業(yè)知識外應該積累更多的知識，技能。只有這樣在進行各項事情的過程中才能更加順利。　　4）“理論聯(lián)系實踐”，實踐是建立在學習的基礎之上，而又在其中

90、不斷的學習的過程。平時上課聽講覺得容易接受，淡然無味，但在實現(xiàn)算法的時候才發(fā)現(xiàn)原來一切并非如此。數(shù)據(jù)結構這門課程比較抽象而且如果自己只是看看書的話根本就不能夠學好的，而且數(shù)據(jù)結構這門課程也應用的非常廣泛，特別是在計算機許多語言中都能夠看到數(shù)據(jù)結構的思想。　　八、附錄　　5.1、課程設計心得體會

91、　　心得體會 　　通過這近一個星期的數(shù)據(jù)結構課程設計實踐，我學到了很多東西。本次課程設計對我來說正是一個提高自己能力的機會，我好好的抓住機會，努力做好每一步，完善每一步。　　自己的C語言知識和數(shù)據(jù)結構知識得到了鞏固，編程能力也有了一定的提高。同時也學會了解決問題的方法?？偨Y起來，自己主要有以

92、下幾點體會：　　1.必須牢固掌握基礎知識。由于C語言是大一所學知識，有所遺忘，且未掌握好上學期所學的《數(shù)據(jù)結構》這門課，所以在實踐之初感到棘手。不知如何下手，但在后來的實習過程中自己通過看書和課外資料，并請教其他同學，慢慢地對C語言和數(shù)據(jù)結構知識有所熟悉，這時才逐漸有了思路。所以，這次課程之后，我告誡自己：今后一定要牢固掌握好專業(yè)基礎知識。　　2.必須培

93、養(yǎng)嚴謹?shù)膽B(tài)度。自己在編程時經常因為一些類似于“少了分號”的小錯誤而導致錯誤，不夠認真細致，這給自己帶來了許多麻煩。編程是一件十分嚴謹?shù)氖虑椋莶坏民R虎。所以在今后自己一定要培養(yǎng)嚴謹?shù)膽B(tài)度。我想這不僅是對于程序設計，做任何事都應如此。　　3.這次課程設計也讓我充分認識到《數(shù)據(jù)結構》這門課的重要性。它給我們一個思想和大綱，讓我們在編程時容易找到思路，不至于無章可循。同時它也有廣泛的實際應用。<

94、/p>　　在實踐過程中，我和組員分工合作，勇于提出問題，解決難題，在實踐中，我遇到了許多困難，但都一一克服了。最終我圓滿的完成此次課程設計，學到了很多東西。同時，程序還存在著一些缺陷，就是不能輸出原圖，存在一些局限性，不過我會繼續(xù)努力思考，完善程序，做到最好。　　此次試驗，老師對我的指導是至關重要的，在此我非常感謝老師，從他那我學到了很多有關c語言的知識，為以后的學習

95、打下了一定的基礎。　　總的來說，本次課程設計，不僅我的知識面有所提高，另外我的綜合素質也有所提高，，比如說：團隊精神、提問能力、思考能力等等。這次課程設計為我以后更好的學習和使用c語言打下了基礎。　　參考文獻　　1．《數(shù)據(jù)結構（C語言版）》嚴蔚敏、吳偉民主編清華大學出

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

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

數(shù)據(jù)結構課程設計-----圖的遍歷

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計-----圖的遍歷

文檔簡介

溫馨提示

最新文檔

評論

免費下載