數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-----圖的遍歷

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-----圖的遍歷_第1頁

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

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

文檔簡介

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

2、;p>　　1.1課程設(shè)計的目的與意義………………………………………………4　　1.2對課程設(shè)計功能的需求分析…………………………………………4　　二、算法思想…………………………………………………………………5　　三、數(shù)據(jù)結(jié)構(gòu)…………………………………………………………………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)的概要設(shè)計　　1、系統(tǒng)功能模塊圖…………………………………………………………9　　六、源程序……………………………………………………………………10　　七、程序的調(diào)試分析以及測試結(jié)果　　1、程序的調(diào)試測試結(jié)果………………………………………

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

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

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

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

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

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

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

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

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

15、n;//標(biāo)志位,用來標(biāo)示是否遍歷過　　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)的概要設(shè)計　　main() /*包含一些調(diào)用和控制語句*/&

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

20、t;p>　　struct node//定義一個結(jié)構(gòu)作為節(jié)點類型　　{　　int data;　　bool sign;//標(biāo)志位,用來標(biāo)示是否遍歷過　　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ù)組內(nèi)存　　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表示結(jié)束）"<<

25、;endl;　　cin>>l;　　if(l!=0)//判斷輸入邊是否結(jié)束　　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);//分配邊的一個頂點內(nèi)存　　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);//分配邊的另一個頂點內(nèi)存　　q->data=l;　　q->next=NULL;　　if(adjacencylist[m].next==NULL)//構(gòu)建鄰接表　　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;//錯誤輸入標(biāo)識　　cin>>l;　　if

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

35、　void DepthFirstSearch(node *list)//深度優(yōu)先搜索　　{　　int m,n=list[0].data,k,*a=new int[n];//設(shè)置一個數(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++)//恢復(fù)原鄰接表　　list[i].sign=f;　　cout<<"深度優(yōu)先搜索遍歷順序為:";　　for(i=0;i<n;i++)//輸出遍歷結(jié)果　　cout<<a[i]<<" &qu

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

45、;b>　　{　　int m,r,k,n=list[0].data,*a=new int[n+1];//設(shè)置數(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;//標(biāo)識遍歷的第一個節(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;//標(biāo)識已經(jīng)遍歷過的節(jié)點

50、}　　p=p->next; 　　}　　}　　for(int i=1;i<=n;i++)//恢復(fù)原鄰接表　　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ù)組內(nèi)存　　};　　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ù)組內(nèi)存存放路

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)//是否為已經(jīng)判斷過的錯誤路徑<b&g

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

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

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

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

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

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;//還原標(biāo)識符&

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++)//恢復(fù)原鄰接表&

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);//釋放鄰接表空間　　}　　七、程序的調(diào)試分析以及測試結(jié)果　　7.1程

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

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

89、lt;/p>　　2）在調(diào)試過程中懂得了，學(xué)習(xí)的嚴謹性，特別對于編程題目。“差之毫厘，謬之千里”。當(dāng)然這也不僅僅在學(xué)習(xí)方面，生活中也是樣。　　3）在這個項目中也提醒了自己在平時除了自己的專業(yè)知識外應(yīng)該積累更多的知識，技能。只有這樣在進行各項事情的過程中才能更加順利。　　4）“理論聯(lián)系實踐”，實踐是建立在學(xué)習(xí)的基礎(chǔ)之上，而又在其中

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

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

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

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

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

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

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-----圖的遍歷

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-----圖的遍歷

文檔簡介

溫馨提示

最新文檔

評論

免費下載