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

.Word資料數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說(shuō)明書圖的遍歷的實(shí)現(xiàn)課程設(shè)計(jì)任務(wù)書課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：圖的遍歷實(shí)現(xiàn)完成期限：設(shè)計(jì)內(nèi)容：1.任務(wù)說(shuō)明(1)采用鄰接表存儲(chǔ)結(jié)構(gòu)創(chuàng)建一個(gè)圖；(2)編程實(shí)現(xiàn)圖的深度優(yōu)先搜索（或廣度優(yōu)先搜索）遍歷算法；(3)輸出遍歷結(jié)果；(4)給定具體數(shù)據(jù)調(diào)試程序。2.要求1）問(wèn)題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問(wèn)題，明確問(wèn)題要求做什么？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ì)語(yǔ)言程序。5）程序調(diào)試與測(cè)試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。6）結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析；7）編寫課程設(shè)計(jì)報(bào)告。3.參考資料指導(dǎo)教師：申靜教研室負(fù)責(zé)人：余冬梅課程設(shè)計(jì)評(píng)閱評(píng)語(yǔ)：指導(dǎo)教師簽名：年月日摘要針對(duì)圖問(wèn)題中如何更好地實(shí)現(xiàn)圖的遍歷問(wèn)題，以無(wú)向圖為例，分別采用廣度優(yōu)先遍歷和深度優(yōu)先遍歷的算法實(shí)現(xiàn)對(duì)各節(jié)點(diǎn)的遍歷，以VC++為開(kāi)發(fā)環(huán)境進(jìn)行系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)，其運(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ù) 22.1課程設(shè)計(jì)的目的 22.2課程設(shè)計(jì)的任務(wù) 2三 設(shè)計(jì)方案和實(shí)施 33.1總體設(shè)計(jì) 33.2基本操作 33.3詳細(xì)設(shè)計(jì) 4四運(yùn)行調(diào)試結(jié)果 6五結(jié)論與致謝 9六 附錄 11一課題描述數(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í)過(guò)程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程，要求學(xué)習(xí)者編寫的程序結(jié)構(gòu)或設(shè)計(jì)的程序結(jié)構(gòu)體清楚、正確、易讀，符合軟件工程的規(guī)范。圖是一種較為復(fù)雜且重要的數(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ì)語(yǔ)言之一—C語(yǔ)言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語(yǔ)言。二 設(shè)計(jì)目的與任務(wù)2.1課程設(shè)計(jì)的目的進(jìn)一步的了解圖的遍歷的問(wèn)題，圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)，用無(wú)向圖來(lái)實(shí)現(xiàn)圖的遍歷。初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能。訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)，熟練的完成問(wèn)題分析、算法設(shè)計(jì)、編寫程序，求解出指定的問(wèn)題。訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，鞏固、深化學(xué)生的理論知識(shí)，提高編程水平，并在此過(guò)程中培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力。2.2課程設(shè)計(jì)的任務(wù)1）任務(wù)說(shuō)明用C/C++編寫一個(gè)程序?qū)崿F(xiàn)圖的遍歷的算法。從鍵盤上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）。圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn);用有向圖實(shí)現(xiàn)圖的遍歷；用無(wú)向圖實(shí)現(xiàn)圖的遍歷；用鄰接矩陣存儲(chǔ)圖；用鄰接表存儲(chǔ)圖。2）要求1>首先輸入圖的結(jié)點(diǎn)數(shù)；2>依次輸入圖的各條邊（數(shù)據(jù)之間用空格隔開(kāi)）；3>輸出的形式：按用戶選擇的遍歷方法給出遍歷順序，各字符間用->分隔；4>程序所能達(dá)到的功能：能夠按要求輸出所要的結(jié)果。三 設(shè)計(jì)方案和實(shí)施3.1總體設(shè)計(jì)采用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)。程序中主要用到以下抽象數(shù)據(jù)類型：抽象數(shù)據(jù)類型的定義typedefstruct{char*vexs; //頂點(diǎn)向量intarcs[MAX_VEX][MAX_VEX]; //鄰接矩陣intvexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}Graph;3.2基本操作CreateUDN(Graph&G)操作結(jié)果：用鄰接矩陣創(chuàng)建帶權(quán)無(wú)向網(wǎng)圖。DFS(GraphG,intk)操作結(jié)果：對(duì)已存在的圖進(jìn)行深度優(yōu)先遍歷。BFS(GraphG)操作結(jié)果：對(duì)已存在的圖進(jìn)行廣度優(yōu)先遍歷。choose(GraphG)操作結(jié)果：對(duì)將要實(shí)現(xiàn)的操作步驟進(jìn)行選擇。程序包含兩個(gè)模塊主程序模塊，其中主函數(shù)為intmain{輸入信息；根據(jù)輸入要求進(jìn)行選擇操作和輸出；輸出結(jié)果；}選擇操作模塊—實(shí)現(xiàn)具體選擇的對(duì)應(yīng)操作及輸出操作。兩模塊之間關(guān)系如下圖3.1所示圖3.1模塊關(guān)系圖3.3詳細(xì)設(shè)計(jì)程序流程圖如圖3.2所示圖3.2程序流程圖函數(shù)設(shè)計(jì)程序設(shè)計(jì)中主要包括下列函數(shù)用鄰接矩陣創(chuàng)建一個(gè)圖：voidCreateUDN(Graph&G){用鄰接矩陣創(chuàng)建一個(gè)帶權(quán)無(wú)向網(wǎng)圖;輸入頂點(diǎn)數(shù)和弧數(shù);輸入各個(gè)頂點(diǎn)及各條弧;}遞歸方法實(shí)現(xiàn)圖的遍歷：voidDFS(GraphG,intk){用遞歸的方法訪問(wèn)圖中的結(jié)點(diǎn);對(duì)圖進(jìn)行深度優(yōu)先遍歷;}非遞歸方法實(shí)現(xiàn)圖的遍歷：voidBFS(GraphG){用隊(duì)列輔助訪問(wèn)圖中的結(jié)點(diǎn);對(duì)圖進(jìn)行廣度優(yōu)先遍歷;}選擇輸出需要的遍歷方法：voidchoose(GraphG){給出程序運(yùn)行的選項(xiàng);對(duì)相應(yīng)的輸入選項(xiàng)調(diào)用相應(yīng)的函數(shù)以執(zhí)行操作；}四運(yùn)行調(diào)試結(jié)果例：遍歷如下無(wú)向圖（圖4.1）(a,b,c,d,e分別表示V1V2V3V4V5五個(gè)頂點(diǎn))以圖4.1為例步驟一：運(yùn)行程序，按提示首先輸入頂點(diǎn)數(shù)和弧數(shù)。圖4.2輸入頂點(diǎn)數(shù)和弧數(shù)步驟二：輸入頂點(diǎn)和弧輸入頂點(diǎn)圖4.3輸入各頂點(diǎn)（2）輸入弧圖4.3輸入各條弧步驟三：選擇便利方式以及選擇后結(jié)果選擇1操作顯示廣度優(yōu)先編歷結(jié)果圖4.4廣度優(yōu)先結(jié)果選2操作顯示深度優(yōu)先遍歷圖4.4深度優(yōu)先遍歷結(jié)果五結(jié)論與致謝在程序設(shè)計(jì)中我主要是解決的是給出一個(gè)圖如何用多種方法完成圖的遍歷的問(wèn)題，也包括如何創(chuàng)建一個(gè)圖，深度優(yōu)先遍歷和廣度優(yōu)先遍歷一個(gè)圖，遞歸和非遞歸的方法實(shí)現(xiàn)圖的遍歷。程序最終通過(guò)調(diào)試運(yùn)行，初步實(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)整體上比較完美，可以從鍵盤獲取輸入元素，并且可以根據(jù)用戶輸入進(jìn)行選擇性地輸出；整體輸出畫面效果整潔、大方。這次課程設(shè)計(jì)也讓我充分認(rèn)識(shí)到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個(gè)思想和大綱，讓我們?cè)诰幊虝r(shí)容易找到思路，不至于無(wú)章可循。同時(shí)它也有廣泛的實(shí)際應(yīng)用。最后，我還要特別感謝我們的輔導(dǎo)老師申靜老師，在她的精心輔導(dǎo)和幫助下，我的設(shè)計(jì)才得以順利完成。對(duì)她為我們的設(shè)計(jì)所提出的寶貴意見(jiàn)表示忠心的感謝！參考文獻(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語(yǔ)言版].北京:清華大學(xué)出版社.[4]楊路明.C語(yǔ)言程序設(shè)計(jì)教程.北京郵電大學(xué)出版社.[5]徐孝凱.數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn).清華大學(xué)出版社.六 附錄源程序代碼//程序功能：采用遞歸和非遞歸算法，有向圖和無(wú)向圖，鄰接矩陣和鄰接表等多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)圖的遍歷。//程序作者：英茜//最后修改日期：201#include"stdio.h"#include"stdlib.h"#defineINFINITY32767#defineMAX_VEX20 //最大頂點(diǎn)個(gè)數(shù)#defineQUEUE_SIZE(MAX_VEX+1) //隊(duì)列長(zhǎng)度bool*visited; //訪問(wèn)標(biāo)志數(shù)組intz=1; //圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)typedefstruct{char*vexs; //頂點(diǎn)向量intarcs[MAX_VEX][MAX_VEX]; //鄰接矩陣intvexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}Graph;classQueue{ //隊(duì)列類public:voidInitQueue(){base=(int*)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;}voidEnQueue(inte){base[rear]=e;rear=(rear+1)%QUEUE_SIZE;}voidDeQueue(int&e){e=base[front];front=(front+1)%QUEUE_SIZE;}int*base;intfront;intrear;};intLocate(GraphG,charc){ //圖G中查找元素c的位置for(inti=0;i<G.vexnum;i++)if(G.vexs[i]==c)returni;return-1;}voidCreateUDN(Graph&G){ //創(chuàng)建無(wú)向網(wǎng)inti,j,w,s1,s2;chara,b,c,temp;printf("輸入頂點(diǎn)數(shù)和弧數(shù)(頂點(diǎn)數(shù)和弧數(shù)之間以空格隔開(kāi)):");scanf("%d%d",&G.vexnum,&G.arcnum);temp=getchar(); //接收回車G.vexs=(char*)malloc(G.vexnum*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]);temp=getchar(); //接收回車}for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;printf("輸入%d條弧.\n",G.arcnum);for(i=0;i<G.arcnum;i++){ //初始化弧printf("輸入弧%d:",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]=G.arcs[s2][s1]=w;}}intFirstVex(GraphG,intk){ //圖G中頂點(diǎn)k的第一個(gè)鄰接頂點(diǎn)if(k>=0&&k<G.vexnum){//k合理for(inti=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//圖G中頂點(diǎn)i的第j個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)intNextVex(GraphG,inti,intj){if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum){//i,j合理for(intk=j+1;k<G.vexnum;k++)if(G.arcs[i][k]!=INFINITY)returnk;}return-1;}//深度優(yōu)先遍歷voidDFS(GraphG,intk){inti;if(k==-1){ //第一次執(zhí)行DFS時(shí),k為-1for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i); //對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFS}else{visited[k]=true;if(z==1)printf("%c",G.vexs[k]);elseprintf("->%c",G.vexs[k]);++z; //訪問(wèn)第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的尚未訪問(wèn)的鄰接頂點(diǎn)i遞歸調(diào)用DFS}}//廣度優(yōu)先遍歷voidBFS(GraphG){intk;QueueQ; //輔助隊(duì)列QQ.InitQueue();for(inti=0;i<G.vexnum;i++)if(!visited[i]){ //i尚未訪問(wèn)visited[i]=true;printf("%c",G.vexs[i]);Q.EnQueue(i); //i入列while(Q.front!=Q.rear){Q.DeQueue(k); //隊(duì)頭元素出列并置為kfor(intw=FirstVex(G,k);w>=0;w=NextVex(G,k,w))if(!visited[w]){ //