圖的遍歷實(shí)現(xiàn)課程設(shè)計(jì)--圖的遍歷的實(shí)現(xiàn)

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

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)　　設(shè)計(jì)說明書　　數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院　　2014年1 月 4日　圖的遍歷的實(shí)現(xiàn) <b&

2、gt;　　課程設(shè)計(jì)任務(wù)書　　2013—2014學(xué)年第一學(xué)期　　設(shè)計(jì)內(nèi)容：　　1. 任務(wù)說明　　(1) 采用鄰接表存儲(chǔ)結(jié)構(gòu)創(chuàng)建一個(gè)圖；

3、　(2) 編程實(shí)現(xiàn)圖的深度優(yōu)先搜索（或廣度優(yōu)先搜索）遍歷算法；　　(3) 輸出遍歷結(jié)果；　　(4) 給定具體數(shù)據(jù)調(diào)試程序。　　2. 要求　　1）問題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問題，明確問題要求做什么？ <

4、;/p>　　2）邏輯設(shè)計(jì)：寫出抽象數(shù)據(jù)類型的定義，各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；　　3）詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。　　4）程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。　　5）程序調(diào)試與測(cè)試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函

5、數(shù)。　　6）結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析；　　7）編寫課程設(shè)計(jì)報(bào)告。　　3. 參考資料　　指導(dǎo)教師：申靜

6、教研室負(fù)責(zé)人：余冬梅　　課程設(shè)計(jì)評(píng)閱　　摘要　　針對(duì)圖問題中如何更好地實(shí)現(xiàn)圖的遍歷問題，以無向圖為例，分別采用廣度優(yōu)先遍歷和深度優(yōu)先遍歷的算法實(shí)現(xiàn)對(duì)各節(jié)點(diǎn)的遍歷，以VC++為開發(fā)環(huán)境進(jìn)行系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)，其

7、運(yùn)行結(jié)果表明，系統(tǒng)能很好地完成遍歷后節(jié)點(diǎn)的輸出，實(shí)現(xiàn)了遍歷的目的，系統(tǒng)界面友好，可操作性強(qiáng)。　　關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；存儲(chǔ)結(jié)構(gòu)；鄰接矩陣　　目錄　　一課題描述1　　二設(shè)計(jì)目的與任務(wù)2

8、　　2.1課程設(shè)計(jì)的目的2　　2.2課程設(shè)計(jì)的任務(wù)2　　三設(shè)計(jì)方案和實(shí)施3　　3.1總體設(shè)計(jì)3　　3.2基本操作3&l

9、t;p>　　3.3詳細(xì)設(shè)計(jì)4　　四運(yùn)行調(diào)試結(jié)果6　　五結(jié)論與致謝9　　六附錄11　　一課題描述&l

10、t;/p>　　數(shù)據(jù)結(jié)構(gòu)是一門專業(yè)基礎(chǔ)課，它對(duì)學(xué)習(xí)者的要求很明確：學(xué)會(huì)分析、研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用設(shè)計(jì)所需的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析的技術(shù)。其次，該課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，要求學(xué)習(xí)者編寫的程序結(jié)構(gòu)或設(shè)計(jì)的程序結(jié)構(gòu)體清楚、正確、易讀，符合軟件工程的規(guī)范。　　圖是一種較為復(fù)雜且重

11、要的數(shù)據(jù)結(jié)構(gòu)，其特殊性在于圖形結(jié)構(gòu)中結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都有可能相關(guān)。就本課程設(shè)計(jì)而言應(yīng)用圖論的知識(shí)討論如何在計(jì)算機(jī)上實(shí)現(xiàn)圖的遍歷的操作，主要解決圖的遍歷的幾種方法的實(shí)現(xiàn)。　　本設(shè)計(jì)采用目前最通用的程序設(shè)計(jì)語言之一—C語言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語言。　　二設(shè)計(jì)目的與任務(wù)</p

12、>　　2.1課程設(shè)計(jì)的目的　　進(jìn)一步的了解圖的遍歷的問題，圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)，用無向圖來實(shí)現(xiàn)圖的遍歷。　　初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能。 　　訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)，熟練的完成問題分析、算法設(shè)計(jì)、編寫

13、程序，求解出指定的問題。　　訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，鞏固、深化學(xué)生的理論知識(shí)，提高編程水平，并在此過程中培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力。　　2.2課程設(shè)計(jì)的任務(wù)

14、1）任務(wù)說明　　用C/C++編寫一個(gè)程序?qū)崿F(xiàn)圖的遍歷的算法。　　從鍵盤上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）。圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn);用有向圖實(shí)現(xiàn)圖的遍歷；用無向圖實(shí)現(xiàn)圖的遍歷；用鄰接矩陣存儲(chǔ)圖；用鄰接表存儲(chǔ)圖。　　2）要求</

15、p>　　1>首先輸入圖的結(jié)點(diǎn)數(shù)； 　　2>依次輸入圖的各條邊（數(shù)據(jù)之間用空格隔開）；　　3>輸出的形式：按用戶選擇的遍歷方法給出遍歷順序，各字符間用->分隔； 　　4>程序所能達(dá)到的功能：能夠按要求輸出所要的結(jié)果。

16、　　三設(shè)計(jì)方案和實(shí)施　　3.1總體設(shè)計(jì)　　采用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)。程序中主要用到以下抽象數(shù)據(jù)類型：　　抽象數(shù)據(jù)類型的定義　　typedef struc

17、t{ 　　char *vexs; //頂點(diǎn)向量 　　int arcs[MAX_VEX][MAX_VEX]; //鄰接矩陣 　　int vexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) 　　}Graph;</b

18、>　　3.2基本操作　　CreateUDN(Graph &G)　　操作結(jié)果：用鄰接矩陣創(chuàng)建帶權(quán)無向網(wǎng)圖。　　DFS(Graph G,int k)　　操作結(jié)果：對(duì)已存在的圖進(jìn)行深度

19、優(yōu)先遍歷。　　BFS(Graph G)　　操作結(jié)果：對(duì)已存在的圖進(jìn)行廣度優(yōu)先遍歷。　　choose(Graph G)　　操作結(jié)果：對(duì)將要實(shí)現(xiàn)的操作步驟進(jìn)行選擇。　　程序包含兩個(gè)模塊</p

20、>　　主程序模塊，其中主函數(shù)為　　int main{　　輸入信息；　　根據(jù)輸入要求進(jìn)行選擇操作和輸出；　　輸出結(jié)果；<

21、b>　　}　　選擇操作模塊—實(shí)現(xiàn)具體選擇的對(duì)應(yīng)操作及輸出操作。　　兩模塊之間關(guān)系如下圖3.1所示　　圖3.1 模塊關(guān)系圖　　3.3詳細(xì)設(shè)計(jì)　　程序流程圖如圖3.2所示

22、　　圖3.2 程序流程圖　　函數(shù)設(shè)計(jì)程序設(shè)計(jì)中主要包括下列函數(shù)用鄰接矩陣創(chuàng)建一個(gè)圖：　　void CreateUDN(Graph &G){　　用鄰接矩陣創(chuàng)建一個(gè)帶權(quán)無向網(wǎng)圖;　　輸入頂點(diǎn)數(shù)和弧數(shù);<

23、/b>　　輸入各個(gè)頂點(diǎn)及各條弧;　　}　　遞歸方法實(shí)現(xiàn)圖的遍歷：　　void DFS(Graph G, int k)　　{&

24、lt;p>　　用遞歸的方法訪問圖中的結(jié)點(diǎn);　　對(duì)圖進(jìn)行深度優(yōu)先遍歷;　　}　　非遞歸方法實(shí)現(xiàn)圖的遍歷：　　void BFS(Graph G) 　　{

25、　　用隊(duì)列輔助訪問圖中的結(jié)點(diǎn);　　對(duì)圖進(jìn)行廣度優(yōu)先遍歷;　　}　　選擇輸出需要的遍歷方法：　　void choose(Graph G)

26、;　　{　　給出程序運(yùn)行的選項(xiàng);　　對(duì)相應(yīng)的輸入選項(xiàng)調(diào)用相應(yīng)的函數(shù)以執(zhí)行操作；　　}　　四運(yùn)行調(diào)試結(jié)果　　例：遍歷如下無向圖（圖 4

27、.1）(a,b,c,d,e分別表示V1 V2 V3 V4 V5五個(gè)頂點(diǎn))　　以圖4.1為例　　步驟一：　　運(yùn)行程序，按提示首先輸入頂點(diǎn)數(shù)和弧數(shù)。　　圖4.2輸入頂點(diǎn)數(shù)和弧數(shù)

28、　　步驟二：　　輸入頂點(diǎn)和弧　　輸入頂點(diǎn)　　圖4.3 輸入各頂點(diǎn)　?。?）輸入弧

29、　　圖4.3 輸入各條弧　　步驟三：　　選擇便利方式以及選擇后結(jié)果　　選擇1操作顯示廣度優(yōu)先編歷結(jié)果　　圖4.4 廣度優(yōu)先結(jié)果　　選2操作顯示深度優(yōu)先遍歷

30、;　　圖4.4深度優(yōu)先遍歷結(jié)果 　　五結(jié)論與致謝　　在程序設(shè)計(jì)中我主要是解決的是給出一個(gè)圖如何用多種方法完成圖的遍歷的問題，也包括如何創(chuàng)建一個(gè)圖，深度優(yōu)先遍歷和廣度優(yōu)先遍歷一個(gè)圖，遞歸和非遞歸的方法實(shí)現(xiàn)圖的遍歷。程序最終通過調(diào)試運(yùn)行，初步

31、實(shí)現(xiàn)了設(shè)計(jì)目標(biāo)。　　圖是一種較為復(fù)雜且重要的數(shù)據(jù)結(jié)構(gòu)，其特殊性在于圖形結(jié)構(gòu)中結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都有可能相關(guān)。用鄰接矩陣作為圖的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)很好地解決了圖的結(jié)構(gòu)難點(diǎn)，借助于鄰接矩陣容易判定任意兩個(gè)頂點(diǎn)之間是否有邊(或弧)相連，并容易求得各個(gè)頂點(diǎn)的度。該程序通俗易懂且實(shí)用性強(qiáng)，并且該程序清單詳細(xì)具體、全面、具有很強(qiáng)的可讀性；系統(tǒng)整體上比較完美，可以從鍵盤獲取輸入元

32、素，并且可以根據(jù)用戶輸入進(jìn)行選擇性地輸出；整體輸出畫面效果整潔、大方。　　這次課程設(shè)計(jì)也讓我充分認(rèn)識(shí)到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個(gè)思想和大綱，讓我們?cè)诰幊虝r(shí)容易找到思路，不至于無章可循。同時(shí)它也有廣泛的實(shí)際應(yīng)用。　　最后，我還要特別感謝我們的輔導(dǎo)老師**老師，在她的精心輔導(dǎo)和幫助下，我的設(shè)計(jì)才得以順利完成。對(duì)她為我們的設(shè)計(jì)所提出的寶貴意見表示

33、忠心的感謝！　　參考文獻(xiàn)　　[1]譚浩強(qiáng). C程序設(shè)計(jì)[第三版]. 北京:清華大學(xué)出版社.　　[2]羅宇等. 數(shù)據(jù)結(jié)構(gòu)[M ]. 北京郵電大學(xué)出版社.　　[3]嚴(yán)藯敏. 數(shù)據(jù)結(jié)構(gòu)[C語言版]. 北京:清華大學(xué)出版社.

34、;　　[4]楊路明. C語言程序設(shè)計(jì)教程. 北京郵電大學(xué)出版社.　　[5]徐孝凱. 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn). 清華大學(xué)出版社.　　六附錄　　源程序代碼　　// 程序功能：采用遞

35、歸和非遞歸算法，有向圖和無向圖，鄰接矩陣和鄰接表等多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)圖的遍歷。　　// 程序作者：英茜　　// 最后修改日期：2014-1-3　　#include"stdio.h"　　#include"stdlib.h"</p&

36、gt;　　#define INFINITY 32767 　　#define MAX_VEX 20 //最大頂點(diǎn)個(gè)數(shù) 　　#define QUEUE_SIZE (MAX_VEX+1) //隊(duì)列長度 　　bool *visited;//訪問標(biāo)志數(shù)組 </p

37、>　　int z=1; //圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu) 　　typedef struct{ 　　char *vexs; //頂點(diǎn)向量 　　int arcs[MAX_VEX][MAX_VEX]; //鄰接矩陣 <

38、;p>　　int vexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) 　　}Graph; 　　class Queue{ //隊(duì)列類 　　public:

39、　void InitQueue(){ 　　base=(int *)malloc(QUEUE_SIZE*sizeof(int)); 　　front=rear=0; 　　} 　　void EnQueue(int e){

40、;　　base[rear]=e; 　　rear=(rear+1)%QUEUE_SIZE; 　　} 　　void DeQueue(int &e){ 　　e=base[front];

41、　　front=(front+1)%QUEUE_SIZE; 　　} 　　int *base; 　　int front; 　　int rear; 　　}; &

42、lt;/b>　　int Locate(Graph G,char c){ //圖G中查找元素c的位置　　for(int i=0;i<G.vexnum;i++) 　　if(G.vexs[i]==c) return i; 　　return -1; <

43、;/p>　　} 　　void CreateUDN(Graph &G){ //創(chuàng)建無向網(wǎng)　　int i,j,w,s1,s2; 　　char a,b,c,temp; 　　printf(&q

44、uot;輸入頂點(diǎn)數(shù)和弧數(shù)(頂點(diǎn)數(shù)和弧數(shù)之間以空格隔開) : ");　　scanf("%d%d",&G.vexnum,&G.arcnum); 　　temp=getchar(); //接收回車 　　G.vexs=(char *)malloc(G.ve

45、xnum*sizeof(char)); //分配頂點(diǎn)數(shù)目 　　printf("輸入%d個(gè)頂點(diǎn).\n",G.vexnum); 　　for(i=0;i<G.vexnum;i++){ //初始化頂點(diǎn) 　　scanf("%c",&G.vexs[i]);

46、　　temp=getchar(); //接收回車 　　} 　　for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣 　　for(j=0;j<G.vexnum;j++) <

47、/p>　　G.arcs[i][j]=INFINITY; 　　printf("輸入%d條弧.\n",G.arcnum); 　　for(i=0;i<G.arcnum;i++){ //初始化弧 　　printf("輸入弧%d: ",

48、i);　　scanf("%c %c %d%c",&a,&b,&w,&c); //輸入一條邊依附的頂點(diǎn)和權(quán)值 　　s1=Locate(G,a); 　　s2=Locate(G,b); 　　G.arcs[s1][s2]

49、=G.arcs[s2][s1]=w; 　　} 　　} 　　int FirstVex(Graph G,int k){ //圖G中頂點(diǎn)k的第一個(gè)鄰接頂點(diǎn)　　if(k>=0 &&a

50、mp; k<G.vexnum){ //k合理 　　for(int i=0;i<G.vexnum;i++) 　　if(G.arcs[k][i]!=INFINITY) return i; 　　} 　　return -1; &l

51、t;/p>　　} 　　//圖G中頂點(diǎn)i的第j個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)　　int NextVex(Graph G,int i,int j){　　if(i>=0 && i<G.vexnum && j>

52、=0 && j<G.vexnum){ //i,j合理 　　for(int k=j+1;k<G.vexnum;k++) 　　if(G.arcs[i][k]!=INFINITY) return k; 　　}

53、　return -1; 　　} 　　//深度優(yōu)先遍歷 　　void DFS(Graph G,int k){ 　　int i; <

54、p>　　if(k==-1){ //第一次執(zhí)行DFS時(shí),k為-1 　　for(i=0;i<G.vexnum;i++) 　　if(!visited[i]) DFS(G,i); //對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS 　　} <

55、;p>　　else{ 　　visited[k]=true;　　if(z==1)　　printf("%c",G.vexs[k]);　　else printf("

56、-> %c",G.vexs[k]); ++z;//訪問第k個(gè)頂點(diǎn) 　　if((z-1)%G.vexnum==0) z=1;　　for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i)) 　　if(!visited[i]) DFS(G,i); //對(duì)k的尚未訪問的

57、鄰接頂點(diǎn)i遞歸調(diào)用DFS 　　} 　　}　　//廣度優(yōu)先遍歷 　　void BFS(Graph G){ <b&

58、gt;　　int k; 　　Queue Q; //輔助隊(duì)列Q 　　Q.InitQueue(); 　　for(int i=0;i<G.vexnum;i++) 　　if(!visited[i]){ //i尚未訪問 &

59、lt;/p>　　visited[i]=true;　　printf("%c ",G.vexs[i]); 　　Q.EnQueue(i); //i入列 　　while(Q.front!=Q.rear){ 　　Q.

60、DeQueue(k); //隊(duì)頭元素出列并置為k 　　for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w)) 　　if(!visited[w]){ //w為k的尚未訪問的鄰接頂點(diǎn) 　　visited[w]=true;

61、　　printf("-> %c ",G.vexs[w]); 　　Q.EnQueue(w); 　　} 　　} 　　} printf("\n 請(qǐng)

62、繼續(xù)選擇:\n");　　} 　　void choose(Graph G){//對(duì)輸入選項(xiàng)調(diào)用相應(yīng)的函數(shù)執(zhí)行操作　　int i,m; 　　visited=(bool *)mall

63、oc(G.vexnum*sizeof(bool));　　scanf("%d",&m);　　switch(m){　　case 1: 　　printf("廣度優(yōu)先遍歷: "); </p

64、>　　for(i=0;i<G.vexnum;i++) 　　visited[i]=false; 　　BFS(G); choose(G); printf("\n");break;　　case 2:<

65、;p>　　printf("深度優(yōu)先遍歷: "); 　　for(i=0;i<G.vexnum;i++) 　　visited[i]=false; 　　DFS(G,-1); 　　printf("\n 請(qǐng)繼續(xù)選擇:\n");

66、choose(G);break;　　case 3:printf("程序結(jié)束."); break;　　default : printf(" 輸入錯(cuò)誤!\n請(qǐng)?jiān)?-3中選擇:\n"); choose(G);　　}

67、　　}　　//主函數(shù) 　　void main(){ 　　int i,m; 　　Graph G; &l

68、t;/p>　　CreateUDN(G); 　　printf("有如下選項(xiàng)供選擇：\n");　　printf("\n");　　printf("|*| 1:廣度優(yōu)先遍歷 2:深度優(yōu)先遍歷 3:退出本程序！|*|\n");<

眾賞文庫> 全部分類> 畢業(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)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(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í)現(xiàn)課程設(shè)計(jì)--圖的遍歷的實(shí)現(xiàn)

文檔簡介

溫馨提示

最新文檔

評(píng)論

圖的遍歷實(shí)現(xiàn)課程設(shè)計(jì)--圖的遍歷的實(shí)現(xiàn)

文檔簡介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載