1、 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告題 目： 圖的遍歷 學(xué)生姓名： 學(xué) 號(hào)： 200817020103 專(zhuān)業(yè)班級(jí)： 信管08101班 同組姓名: 指導(dǎo)教師： 設(shè)計(jì)時(shí)間： 2010年上學(xué)期第 1 周 指導(dǎo)老師意見(jiàn):評(píng)定成績(jī): 簽名: 日期:目 錄一、前言 1.1課程設(shè)計(jì)的目的與意義31.2對(duì)課程設(shè)計(jì)功能的需求分析3二、算法思想4三、數(shù)據(jù)結(jié)構(gòu)4四、模塊劃分4.1、有關(guān)隊(duì)列的一系列函數(shù)54.2、創(chuàng)建圖的函數(shù)54.3、圖的深度優(yōu)先遍歷遞歸54.4、圖的廣度優(yōu)先遍歷遞歸54.5、深度優(yōu)先遍歷54.6、廣度優(yōu)先遍歷54.7、主函數(shù)5五、系統(tǒng)的概要設(shè)計(jì)1、系統(tǒng)功能模塊圖62、各模塊流程圖7六、源程序12七、程序的調(diào)試分

2、析以及測(cè)試結(jié)果1、程序的調(diào)試分析202、程序的測(cè)試結(jié)果20八、附錄1、課程設(shè)計(jì)心得體會(huì)252、參考文獻(xiàn)26一、前言1.1課程設(shè)計(jì)的目的與意義上學(xué)期我們對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)課程進(jìn)行了學(xué)習(xí)。這門(mén)課程是一門(mén)實(shí)踐性非常強(qiáng)的課程，為了讓大家更好地理解與運(yùn)用所學(xué)知識(shí)，提高動(dòng)手能力，我們進(jìn)行了此次課程設(shè)計(jì)實(shí)習(xí)。這次課程設(shè)計(jì)不但要求我們掌握數(shù)據(jù)結(jié)構(gòu)中的各方面知識(shí)，還要求我們具備一定的c語(yǔ)言基礎(chǔ)和編程能力。通過(guò)實(shí)踐我們掌握數(shù)據(jù)結(jié)構(gòu)中的知識(shí)。對(duì)于圖的遍歷這一課題來(lái)說(shuō)，所要求我們掌握的數(shù)據(jù)結(jié)構(gòu)知識(shí)主要有：圖的存儲(chǔ)結(jié)構(gòu)、隊(duì)列的基本運(yùn)算實(shí)現(xiàn)、圖的深度優(yōu)先遍歷算法實(shí)現(xiàn)、圖的廣度優(yōu)先遍歷算法實(shí)現(xiàn)。對(duì)于我們學(xué)生來(lái)講，此次課程設(shè)計(jì)是

3、為了讓我們訓(xùn)練自己的實(shí)際設(shè)計(jì)能力，通過(guò)設(shè)計(jì)實(shí)踐，去真正獲得此項(xiàng)目管理和團(tuán)隊(duì)協(xié)作等方面的基本訓(xùn)練和工作經(jīng)驗(yàn)。通過(guò)課程設(shè)計(jì)的一系列訓(xùn)練，我們能提高如何綜合運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力，以及獲得此項(xiàng)目管理和團(tuán)隊(duì)協(xié)作等等眾多方面的具體經(jīng)驗(yàn)，增強(qiáng)對(duì)相關(guān)課程具體內(nèi)容的理解和掌握能力，培養(yǎng)對(duì)整體課程知識(shí)綜合運(yùn)用和融會(huì)貫通能力。1.2對(duì)課程設(shè)計(jì)功能的需求分析圖的遍歷并不需要是一個(gè)過(guò)于復(fù)雜的工作環(huán)境，一般來(lái)說(shuō)：最合適的才是最好的。軟件設(shè)計(jì)必須符合我們使用實(shí)際情況的需要。根據(jù)要求，圖的遍歷主要功能如下： 1、用戶(hù)可以隨時(shí)建立一個(gè)有向圖或無(wú)向圖；2、用戶(hù)可以根據(jù)自己的需要，對(duì)圖進(jìn)行深度遍歷或廣度遍歷；3、用戶(hù)可以

4、根據(jù)自己的需要對(duì)圖進(jìn)行修改；4、在整個(gè)程序中,用戶(hù)可以不斷的按照不同的方式對(duì)圖進(jìn)行遍歷,若不繼續(xù),用戶(hù)也可以隨時(shí)跳出程序,同時(shí),如果用戶(hù)輸入的序號(hào)錯(cuò)誤,程序會(huì)提示用戶(hù)重新輸入序號(hào);二、算法思想本課題本人所采用的是鄰接矩陣的方式存儲(chǔ)圖，實(shí)現(xiàn)圖的深度、廣度兩種遍歷，并將每種遍歷結(jié)果輸出來(lái)。2.1.1圖的鄰接矩陣的建立 對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），根據(jù)鄰接矩陣的存儲(chǔ)結(jié)構(gòu)建立圖的鄰接矩陣。2.1.2 圖的遍歷的實(shí)現(xiàn) 圖的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對(duì)于廣度優(yōu)先遍歷應(yīng)利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）來(lái)實(shí)現(xiàn)。首先建立一空隊(duì)列，從初始點(diǎn)出發(fā)進(jìn)行訪問(wèn)，當(dāng)被

5、訪問(wèn)時(shí)入隊(duì)，訪問(wèn)完出隊(duì)。并以隊(duì)列是否為空作為循環(huán)控制條件。對(duì)于深度優(yōu)先遍歷則采用遞歸或非遞歸算法來(lái)實(shí)現(xiàn)，這里我所采用的是遞歸算法。三、數(shù)據(jù)結(jié)構(gòu)#define max 10#define false 0#define true 1#define error printf#define queuesize 30typedef struct char vexsmax; int edgesmaxmax; int n,e;mgraph;int visitedmax;typedef struct int front; int rear; int count; int dataqueuesize;cirqu

6、eue;四、模塊劃分 4.1、隊(duì)列的初始化、進(jìn)隊(duì)、出隊(duì)、隊(duì)列空、隊(duì)列滿(mǎn)的函數(shù)； void initqueue(cirqueue *q) /初始化隊(duì)列int queueempty(cirqueue *q)/隊(duì)列是否為空int queuefull(cirqueue *q)/隊(duì)列滿(mǎn)void enqueue(cirqueue *q,int x)/將隊(duì)員進(jìn)隊(duì)int dequeue(cirqueue *q)/將隊(duì)員出隊(duì)4.2、創(chuàng)建圖的函數(shù) void createmgraph(mgraph *g)/根據(jù)用戶(hù)需要?jiǎng)?chuàng)建一個(gè)圖4.3、圖的深度優(yōu)先遍歷遞歸void dfsm(mgraph *g,int i)/*含有

7、輸出已訪問(wèn)的頂點(diǎn)的語(yǔ)句*/4.4、圖的廣度優(yōu)先遍歷遞歸 void bfsm(mgraph *g,int k) /*含有輸出已訪問(wèn)的頂點(diǎn)的語(yǔ)句*/4.5、深度優(yōu)先遍歷 void dfstraversem(mgraph *g)/*調(diào)用dfsm函數(shù)*/4.6、廣度優(yōu)先遍歷 void bfstraversem(mgraph *g) /*調(diào)用bfsm函數(shù)*/4.7、主函數(shù) main() /*包含一些調(diào)用和控制語(yǔ)句*/ 五、系統(tǒng)的概要設(shè)計(jì)進(jìn)入菜單選擇用戶(hù)登錄圖信息的錄入修改圖的信息廣度優(yōu)先遍歷圖深度優(yōu)先遍歷圖 退出程序 圖一、系統(tǒng)功能模塊圖輸入ch2登陸開(kāi)始createmgraph(g);ch1=ych1

8、=y 真 假 ch2 b r e a kch1=n 0createmgraph(g) 1dfstraversem(g) bfstraversem(g)bfstraversem(g) dfstraversem(g) dfstraversem(g) dfstraversem(g) dfstraversem(g) dfstraversem(g)dfstraversem(g) 2 bfstraversem(g) 3結(jié)束程序圖二、主函數(shù)流程圖dfstraversem(mgraph *g)i=0invisitedi=falsei+i=0 in 真!visitedi i+ 非零 零dfsm(g,i)結(jié)束程序

9、圖三、 深度優(yōu)先遍歷流程圖dfsm(mgraph *g,int i) 輸出g-vexsivisitedi=true j=0 jn 真 g-edgesij=1&!visitedjdfsm(g,i)j+結(jié)束程序圖四、 深度優(yōu)先遍歷遞歸bfstraversem(mgraph *g)i=0invisitedi=falsei+i=0 in 真!visitedi i+ 非零 零bfs(g,i)結(jié)束程序圖五、 深度優(yōu)先遍歷流程圖i=dequeue(&q) j=0 !queueempty(&q)enqueue(&q,k)visitedi=true輸出g-vexskinitqueue(&q)bfsm(mgrap

10、h *g,int k) jn 真!visitedi dfsm(g,i)i+結(jié)束程序圖六、廣度優(yōu)先遍歷遞歸流程圖六、源程序#include#include#define max 10#define false 0#define true 1#define error printf#define queuesize 30typedef struct char vexsmax; int edgesmaxmax; int n,e;mgraph;/*以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)*/int visitedmax;/*將visitedmax定義為全局變量并分配最大空間*/typedef struct int

11、front; int rear; int count; int dataqueuesize;cirqueue;/*定義隊(duì)列的數(shù)據(jù)結(jié)構(gòu)*/初始化隊(duì)列 void initqueue(cirqueue *q) q-front=q-rear=0; q-count=0;/隊(duì)列空int queueempty(cirqueue *q) return q-count=queuesize;/*返回隊(duì)列的最大長(zhǎng)度*/ /隊(duì)列滿(mǎn)int queuefull(cirqueue *q) return q-count=queuesize;/*返回隊(duì)列的最大長(zhǎng)度*/ /進(jìn)隊(duì)void enqueue(cirqueue *q,i

12、nt x) if(queuefull(q)/*隊(duì)列滿(mǎn)則出錯(cuò)*/ error(queue overflow); else q-count+;/*否則count+，將x進(jìn)隊(duì)*/ q-dataq-rear=x; q-rear=(q-rear+1)%queuesize; /出隊(duì)int dequeue(cirqueue *q) int temp;/*定義整型的變量*/ if(queueempty(q)/*若為真則出錯(cuò)*/ error(queue underflow); else/*為假則count-，將隊(duì)員出隊(duì)*/ temp=q-dataq-front;/*用temp返回其值*/ q-count-; q

13、-front=(q-front+1)%queuesize; return temp;/*返回出隊(duì)元素值*/ /建立一個(gè)圖void createmgraph(mgraph *g) int i,j,k;/*定義整型變量*/ char ch1,ch2;/*定義字符型變量*/ printf(n請(qǐng)輸入頂點(diǎn)數(shù)，邊數(shù)（格式：3，4）:); scanf(%d,%d,&(g-n),&(g-e);/*輸入圖的頂點(diǎn)數(shù)和邊數(shù)*/ for(i=0;in;i+) getchar(); printf(n請(qǐng)輸入第%d個(gè)頂點(diǎn)序號(hào),i+1); scanf(%c,&(g-vexsi);/*輸入頂點(diǎn)的序號(hào)*/ for(i=0;in;

14、i+) for(j=0;jn;j+) g-edgesij=0;/*初始化矩陣*/ for(k=0;ke;k+) getchar(); printf(n請(qǐng)輸入第%d條邊的頂點(diǎn)序號(hào)（格式：i，j）:,k+1); scanf(%c,%c,&ch1,&ch2);/*輸入邊的頂點(diǎn)序號(hào)*/ for(i=0;ch1!=g-vexsi;i+); for(j=0;ch2!=g-vexsj;j+); g-edgesij=1;/*有邊則賦值為1*/ /深度優(yōu)先遍歷遞歸 void dfsm(mgraph *g,int i) int j; printf(%c ,g-vexsi); visitedi=true;/*標(biāo)記v

15、isitedi*/ /*依次優(yōu)先搜索訪問(wèn)visitedi的每個(gè)鄰接點(diǎn)*/for(j=0;jn;j+) /*若visitedi的一個(gè)有效鄰接點(diǎn)visitedj未被訪問(wèn)過(guò)，則從visitedj出發(fā)進(jìn)行遞歸調(diào)用*/ if(g-edgesij=1&!visitedj) dfsm(g,j); /廣度優(yōu)先遍歷遞歸void bfsm(mgraph *g,int k) int i,j; cirqueue q;/*定義一個(gè)隊(duì)列q，初始化隊(duì)列為空*/ initqueue(&q); printf(%c ,g-vexsk);/*訪問(wèn)初始點(diǎn)，并將其標(biāo)記已訪問(wèn)過(guò)*/ visitedk=true; enqueue(&q,k

16、);/*將以訪問(wèn)過(guò)的初始點(diǎn)序號(hào)k入隊(duì)*/ while(!queueempty(&q)/*隊(duì)列非空進(jìn)行循環(huán)處理*/ i=dequeue(&q);/*將隊(duì)首元素出隊(duì)*/ for(j=0;jn;j+)/*依次搜索vexsk的每一個(gè)可能的鄰接點(diǎn)*/ if(g-edgesij=1 &! visitedj) visitedj=true;/*標(biāo)記vexsj已訪問(wèn)過(guò)*/ enqueue(&q,j);/*頂點(diǎn)序號(hào)j入隊(duì)*/ /深度優(yōu)先遍歷void dfstraversem(mgraph *g) int i; printf(n 深度優(yōu)先遍歷序列:);for(i=0;in;i+) visitedi=false;/*

17、訪問(wèn)標(biāo)志數(shù)組初始化*/ for(i=0;in;i+) if(!visitedi)/*對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用dfsm*/ dfsm(g,i); /廣度優(yōu)先遍歷void bfstraversem(mgraph *g) int i; printf(n 廣度優(yōu)先遍歷序列:);for(i=0;in;i+) visitedi=false;/*訪問(wèn)標(biāo)志數(shù)組初始化*/ for(i=0;in;i+) if(!visitedi)/*對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用bfsm*/ bfsm(g,i); main() mgraph *g,a; char ch1; int i,j,ch2; g=&a;printf(ntt 深度優(yōu)先搜索

18、和廣度優(yōu)先搜索 n); createmgraph(g);/*調(diào)用創(chuàng)建圖矩陣的函數(shù)*/ getchar(); ch1=y;/*設(shè)置控制語(yǔ)句標(biāo)志*/ while(ch1=y|ch1=y) /*菜單欄*/ printf(n); printf( 選擇菜單); printf(ntt*n); printf(tt* 更改數(shù)據(jù)請(qǐng)按:1 *n); printf(tt* 深度優(yōu)先搜索請(qǐng)按:2 *n); printf(tt* 廣度優(yōu)先搜索請(qǐng)按:3 *n); printf(tt* 退出搜索請(qǐng)按:0 *n); printf(tt*n); printf(ntt請(qǐng)選擇菜單號(hào)（0-3）：); scanf(%d,&ch2);

19、getchar(); switch(ch2) case 1: createmgraph(g);/*選1創(chuàng)建一個(gè)新的圖矩陣*/ break; case 2: dfstraversem(g);/*選2進(jìn)入深度優(yōu)先搜索*/ break; case 3: bfstraversem(g);/*選3進(jìn)入廣度優(yōu)先搜索*/ break; case 0:/*選0結(jié)束搜索，退出程序*/ ch1=n; break; default: system(cls); printf(ntt輸入有誤！n); break; if(ch2=1|ch2=2|ch2=3) printf(nntt );/*控制格式*/ 七、程序的調(diào)試分

20、析以及測(cè)試結(jié)果7.1程序的調(diào)試分析在調(diào)試過(guò)程中，程序中出現(xiàn)了許多的錯(cuò)誤，有錯(cuò)誤的調(diào)用、一些變量沒(méi)有定義、等等。不斷的對(duì)程序進(jìn)行調(diào)試以得到最好的結(jié)果，程序中特別要注意的是類(lèi)的對(duì)象作為作為參數(shù)時(shí)要注意如何去調(diào)用它，使程序有一個(gè)令人滿(mǎn)意的結(jié)果，具體的調(diào)試是在上機(jī)過(guò)程中進(jìn)行的，在編寫(xiě)程序的過(guò)程中主要有如下錯(cuò)誤：1、在編寫(xiě)程序的過(guò)程出現(xiàn)了一些函數(shù)名、變量的大小寫(xiě)不統(tǒng)一的錯(cuò)誤，導(dǎo)致程序在運(yùn)行的過(guò)程中出現(xiàn)函數(shù)名、變量沒(méi)有被定義等問(wèn)題；2、在編寫(xiě)程序的過(guò)程中數(shù)組的大小寫(xiě)沒(méi)有被確定；3、在編寫(xiě)程序的過(guò)程中一些變量沒(méi)有被定義，導(dǎo)致程序出錯(cuò)；4、數(shù)組visitedmax應(yīng)定義為全局變量，若不是則會(huì)出錯(cuò)；5、函數(shù)的返

21、回類(lèi)型要確定，是void還是其他類(lèi)型要十分注意；6、在編程的過(guò)程中，函數(shù)里一些控制語(yǔ)句的嵌套使用，括號(hào)要引起注意，這次的課程設(shè)計(jì)就有一些括號(hào)漏了或者多打了，導(dǎo)致括號(hào)不配套；7.2、程序的測(cè)試結(jié)果 7.2.1、初始進(jìn)入程序時(shí)，程序提示按格式輸入圖的頂點(diǎn)個(gè)數(shù)和邊數(shù)。7.2.2、輸入頂點(diǎn)數(shù)和邊數(shù)后，程序提示輸入頂點(diǎn)的序號(hào)，為各頂點(diǎn)依次進(jìn)行編號(hào)。7.2.3、將各頂點(diǎn)進(jìn)行編號(hào)后，程序提示按格式輸入邊的頂點(diǎn)序號(hào)。 7.2.4、按格式依次輸入邊的頂點(diǎn)序號(hào)后，按enter鍵程序會(huì)出現(xiàn)“選擇菜單”，用戶(hù)根據(jù)需要進(jìn)行選擇。 7.2.5、用戶(hù)選擇2進(jìn)入深度優(yōu)先搜索，并輸出深度優(yōu)先遍歷后的序列，再次輸出菜單欄，進(jìn)行選擇。 7.2.7、用戶(hù)再次選擇3進(jìn)入廣度優(yōu)先搜索，并輸出廣度優(yōu)先遍歷后的序列，再次輸出菜單欄，進(jìn)行選擇。 7.2.8、用戶(hù)選擇1后進(jìn)入更改數(shù)據(jù)，重新創(chuàng)建一個(gè)圖。 6.2.9、用戶(hù)選擇0，則退出程序。八、附錄5.1、課程設(shè)計(jì)心得體會(huì) 心得體會(huì) 通過(guò)這近一個(gè)星期的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)踐，我學(xué)到了很多東西。本次課程設(shè)計(jì)對(duì)我來(lái)說(shuō)正是一個(gè)提高自己能力的機(jī)會(huì)，我好好的抓住機(jī)會(huì)，努力做好每一步，完善每一步。自己的c語(yǔ)言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固，編程能力也有了一定的提高。同時(shí)也學(xué)會(huì)了解決問(wèn)題的方法。總結(jié)起來(lái)，自己主要有以下幾點(diǎn)體會(huì)：1.必須牢固掌握基礎(chǔ)知識(shí)。由于c