課程設(shè)計(jì)-圖的遍歷

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

2023年全國(guó)碩士研究生考試考研英語一試題真題（含答案詳解+作文范文）_第1頁

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

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

文檔簡(jiǎn)介

1、　　目錄　　一、課題的主要功能2　　1.1設(shè)計(jì)內(nèi)容2　　1.2對(duì)課程設(shè)計(jì)功能的需求分析2　　二、課題的功能模塊的劃分2<b

2、>　　2.1模塊劃分2　　2.2系統(tǒng)的概要設(shè)計(jì)3　　三、主要功能的實(shí)現(xiàn)4　　3.1算法思想4　　1.圖的鄰接矩陣的建立4　　2.圖的遍歷的實(shí)現(xiàn)4</

3、p>　　3.2數(shù)據(jù)結(jié)構(gòu)4　　3.3主函數(shù)流程圖5　　3.4深度優(yōu)先遍歷流程圖6　　3.5深度優(yōu)先遍歷遞歸7　　3.6深度優(yōu)先遍歷流程圖9　　3.7廣度優(yōu)先

4、遍歷遞歸流程圖10　　四、程序調(diào)試11　　4.1程序的調(diào)試分析11　　4.2程序的測(cè)試結(jié)果11　　五、總結(jié)16　　六、附件1

5、6　　6.1源程序16　　一、課題的主要功能　　1.1設(shè)計(jì)內(nèi)容　　演示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過程，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。要求圖

6、的結(jié)點(diǎn)數(shù)不能少于6個(gè)?？梢杂上到y(tǒng)隨機(jī)生成圖，也可以由用戶手動(dòng)輸入圖。報(bào)告中要寫出畫圖的思路；畫出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進(jìn)一步改進(jìn)圖的效果。　　1.2對(duì)課程設(shè)計(jì)功能的需求分析　　圖的遍歷并不需要是一個(gè)過于復(fù)雜的工作環(huán)境，一般來說：最合適的才是最好的。軟件設(shè)計(jì)必須符合我們使用實(shí)際情況的需要。根據(jù)要求，圖的遍歷主要功能如下：<

7、p>　　1.用戶可以隨時(shí)建立一個(gè)有向圖或無向圖；　　2.用戶可以根據(jù)自己的需要，對(duì)圖進(jìn)行深度遍歷或廣度遍歷；　　3.用戶可以根據(jù)自己的需要對(duì)圖進(jìn)行修改；　　4.在整個(gè)程序中,用戶可以不斷的按照不同的方式對(duì)圖進(jìn)行遍歷,若不繼續(xù),用戶也可以隨時(shí)跳出程序,同時(shí),如果用戶輸入的序號(hào)錯(cuò)誤,程序會(huì)提示用戶重新輸入序號(hào)；

8、　　二、課題的功能模塊的劃分　　2.1模塊劃分　　1.隊(duì)列的初始化、進(jìn)隊(duì)、出隊(duì)、隊(duì)列空、隊(duì)列滿的函數(shù)　　void InitQueue(CirQueue *Q) //初始化隊(duì)列　　int Qu

9、eueEmpty(CirQueue *Q)//隊(duì)列是否為空　　int QueueFull(CirQueue *Q)//隊(duì)列滿　　Void EnQueue(CirQueue *Q,int x)//將隊(duì)員進(jìn)隊(duì)　　int DeQueue(CirQueue *Q)//將隊(duì)員出隊(duì)<p&g

10、t;　　2.創(chuàng)建圖的函數(shù)　　void CreateMGraph(MGraph *G)//根據(jù)用戶需要?jiǎng)?chuàng)建一個(gè)圖　　3.圖的深度優(yōu)先遍歷遞歸　　void DFSM(MGraph *G,int i)/*含有輸出已訪問的頂點(diǎn)的語句*/　　4

11、.圖的廣度優(yōu)先遍歷遞歸 　　void BFSM(MGraph *G,int k) /*含有輸出已訪問的頂點(diǎn)的語句*/　　5.深度優(yōu)先遍歷 　　void DFSTraverseM(MGraph *G)/*調(diào)用DFSM函數(shù)*/<b&

12、gt;　　6.廣度優(yōu)先遍歷 　　void BFSTraverseM(MGraph *G) /*調(diào)用BFSM函數(shù)*/　　7.主函數(shù) 　　main() /*包含一些調(diào)用和控制語句*/　　2.2系統(tǒng)的概要設(shè)計(jì)</

13、p>　　三、主要功能的實(shí)現(xiàn)　　3.1算法思想　　本課題所采用的是鄰接矩陣的方式存儲(chǔ)圖，實(shí)現(xiàn)圖的深度、廣度兩種遍歷，并將每種遍歷結(jié)果輸出來。　　1.圖的鄰接矩陣的建立

14、對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），根據(jù)鄰接矩陣的存儲(chǔ)結(jié)構(gòu)建立圖的鄰接距陣。　　2.圖的遍歷的實(shí)現(xiàn)　　圖的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對(duì)于廣度優(yōu)先遍歷應(yīng)利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）來實(shí)現(xiàn)。首先建立一空隊(duì)列，從初始點(diǎn)出發(fā)進(jìn)行訪問，當(dāng)被訪問時(shí)入隊(duì)，訪問完出隊(duì)。并以隊(duì)列是否

15、為空作為循環(huán)控制條件。對(duì)于深度優(yōu)先遍歷則采用遞歸或非遞歸算法來實(shí)現(xiàn)，這里我所采用的是遞歸算法。　　3.2數(shù)據(jù)結(jié)構(gòu)　　#define Max 10　　#define FALSE 0　　#define TRUE 1

16、　　#define Error printf　　#define QueueSize 30　　typedef struct 　　{　　char vexs[Max];　　int

17、edges[Max][Max];　　int n,e;　　}MGraph;　　int visited[Max];　　typedef struct <b

18、>　　{　　int front;　　int rear;　　int count;　　int data[QueueSize];　　}CirQueue;

19、　　3.3主函數(shù)流程圖　　假 　　0　　1

20、　　2 　　3　　3.4深度優(yōu)先遍歷流程圖　　真　　非零零　　3.

21、5深度優(yōu)先遍歷遞歸　　真 　　3.6深度優(yōu)先遍歷流程圖　　真　　非零零　　3.7廣度優(yōu)先遍歷遞歸流程圖<

22、/p>　　真　　四、程序調(diào)試　　4.1程序的調(diào)試分析　　在調(diào)試過程中，程序中出現(xiàn)了許多的錯(cuò)誤，有錯(cuò)誤的調(diào)用,一些變量沒有定義等等。不斷的對(duì)程序進(jìn)行調(diào)試以得到最好的結(jié)果，程序中特別要注意的是類的對(duì)象作為作為參數(shù)時(shí)

23、要注意如何去調(diào)用它，使程序有一個(gè)令人滿意的結(jié)果，具體的調(diào)試是在上機(jī)過程中進(jìn)行的，在編寫程序的過程中主要有如下錯(cuò)誤：　　1.在編寫程序的過程出現(xiàn)了一些函數(shù)名、變量的大小寫不統(tǒng)一的錯(cuò)誤，導(dǎo)致程序在運(yùn)行的過程中出現(xiàn)函數(shù)名、變量沒有被定義等問題；　　2.在編寫程序的過程中數(shù)組的大小寫沒有被確定；　　3.在編寫程序的過程中

24、一些變量沒有被定義，導(dǎo)致程序出錯(cuò)；　　4.數(shù)組visited[Max]應(yīng)定義為全局變量，若不是則會(huì)出錯(cuò)；　　5.函數(shù)的返回類型要確定，是void還是其他類型要十分注意；　　6.在編程的過程中，函數(shù)里一些控制語句的嵌套使用，括號(hào)要引起注意，　　4.2程序的測(cè)試結(jié)果</

25、p>　　初始進(jìn)入程序時(shí)，程序提示按格式輸入圖的頂點(diǎn)個(gè)數(shù)和邊數(shù)。　　輸入頂點(diǎn)數(shù)和邊數(shù)后，程序提示輸入頂點(diǎn)的序號(hào)，為各頂點(diǎn)依次進(jìn)行編號(hào)。　　將各頂點(diǎn)進(jìn)行編號(hào)后，程序提示按格式輸入邊的頂點(diǎn)序號(hào)。　　按格式依次輸入邊的頂點(diǎn)序號(hào)后，按enter鍵程序會(huì)出現(xiàn)“選擇菜單”，用戶根據(jù)需要進(jìn)行選擇。&l

26、t;/p>　　用戶選擇2進(jìn)入深度優(yōu)先搜索，并輸出深度優(yōu)先遍歷后的序列，再次輸出菜單欄，進(jìn)行選擇。　　用戶再次選擇3進(jìn)入廣度優(yōu)先搜索，并輸出廣度優(yōu)先遍歷后的序列，再次輸出菜單欄，進(jìn)行選擇。　　用戶選擇1后進(jìn)入更改數(shù)據(jù)，重新創(chuàng)建一個(gè)圖。　　用戶選擇0，則退出程序。&

27、lt;p>　　五、總結(jié)　　通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)踐，我學(xué)到了很多東西。本次課程設(shè)計(jì)對(duì)我來說正是一個(gè)提高自己能力的機(jī)會(huì)，我好好的抓住機(jī)會(huì)，努力做好每一步，完善每一步。自己的C語言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固，編程能力也有了一定的提高。同時(shí)也學(xué)會(huì)了解決問題的方法?？偨Y(jié)起來，自己主要有以下幾點(diǎn)體會(huì)：　　1.必須牢

28、固掌握基礎(chǔ)知識(shí)。由于C語言是大一所學(xué)知識(shí)，有所遺忘，且未掌握好上學(xué)期所學(xué)的《數(shù)據(jù)結(jié)構(gòu)》這門課，所以在實(shí)踐之初感到棘手。不知如何下手，但在后來的實(shí)習(xí)過程中自己通過看書和課外資料，并請(qǐng)教其他同學(xué)，慢慢地對(duì)C語言和數(shù)據(jù)結(jié)構(gòu)知識(shí)有所熟悉，這時(shí)才逐漸有了思路。所以今后一定要牢固掌握好專業(yè)基礎(chǔ)知識(shí)。　　2.必須培養(yǎng)嚴(yán)謹(jǐn)?shù)膽B(tài)度。自己在編程時(shí)經(jīng)常因?yàn)橐恍┬″e(cuò)誤而導(dǎo)致出現(xiàn)問題，不夠認(rèn)真細(xì)致，這給自己帶來了許多麻煩

29、。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑?，容不得馬虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)膽B(tài)度。我想這不僅是對(duì)于程序設(shè)計(jì)，做任何事都應(yīng)如此。　　3.這次課程設(shè)計(jì)也讓我充分認(rèn)識(shí)到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個(gè)思想和大綱，讓我們?cè)诰幊虝r(shí)容易找到思路，不至于無章可循。同時(shí)它也有廣泛的實(shí)際應(yīng)用。　　在實(shí)踐過程中，我遇到了許多困難，但都一一克服了。最終我圓滿的完成此次課程設(shè)

30、計(jì)，學(xué)到了很多東西。同時(shí)，程序還存在著一些缺陷，我會(huì)繼續(xù)努力思考，完善程序，做到最好。　　總的來說，本次課程設(shè)計(jì)，不僅我的知識(shí)面有所提高，另外我的綜合素質(zhì)也有所提高，這次課程設(shè)計(jì)為我以后更好的學(xué)習(xí)和使用c語言打下了基礎(chǔ)。　　六、附件　　6.1源程序</

31、b>　　#include<stdio.h>　　#include<stdlib.h>　　#define Max 10　　#define FALSE 0　　#define TRUE 1

32、　　#define Error printf　　#define QueueSize 30　　typedef struct 　　{　　char vexs[Max];　　in

33、t edges[Max][Max];　　int n,e;　　}MGraph;/*以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)*/　　int visited[Max];/*將visited[Max]定義為全局變量并分配最大空間*/　　typedef st

34、ruct 　　{　　int front;　　int rear;　　int count;　　int data[QueueSize];

35、　　}CirQueue;/*定義隊(duì)列的數(shù)據(jù)結(jié)構(gòu)*/　　//初始化隊(duì)列 　　void InitQueue(CirQueue *Q)　　{　　Q->front=Q->re

36、ar=0;　　Q->count=0;　　}　　//隊(duì)列空　　int QueueEmpty(CirQueue *Q)　　{</

37、b>　　return Q->count=QueueSize;/*返回隊(duì)列的最大長(zhǎng)度*/　　} 　　//隊(duì)列滿　　int QueueFull(CirQueue *Q)

38、　　{　　return Q->count==QueueSize;/*返回隊(duì)列的最大長(zhǎng)度*/　　} 　　//進(jìn)隊(duì)　　void EnQ

39、ueue(CirQueue *Q,int x)　　{　　if(QueueFull(Q))/*隊(duì)列滿則出錯(cuò)*/　　{　　Error("Queue overflow");</

40、p>　　}　　else　　{　　Q->count++;/*否則count++，將x進(jìn)隊(duì)*/　　Q->data[Q-&g

41、t;rear]=x;　　Q->rear=(Q->rear+1)%QueueSize;　　}　　}　　//出隊(duì)<p&g

42、t;　　int DeQueue(CirQueue *Q)　　{　　int temp;/*定義整型的變量*/　　if(QueueEmpty(Q))/*若為真則出錯(cuò)*/　　{&

43、lt;p>　　Error("Queue underflow");　　}　　else/*為假則count--，將隊(duì)員出隊(duì)*/　　{　　temp=Q->data[Q-&

44、gt;front];/*用temp返回其值*/　　Q->count--;　　Q->front=(Q->front+1)%QueueSize;　　return temp;/*返回出隊(duì)元素值*/　　}

45、　　} 　　//建立一個(gè)圖　　void CreateMGraph(MGraph *G)　　{　　int i,j,k;/*定義整型變量*/

46、　　char ch1,ch2;/*定義字符型變量*/　　printf("\n請(qǐng)輸入頂點(diǎn)數(shù)，邊數(shù)（格式：3，4）:");　　scanf("%d,%d",&(G->n),&(G->e));/*輸入圖的頂點(diǎn)數(shù)和邊數(shù)*/<p

47、>　　for(i=0;i<G->n;i++)　　{　　getchar();　　printf("\n請(qǐng)輸入第%d個(gè)頂點(diǎn)序號(hào)",i+1);　　scanf("%c",&(G-

48、>vexs[i]));/*輸入頂點(diǎn)的序號(hào)*/　　}　　for(i=0;i<G->n;i++)　　{　　for(j=0;j<G->n;j++)&

49、lt;p>　　{　　G->edges[i][j]=0;/*初始化矩陣*/　　}　　}　　for(k=0;k<G->e;k++)<

50、/p>　　{　　getchar();　　printf("\n請(qǐng)輸入第%d條邊的頂點(diǎn)序號(hào)（格式：i，j）:",k+1);　　scanf("%c,%c",&ch1,&ch2);/*輸入邊的頂點(diǎn)序號(hào)

51、*/　　for(i=0;ch1!=G->vexs[i];i++);　　for(j=0;ch2!=G->vexs[j];j++);　　G->edges[i][j]=1;/*有邊則賦值為1*/　　}

52、　　} 　　//深度優(yōu)先遍歷遞歸 　　void DFSM(MGraph *G,int i)　　{　　int j;&

53、lt;p>　　printf("%c ",G->vexs[i]);　　visited[i]=TRUE;/*標(biāo)記visited[i]*/　　/*依次優(yōu)先搜索訪問visited[i]的每個(gè)鄰接點(diǎn)*/　　for(j=0;j<G->n;j++)<p&

54、gt;　　/*若visited[i]的一個(gè)有效鄰接點(diǎn)visited[j]未被訪問過，則從visited[j]出發(fā)進(jìn)行遞歸調(diào)用*/　　if(G->edges[i][j]==1&&!visited[j])　　DFSM(G,j);　　}

55、　　//廣度優(yōu)先遍歷遞歸　　void BFSM(MGraph *G,int k)　　{　　int i,j;　　CirQueue Q;/*定義一個(gè)隊(duì)列Q，初始化隊(duì)列為空*/<

56、;/p>　　InitQueue(&Q);　　printf("%c ",G->vexs[k]);/*訪問初始點(diǎn)，并將其標(biāo)記已訪問過*/　　visited[k]=TRUE;　　EnQueue(&Q,k);/*將以訪問過的初始點(diǎn)序號(hào)k入隊(duì)*/<

57、/p>　　while(!QueueEmpty(&Q))/*隊(duì)列非空進(jìn)行循環(huán)處理*/　　{　　i=DeQueue(&Q);/*將隊(duì)首元素出隊(duì)*/　　for(j=0;j<G->n;j++)/*依次搜索vexs[k]的每一個(gè)可

58、能的鄰接點(diǎn)*/　　{　　if(G->edges[i][j]==1 &&! visited[j])　　{　　visited[j]=TRUE;/*標(biāo)記vexs[j]已訪問過*/&

59、lt;/p>　　EnQueue(&Q,j);/*頂點(diǎn)序號(hào)j入隊(duì)*/　　}　　}　　}　　}</b&

60、gt;　　//深度優(yōu)先遍歷　　void DFSTraverseM(MGraph *G)　　{　　int i;　　pr

61、intf("\n 深度優(yōu)先遍歷序列:");　　for(i=0;i<G->n;i++)　　{　　visited[i]=FALSE;/*訪問標(biāo)志數(shù)組初始化*/

62、;　　}　　for(i=0;i<G->n;i++)　　{　　if(!visited[i])/*對(duì)尚未訪問的頂點(diǎn)調(diào)用DFSM*/　　{<

63、p>　　DFSM(G,i);　　}　　}　　} 　　//廣度優(yōu)先遍歷

64、void BFSTraverseM(MGraph *G)　　{　　int i;　　printf("\n 廣度優(yōu)先遍歷序列:");　　for(i=0

65、;i<G->n;i++)　　{　　visited[i]=FALSE;/*訪問標(biāo)志數(shù)組初始化*/　　}　　for(i=0;i<G->n;i++)<

66、;p>　　{　　if(!visited[i])/*對(duì)尚未訪問的頂點(diǎn)調(diào)用BFSM*/　　{　　BFSM(G,i);　　}<p

67、>　　}　　} 　　main()　　{　　MGraph *G,a;<

68、;b>　　char ch1;　　int i,j,ch2;　　G=&a;　　printf("\n\t\t 深度優(yōu)先搜索和廣度優(yōu)先搜索 \n");

69、　CreateMGraph(G);/*調(diào)用創(chuàng)建圖矩陣的函數(shù)*/　　getchar(); 　　ch1='y';/*設(shè)置控制語句標(biāo)志*/　　while(ch1=='y'||ch1=='Y')　　{ /

70、*菜單欄*/　　printf("\n");　　printf(" 選擇菜單"); 　　printf("\n\t\t******************************************

71、\n");　　printf("\t\t* 更改數(shù)據(jù)請(qǐng)按:1 *\n");　　printf("\t\t* 深度優(yōu)先搜索請(qǐng)按:2 *\n");　　printf("\t\t

72、* 廣度優(yōu)先搜索請(qǐng)按:3 *\n");　　printf("\t\t* 退出搜索請(qǐng)按:0 *\n");　　printf("\t\t******************************************\n"

73、);　　printf("\n\t\t請(qǐng)選擇菜單號(hào)（0-3）：");　　scanf("%d",&ch2);　　getchar();　　switch(ch2)　　{&l

74、t;/b>　　case 1:　　CreateMGraph(G);/*選1創(chuàng)建一個(gè)新的圖矩陣*/　　break;　　case 2:

75、　　DFSTraverseM(G);/*選2進(jìn)入深度優(yōu)先搜索*/　　break;　　case 3:　　BFSTraverseM(G);/*選3進(jìn)入廣度優(yōu)先搜索*/

76、;　　break;　　case 0:/*選0結(jié)束搜索，退出程序*/　　ch1='n';　　break;　　default:

77、　　system("cls");　　printf("\n\t\t輸入有誤！\n");　　break;　　}　　if

78、(ch2==1||ch2==2||ch2==3)　　printf("\n\n\t\t ");/*控制格式*/　　}　　}　　計(jì)算機(jī)與通信學(xué)院課程設(shè)計(jì)評(píng)分表

眾賞文庫(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)頁內(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ǎn)介

溫馨提示

最新文檔

評(píng)論

課程設(shè)計(jì)-圖的遍歷

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載