《校園導(dǎo)游咨詢系統(tǒng)》數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說(shuō)明書(shū)

1、【精品文檔】如有侵權(quán)，請(qǐng)聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流校園導(dǎo)游咨詢系統(tǒng)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說(shuō)明書(shū).精品文檔.中北大學(xué)數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計(jì) 說(shuō) 明 書(shū)學(xué)生姓名:劉安光學(xué) 號(hào)：1507084143學(xué)生姓名:劉晨馨學(xué) 號(hào)：1507084103學(xué)生姓名:古文慧學(xué) 號(hào)：1507084118學(xué)生姓名:周順?lè)珜W(xué) 號(hào)：1507084114學(xué) 院:計(jì)算機(jī)與控制工程學(xué)院專 業(yè):網(wǎng)絡(luò)工程專業(yè)題 目:校園導(dǎo)游咨詢系統(tǒng)指導(dǎo)教師梁志劍、張建華2016 年 12月30日目錄1設(shè)計(jì)目的12設(shè)計(jì)內(nèi)容13設(shè)計(jì)要求14模塊分工15數(shù)據(jù)結(jié)構(gòu)26詳細(xì)設(shè)計(jì)36.1 主函數(shù)模塊36.1.1 詳細(xì)設(shè)計(jì)思想36.1.2 核心代碼46.2 圖

2、的建立模塊46.2.1詳細(xì)設(shè)計(jì)思想46.2.2 核心代碼56.3 信息查詢模塊66.3.1詳細(xì)設(shè)計(jì)思想66.3.2 核心代碼76.4 兩景點(diǎn)最短路徑模塊86.4.1詳細(xì)設(shè)計(jì)思想86.4.2 核心代碼106.5 多景點(diǎn)最佳路徑模塊126.5.1詳細(xì)設(shè)計(jì)思想126.5.2 核心代碼126.6 求圖的關(guān)節(jié)點(diǎn)模塊136.6.1詳細(xì)設(shè)計(jì)思想136.6.2 核心代碼156.7 兩景點(diǎn)所有路徑模塊176.7.1詳細(xì)設(shè)計(jì)思想176.7.2 核心代碼186.8 游客及管理員菜單模塊196.8.1詳細(xì)設(shè)計(jì)思想196.8.2 核心代碼207源碼文件257.1 源碼257.2 文本文件307.2.1 map.txt3

3、07.2.2 liuyan.txt318運(yùn)行截圖328.1 主菜單界面與功能一覽328.2 中北校園景點(diǎn)信息查詢328.3 兩景點(diǎn)間最短路徑查詢328.4 兩景點(diǎn)間所有路徑查詢338.5 多景點(diǎn)間訪問(wèn)路線查詢338.6 輸出校園景點(diǎn)圖關(guān)節(jié)點(diǎn)338.7 公告查看及游客留言欄348.8 景點(diǎn)管理員后臺(tái)管理欄358.9 退出校園導(dǎo)游咨詢系統(tǒng)369經(jīng)驗(yàn)總結(jié)379.1 關(guān)于分工379.2 關(guān)于答辯371設(shè)計(jì)目的數(shù)據(jù)結(jié)構(gòu)課程主要介紹最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)單的分析和討論。進(jìn)行數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)要達(dá)到

4、以下目的：（1）了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；（2）初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；（3）提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。2設(shè)計(jì)內(nèi)容設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪的客人提供各種信息查詢服務(wù)。（1）設(shè)計(jì)中北大學(xué)的校園平面圖，所含景點(diǎn)不少于10個(gè)，以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。（2）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。（3）為來(lái)訪客人

5、提供圖中任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨上嗑包c(diǎn)之間的一條最短的簡(jiǎn)單路徑。（4）求校園圖的關(guān)節(jié)點(diǎn)。（5）提供圖中任意景點(diǎn)問(wèn)路查詢，即求任意兩個(gè)景點(diǎn)之間的所有路徑。（6）提供校園圖中多個(gè)景點(diǎn)的最佳訪問(wèn)路線查詢，即求途經(jīng)這多個(gè)景點(diǎn)的最佳路徑。3設(shè)計(jì)要求（1）符合課題要求，實(shí)現(xiàn)相應(yīng)功能；（2）要求界面友好美觀，操作方便易行；（3）注意程序的實(shí)用性、安全性；4模塊分工劉安光：主函數(shù)模塊、求圖的關(guān)節(jié)點(diǎn)模、兩景點(diǎn)所有路徑模塊。劉晨馨：兩景點(diǎn)最短路徑模塊、多景點(diǎn)最佳路徑模塊。古文慧：游客菜單模塊、管理員菜單模塊。周順?lè)簣D的建立及輸出模塊、信息查詢模塊。5數(shù)據(jù)結(jié)構(gòu)該程序用到的是圖的數(shù)據(jù)結(jié)構(gòu)，其中用到的是圖的鄰

6、接矩陣存儲(chǔ)結(jié)構(gòu)。#define INFINITY 9999 /*此處用9999代表無(wú)窮大*/#define M 20 /*最大頂點(diǎn)數(shù)*/typedef struct /*景點(diǎn)信息結(jié)構(gòu)定義*/int num; /*景點(diǎn)代號(hào)*/char name20; /*景點(diǎn)名稱*/char intro200; /*景點(diǎn)簡(jiǎn)介*/vertexType; /*鄰接矩陣頂點(diǎn)結(jié)構(gòu)*/typedef int edgeType; /*權(quán)值類型*/typedef struct /*校園景點(diǎn)圖結(jié)構(gòu)體定義*/vertexType vexsM; /*頂點(diǎn)值類型*/edgeType edgsMM; /*邊權(quán)值類型-距離*/ int

7、vexNum, edgNum; /*圖頂點(diǎn)總數(shù)與邊數(shù)*/mgraphType; /*鄰接矩陣結(jié)構(gòu)*/*函數(shù)一覽表*/void main(); /*主函數(shù)*/ int Menu(); /*主菜單*/void Creat_Map(mgraphType *g); /*從文件讀取信息建立圖*/void Dis_Map(); /*顯示校園景點(diǎn)地圖*/void Admin_Menu(mgraphType *g); /*管理員菜單*/void Tour_Menu(mgraphType *g); /*游客菜單*/ int Judeg_Innum(int num); /*判斷輸入的編號(hào)是否合理*/void Se

8、arch_Intro(mgraphType *g); /*景點(diǎn)信息查詢*/void ShortestPath_FLD(mgraphType *g); /*弗洛伊德算法求景點(diǎn)間最短的路徑*/void Floyd_Print(mgraphType,int,int); /*遞歸實(shí)現(xiàn)打印兩點(diǎn)間的最短路徑*/void ShortestPath_Print(mgraphType); /*輸出并打印兩點(diǎn)間的最短路徑*/void Dfs_Allpath(mgraphType,int,int); /*深度優(yōu)先遍歷查詢兩景點(diǎn)間所有路徑*/void Allpath_Print(mgraphType *g); /*查

9、詢兩景點(diǎn)之間的所有路徑并打印*/void Bestpath_Multispot(mgraphType); /*多景點(diǎn)間求最佳路徑*/void Dfs_Coila(mgraphType *g, int i); /*深度遍歷找關(guān)節(jié)點(diǎn)*/void Coila_Query(mgraphType *g); /*求校園交通圖關(guān)節(jié)點(diǎn)*/void System_Exit(int *quit); /*退出系統(tǒng)函數(shù)*/6詳細(xì)設(shè)計(jì)6.1 主函數(shù)模塊6.1.1 詳細(xì)設(shè)計(jì)思想圖1 主函數(shù)模塊6.1.2 核心代碼/*主函數(shù)*/void main()int quit=0;mgraphType g; Creat_Map(&a

10、mp;g); /*從文件讀取信息建立圖*/ ShortestPath_FLD(&g); /*floyed求dist與path*/ while(!quit) /*系統(tǒng)退出條件滿足判定*/ switch(menu() /*打印主菜單等待輸入項(xiàng)*/ case 1: Dis_Map();Search_Intro(&g);break; /*中北校園景點(diǎn)信息查詢*/ case 2: Dis_Map();ShortestPath_Print(&g); break; /*兩景點(diǎn)間最短路徑查詢*/ case 3: Dis_Map();Allpath_Print(&g); brea

11、k; /*兩景點(diǎn)間所有路徑查詢*/ case 4: Dis_Map();Bestpath_Multispot(&g);break; /*多景點(diǎn)間訪問(wèn)路線查詢*/ case 5: Dis_Map();Coila_Query(&g);break; /*輸出校園景點(diǎn)圖關(guān)節(jié)點(diǎn)*/ case 6: Dis_Map();Tour_Menu(&g);break; /*公告查看及游客留言欄*/ case 7: Dis_Map();Admin_Menu(&g);break; /*景點(diǎn)管理員后臺(tái)管理欄*/ case 8: System_Exit(&quit);break;

12、/*退出校園導(dǎo)游咨詢系統(tǒng)*/ default:printf("錯(cuò)誤！沒(méi)有該選項(xiàng)對(duì)應(yīng)的操作。"); /*按錯(cuò)選項(xiàng)反饋錯(cuò)誤信息*/ system("pause"); system("cls");6.2 圖的建立模塊6.2.1詳細(xì)設(shè)計(jì)思想當(dāng)建立圖存儲(chǔ)結(jié)構(gòu)時(shí)，圖的信息以三元組（i，j，w）的形式輸入，i、j分別表示兩頂點(diǎn)的序號(hào)，w表示邊權(quán)。圖的頂點(diǎn)信息則時(shí)按照編號(hào)、名字、簡(jiǎn)介的方式的方式在文件中存儲(chǔ)。先初始化鄰接矩陣，然后打開(kāi)文件，若文件不為空則先讀入頂點(diǎn)數(shù)與邊數(shù)信息，然后按文件中所給信息初始化鄰接矩陣的每個(gè)頂點(diǎn)，處理完定點(diǎn)后，把文件中的邊權(quán)

13、信息讀入到鄰接矩陣中建立無(wú)向圖，最后關(guān)閉文件，以待稍后輸出。如果文件不能打開(kāi)，將無(wú)向圖的頂點(diǎn)賦值為零。具體流程如下圖（圖2 圖的建立）所示。圖2 圖的建立6.2.2 核心代碼/*校園景點(diǎn)圖的讀取與創(chuàng)建*/void Creat_Map(mgraphType *g) /*從文件讀取圖的信息并建立圖*/ int i, j, k, e; FILE *rf; /*定義帶緩沖的文件指針*/rf = fopen("map.txt","r"); /*從文件讀取圖的邊信息*/if(rf) /*讀入圖的頂點(diǎn)數(shù)和邊數(shù)*/fscanf(rf,"%d%d",&

14、amp;g->vexNum, &g->edgNum); /*讀入圖的頂點(diǎn)數(shù)與邊數(shù)*/for(i=0; i<g->vexNum; i+) /*讀入圖的頂點(diǎn)信息*/fscanf(rf,"%d%s%s",&g->vexsi.num,g->,g->ro);for(i=0; i<g->vexNum; i+) /*初始化領(lǐng)接矩陣*/for(j=0; j<g->vexNum; j+)if(i=j) g->edgsij=0; /*到本點(diǎn)的距離為0其余不可達(dá)*/els

15、e g->edgsij=INFINITY;for(k=0; k<g->edgNum; k+) /*讀入圖的邊權(quán)，建立無(wú)向圖*/fscanf(rf,"%d%d%d",&i,&j,&e); /*文件以三元組形式存儲(chǔ)圖信息*/g->edgsij=g->edgsji=e; /*建立無(wú)向圖*/fclose(rf); /*關(guān)閉文件*/else g->edgNum=0;6.3 信息查詢模塊6.3.1詳細(xì)設(shè)計(jì)思想信息查詢?yōu)楸境绦蚬δ芤唬谶\(yùn)行此功能時(shí)需要用到Judeg_Innum函數(shù)。先提示用戶按顯示的地圖上的景點(diǎn)輸入對(duì)應(yīng)的編號(hào)進(jìn)

16、行查詢。等待用戶輸入完編號(hào)后，讀入游客輸入要查詢的景點(diǎn)編號(hào)，然后用Judeg_Innum函數(shù)判斷輸入的編號(hào)，如果游客輸入值為-1，表示用戶結(jié)束輸入，則Judeg_Innum函數(shù)返回-1并結(jié)束信息查詢。如果游客輸入值不為-1，判斷游客輸入值是否合理（即是否在1-12范圍類以及對(duì)應(yīng)景點(diǎn)是否關(guān)閉），不合理的話提示游客輸入有誤，返回1，等待用戶再次輸入。如果游客輸入正確的話，再次判斷查詢的景點(diǎn)是否關(guān)閉，如果景點(diǎn)關(guān)閉，輸出景點(diǎn)關(guān)閉及原因并返回1。如果Judeg_Innum函數(shù)返回值為1，跳回開(kāi)始，返回值不為-1和1，輸出景點(diǎn)名稱簡(jiǎn)介并結(jié)束。流程圖如下圖（圖3 信息查詢）所示。圖3 信息查詢6.3.2 核

17、心代碼/*景點(diǎn)信息查詢*/void Search_Intro(mgraphType *g) int s;doprintf("n請(qǐng)輸入你要查找的景點(diǎn)編號(hào)：");scanf("%d",&s); /*輸入的編號(hào)比實(shí)際景點(diǎn)編號(hào)大1*/while(judeg_Innum(s);printf("n景點(diǎn)名稱：%snn",g->);printf("景點(diǎn)簡(jiǎn)介： %snn",g->ro);/*判斷用戶輸入的編號(hào)是否合理及對(duì)應(yīng)景點(diǎn)是否開(kāi)放*/int judeg_Innum

18、(int num)int i=0;if(num=-1) return i;if(num<1|num>12)printf("nttt你輸入的景點(diǎn)編號(hào)有誤，請(qǐng)輸入1-12之間的數(shù)！nn");i=1;else if (cloNumnum-1.close=INFINITY)printf("nttt%s暫時(shí)無(wú)法游覽！n",cloN);printf("ntt關(guān)閉原因：%sn",cloNumnum-1.reason);i=1;return i;6.4 兩景點(diǎn)最短路徑模塊6.4.1詳細(xì)設(shè)計(jì)思想用floyed算法通過(guò)

19、一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=a(i,j) n×n開(kāi)始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一個(gè)公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長(zhǎng)度，稱D(n)為圖的距離矩陣，同時(shí)還可引入一個(gè)后繼節(jié)點(diǎn)矩陣path來(lái)記錄兩點(diǎn)間的最短路徑。具體算法思想如下：（1）從任意一條單邊路徑開(kāi)始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒(méi)有邊相連，則權(quán)為無(wú)窮大。（2）對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得

20、從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。（3）把圖用鄰接矩陣G表示出來(lái)，如果從Vi到Vj有路可達(dá)，則Gij=d，d表示該路的長(zhǎng)度；否則Gij=無(wú)窮大。定義一個(gè)矩陣D用來(lái)記錄所插入點(diǎn)的信息，Dij表示從Vi到Vj需要經(jīng)過(guò)的點(diǎn)，初始化Dij=j。把各個(gè)頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來(lái)的距離，Gij = min( Gij, Gik+Gkj )，如果Gij的值變小，則Dij=k。在G中包含有兩點(diǎn)之間最短道路的信息，而在D中則包含了最短通路徑的信息。比如，要尋找從V5到V1的路徑。根據(jù)D，假如D(5,1)=3則說(shuō)明從V5到V1經(jīng)過(guò)V3，路徑為V5,V3,V1，如果D(5,3)=3，

21、說(shuō)明V5與V3直接相連，如果D(3,1)=1，說(shuō)明V3與V1直接相連。進(jìn)入該功能時(shí)，系統(tǒng)會(huì)首先提醒用戶輸入起點(diǎn)與終點(diǎn)編號(hào)，具體流程如圖5所示，待編號(hào)無(wú)誤后，利用floyed算法得出兩點(diǎn)間最短距離，算法流程如下。圖4 弗洛伊德算法求兩景點(diǎn)間的一條最短的路徑圖5 輸出并打印兩點(diǎn)間的最短路徑6.4.2 核心代碼/*弗洛伊德算法求兩景點(diǎn)間的一條最短的路徑*/int distMM; /*距離向量類型*/int pathMM; /*路徑類型*/void ShortestPath_FLD(mgraphType *g) /*弗洛伊德算法求兩景點(diǎn)間的一條最短的路徑并輸出所經(jīng)結(jié)點(diǎn)*/int i, j, k;for

22、(i=0; i<g->vexNum; i+) /*初始化距離向量與路徑向量矩陣*/for(j=0; j<g->vexNum; j+)distij=g->edgsij;if(i!=j&&distij<INFINITY) pathij=i;else pathij=-1; /*-1代表當(dāng)前兩點(diǎn)不可達(dá)*/for(k=0; k<g->vexNum; k+) /*遞推求解每?jī)删包c(diǎn)的最短路徑*/for(i=0; i<g->vexNum; i+)for(j=0; j<g->vexNum; j+) /*更新distij的值*

23、/if(distij>(distik+distkj)distij=distik+distkj; pathij=k; /*path用于記錄最短路徑上的結(jié)點(diǎn)*/*遞歸實(shí)現(xiàn)打印兩點(diǎn)間的最短路徑*/void Floyd_Print(mgraphType *g, int sNum, int eNum) if(pathsNumeNum=-1|pathsNumeNum=eNum|pathsNumeNum=sNum) return;else Floyd_Print(g,sNum,pathsNumeNum ); /*將中間點(diǎn)作為終點(diǎn)繼續(xù)打印路徑*/printf("%s->",g-

24、>vexspathsNumeN); /*打印中間景點(diǎn)名字*/Floyd_Print(g,pathsNumeNum,eNum); /*將中間點(diǎn)作為起點(diǎn)繼續(xù)打印路徑*/6.5 多景點(diǎn)最佳路徑模塊6.5.1詳細(xì)設(shè)計(jì)思想用戶依次輸入節(jié)點(diǎn)編號(hào)，即游覽順序。根據(jù)Floyd算法，算出第一個(gè)景點(diǎn)和第二個(gè)景點(diǎn)的最短路徑，依次類推，算出多景點(diǎn)的最短路徑。具體流程如下圖所示。圖6 多景點(diǎn)求最佳路徑6.5.2 核心代碼/*多景點(diǎn)間求最佳路徑*/void Bestpath_Multispot(mgraphType *g) int vNumM=0,j=1; /*記錄用戶輸入的編號(hào)信息*/int d=0

25、; /*統(tǒng)計(jì)全程總長(zhǎng)*/printf("請(qǐng)輸入你要游覽的第%d個(gè)景點(diǎn)的編號(hào)（輸入-1結(jié)束輸入）：",j);scanf("%d",&vNumj-1);while(vNumj-1!=-1&&j<12)while(judeg_Innum(vNumj-1)printf("請(qǐng)輸入你要游覽的第%d個(gè)景點(diǎn)編號(hào)：",j);scanf("%d", &vNumj-1);if(vNumj-1=-1) break;printf("請(qǐng)輸入你要游覽的第%d個(gè)景點(diǎn)編號(hào)：",+j);sca

26、nf("%d", &vNumj-1);printf("n這是最佳訪問(wèn)路徑：");for(int i=0; vNumi>0&&vNumi+1>0; i+)printf("%s->",g->vexsvN); /*輸出路徑上的起點(diǎn)*/Floyd_Print(g,vNumi-1,vNumi+1-1); /*利用佛洛依德算法*/d+=distvNumi-1vNumi+1-1;printf("%snn",g->vexsvN); /

27、*輸出路徑上的終點(diǎn)*/printf("全程總長(zhǎng)為：%dmnn",d);6.6 求圖的關(guān)節(jié)點(diǎn)模塊6.6.1詳細(xì)設(shè)計(jì)思想通過(guò)深搜優(yōu)先生成樹(shù)來(lái)判定。從任一點(diǎn)出發(fā)深度優(yōu)先遍歷得到優(yōu)先生成樹(shù)，對(duì)于樹(shù)中任一頂點(diǎn)而言，其孩子節(jié)點(diǎn)為鄰接點(diǎn)。由深度優(yōu)先生成樹(shù)可得出兩類割點(diǎn)的特性：（）若生成樹(shù)的根有兩棵或兩棵以上的子樹(shù)，則此根頂點(diǎn)必為割點(diǎn)。因?yàn)閳D中不存在連接不同子樹(shù)頂點(diǎn)的邊，若刪除此節(jié)點(diǎn)，則樹(shù)便成為森林；（）若生成樹(shù)中某個(gè)非葉子頂點(diǎn)V，其某棵子樹(shù)的根和子樹(shù)中的其他節(jié)點(diǎn)均沒(méi)有指向V的祖先的回邊，則V為割點(diǎn)。因?yàn)閯h去v，則其子樹(shù)和圖的其它部分被分割開(kāi)來(lái)。仍然利用深搜算法，只不過(guò)在這里定義visit

28、edv表示為深度優(yōu)先搜索遍歷圖時(shí)訪問(wèn)頂點(diǎn)v的次序號(hào)，定義lowv=Minvisitedv，loww，visitedk，其中w是頂點(diǎn)v在深度優(yōu)先生成樹(shù)上的孩子節(jié)點(diǎn)；k是頂點(diǎn)v在深度優(yōu)先生成樹(shù)上由回邊聯(lián)結(jié)的祖先節(jié)點(diǎn)。割點(diǎn)判定條件：如果對(duì)于某個(gè)頂點(diǎn)v，存在孩子節(jié)點(diǎn)w且loww>=visitedv，則該頂點(diǎn)v必為關(guān)節(jié)點(diǎn)。因?yàn)楫?dāng)w是v的孩子節(jié)點(diǎn)時(shí)，loww>=visitedv，表明w及其子孫均無(wú)指向v的祖先的回邊，那么當(dāng)刪除頂點(diǎn)v后，v的孩子節(jié)點(diǎn)將于其他節(jié)點(diǎn)被分割開(kāi)來(lái)，從來(lái)形成新的連通分量。流程圖如下。圖7 深度遍歷找關(guān)節(jié)點(diǎn)圖8 求校園交通圖關(guān)節(jié)點(diǎn)6.6.2 核心代碼/*深度遍歷找關(guān)節(jié)點(diǎn)*/

29、#define ROOT -1 /*根節(jié)點(diǎn)標(biāo)記*/ #define COILA 1 /*關(guān)節(jié)點(diǎn)標(biāo)記*/int visiM，coilaM=0; /*根節(jié)點(diǎn)標(biāo)記或訪問(wèn)標(biāo)記及關(guān)節(jié)點(diǎn)*/int coilaNum; /*統(tǒng)計(jì)校園圖關(guān)節(jié)點(diǎn)數(shù)目*/void Dfs_Coila(mgraphType *g, int i) int child=0; /*用于統(tǒng)計(jì)結(jié)點(diǎn)子樹(shù)數(shù)目*/if(visii!=ROOT)visii=1; /*將不是根結(jié)點(diǎn)的i結(jié)點(diǎn)標(biāo)記為已訪問(wèn)*/for(int j=0; j<g->vexNum; j+)if(g->edgsij!= 0 && g->edg

30、sij!= INFINITY && !visij) /*表明i結(jié)點(diǎn)與j結(jié)點(diǎn)之間可達(dá)，且j結(jié)點(diǎn)未被訪問(wèn)*/child+; /*i結(jié)點(diǎn)子樹(shù)加一*/Dfs_Coila(g, j); /*遞歸，對(duì)j結(jié)點(diǎn)執(zhí)行同樣的操作*/if(visii = ROOT && child >= 2) /*若該點(diǎn)是根并有大于等于2的子樹(shù)*/ coilaNum+; /*關(guān)節(jié)點(diǎn)總數(shù)加一*/ coilai=COILA; /*將該點(diǎn)標(biāo)記為關(guān)節(jié)點(diǎn)*/ /*求校園交通圖關(guān)節(jié)點(diǎn)*/void Coila_Query(mgraphType *g) /*關(guān)節(jié)點(diǎn)查詢*/coilaNum = 0; /*關(guān)節(jié)點(diǎn)

31、數(shù)目初始化*/ for(int i=0; i<g->vexNum; i+) /*對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行DFS*/memset(visi, 0, sizeof(visi); /*標(biāo)記數(shù)組初始化*/visii = ROOT; /*DFS之前，將該點(diǎn)標(biāo)記為根節(jié)點(diǎn)*/ Dfs_Coila(g, i); /*深度遍歷找關(guān)節(jié)點(diǎn)*/printf("ttt校園圖的關(guān)節(jié)點(diǎn)個(gè)數(shù)為：%dnnttt分別為:", coilaNum);for(int i=0; i<g->vexNum; i+) /*遍歷輸出關(guān)節(jié)點(diǎn)*/ if(coilai = COILA) printf("%s

32、t", g->); 6.7 兩景點(diǎn)所有路徑模塊6.7.1詳細(xì)設(shè)計(jì)思想兩景點(diǎn)間所有路徑的查詢依然是采用的DFS算法，每一次將起點(diǎn)壓入棧內(nèi)，并將其標(biāo)記為已訪問(wèn)，然后檢查其是否有未訪問(wèn)的鄰接點(diǎn)，然后將其鄰接點(diǎn)作為起點(diǎn)采取深度搜索做相同的操作，若遇到路不通的時(shí)候，依次將棧內(nèi)的點(diǎn)推出，找其下一個(gè)未訪問(wèn)的鄰接點(diǎn)，直到找到終點(diǎn)，算法結(jié)束。算法結(jié)合DFS與遞歸的方式，效率不高但很容易理解，具體實(shí)現(xiàn)如下圖所示。圖9 深度優(yōu)先遍歷查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的所有路徑6.7.2 核心代碼/*深度優(yōu)先遍歷查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的所有路徑*int pathStackM,top,count /

33、*路徑棧,棧頂及路徑計(jì)數(shù)器*/int visitedM /*入棧(訪問(wèn))標(biāo)記*/ void Dfs_Allpath(mgraphType *g,int sNum, int eNum)int dis=0;pathStacktop=sNum; top+; /*將本趟起點(diǎn)入棧*/visitedsNum=1; /*將入棧點(diǎn)標(biāo)記為已入棧*/for(int i=0; i<g->vexNum; i+) /*表明兩點(diǎn)可達(dá)，且該點(diǎn)未未被訪問(wèn)*/if(g->edgssNumi>0&&g->edgssNumi!=INFINITY&&!visitedi)

34、if(i=eNum) /*如果深搜到了終點(diǎn)，就輸出剛才的路徑*/printf("第%d條路:",count+);for(int j=0; j<top; j+)printf("%s->",g->vexspathS);if(j<top-1) /*統(tǒng)計(jì)路徑長(zhǎng)度*/dis=dis+g->edgspathStackjpathStackj+1; dis=dis+g->edgspathStacktop-1eNum; printf("%sn",g->vexseN);print

35、f("總長(zhǎng)度是：%dmnn",dis);else /*如果該點(diǎn)不是終點(diǎn),接著深度搜索*/Dfs_Allpath(g,i,eNum); top-; /*支路全被訪問(wèn)一遍后，頂點(diǎn)出棧*/visitedi=0; /*將出棧點(diǎn)標(biāo)記為已出棧，允許下次訪問(wèn)*/6.8 游客及管理員菜單模塊6.8.1詳細(xì)設(shè)計(jì)思想游客菜單的功能有：1.查看公告、2.我要留言。分別對(duì)應(yīng)查看管理員發(fā)布的公告以及留言給管理員的功能。這兩項(xiàng)功能的靈感均來(lái)自校園網(wǎng)認(rèn)證的網(wǎng)頁(yè)，登錄校園網(wǎng)時(shí)我們不僅能及時(shí)從公告中獲取很多重要消息，也能通過(guò)留言反饋功能反饋?zhàn)约涸谑褂眯@網(wǎng)中遇到的問(wèn)題，對(duì)于游客來(lái)說(shuō)，同樣如此，所以這兩項(xiàng)功能

36、是必要的。管理員菜單的功能有：1. 關(guān)閉某景點(diǎn)的游覽、2.恢復(fù)某景點(diǎn)的游覽、3.發(fā)布公告、4.查看游客留言。管理員菜單的功能主要體現(xiàn)在能夠關(guān)閉景點(diǎn)的游覽和發(fā)布公告，對(duì)于現(xiàn)實(shí)生活中，這兩項(xiàng)功能都是比較貼合實(shí)際的。這樣游客就能及時(shí)知道哪些景點(diǎn)不能游覽或者哪條路無(wú)法通行。具體實(shí)現(xiàn)如下方圖10及圖11所示。圖10 游客菜單圖11 管理員菜單6.8.2 核心代碼/*管理員菜單*/structchar name20;int close;int reason100;cloNumM;char Affiche200="NULL" /*公告*/void Admin_Menu(mgraphTyp

37、e *g)char buf1024; /*緩沖區(qū)*/int len; /*行字符個(gè)數(shù)*/FILE *fp;int s=1,num,account=0,password=0;while(account!=150708|password!=150708)printf("請(qǐng)輸入你的管理賬號(hào)：");scanf("%d",&account);printf("n請(qǐng)輸入你的管理密碼：");scanf("%d",&password);if(account!=150708|password!=150708)print

38、f("tttt賬號(hào)或密碼錯(cuò)誤，請(qǐng)重新輸入！n");elseprintf("nttttttt登錄成功！nn");Sleep (1000);while(s>0&&s<5)system("cls");Dis_Map();printf("1.關(guān)閉景點(diǎn)2.恢復(fù)景點(diǎn)3.發(fā)布公告 4.查看留言 n");printf("tn請(qǐng)選擇你的操作（其余按鍵返回主菜單）：");scanf("%d",&s);switch(s)case 1:printf("n

39、請(qǐng)輸入你要關(guān)閉景點(diǎn)的編號(hào)：");scanf("%d",&num);if(num<0|num>12) printf("ntttt對(duì)不起，沒(méi)有該編號(hào)對(duì)應(yīng)的景點(diǎn)n");elsecloNumnum-1.close=INFINITY;strcpy(cloN,g->);printf("n關(guān)閉景點(diǎn)成功，請(qǐng)輸入關(guān)閉%s的原因：",g->);scanf("%s",cloNumnum-1.reason);print

40、f("n關(guān)閉景點(diǎn)成功！n);system("pause");break;case 2:printf("n請(qǐng)輸入你要恢復(fù)景點(diǎn)的編號(hào)：");scanf("%d",&num);if(num<0|num>12) printf("ntttt對(duì)不起，沒(méi)有該編號(hào)對(duì)應(yīng)的景點(diǎn)n");elsecloNumnum-1.close=0;printf("nt%s景點(diǎn)恢復(fù)成功！n",g->);system("pause");break;ca

41、se 3:printf("n請(qǐng)輸入公告內(nèi)容：");scanf("%s",Affiche);printf("ntttt公告發(fā)布成功！n");system("pause");break;case 4:if(fp = fopen("liuyan.txt","r") = NULL)printf("ntttt目前暫無(wú)游客留言");exit (1) ; printf("n以下是游客留言：n");while(fgets(buf,1024,fp) !=

42、 NULL) /*gets讀取一行*/len = strlen(buf);buflen-1 = '0' /*去掉換行符*/printf("t%sn",buf,len - 1);printf("n"); system("pause"); break;default:printf("n");/*游客菜單*/void Tour_Menu(mgraphType *g)int s=1,i=1;char ly250; FILE *fp; /*臨時(shí)存放用戶輸入的留言*/while(s>0&&

43、s<3)system("cls");Dis_Map();printf("n n");printf("t 1.查看公告 2.我要留言 n");printf("t n");printf("nt請(qǐng)選擇你的操作(其余按鍵返回主菜單)：");scanf("%d",&s);switch(s)case 1:if(!strcmp(Affiche,"NULL")printf("nttttt目前暫時(shí)無(wú)任何公告n");system("

44、pause");else printf("nn公告內(nèi)容如下：nnt%snn",Affiche);system("pause");break;case 2:fp=fopen("liuyan.txt","a"); /*以追加的方式添加文本*/while(i)printf("n請(qǐng)輸入你的留言：");scanf("%s",ly);time_t t; /*得到從標(biāo)準(zhǔn)計(jì)時(shí)點(diǎn)到當(dāng)前時(shí)間的秒數(shù)*/struct tm *p;t=time(NULL);p=localtime(&

45、t); /*時(shí)間轉(zhuǎn)換后賦給p*/fprintf(fp,"留言時(shí)間：%s留言內(nèi)容：%sn",asctime(p),ly);printf("n留言時(shí)間：%sn留言內(nèi)容：%s",asctime(p),ly);printf("nn是否要繼續(xù)留言(是：1 否：0)：");scanf("%d",&i);fclose(fp);break;default:printf("nttttt 返回主菜單！n");7源碼文件Ps：從7開(kāi)始以下內(nèi)容均不用在說(shuō)明書(shū)中寫(xiě)明，這里僅僅做補(bǔ)充作用，給大家一個(gè)參考。7.1 源

46、碼源碼說(shuō)明：因代碼過(guò)多，不得已將字體與行距和縮小，全程格式無(wú)更改，拷貝可用。編譯環(huán)境：vs201x#include <stdio.h>#include <stdlib.h>#include <time.h>#include <windows.h>#define INFINITY 9999 /*此處用9999代表無(wú)窮大*/#define M 20 /*最大頂點(diǎn)數(shù)*/typedef struct /*景點(diǎn)信息結(jié)構(gòu)定義*/int num; /*景點(diǎn)代號(hào)*/char name20; /*景點(diǎn)名稱*/char intro200; /*景點(diǎn)簡(jiǎn)介*/verte

47、xType; /*鄰接矩陣頂點(diǎn)結(jié)構(gòu)*/typedef int edgeType; /*權(quán)值類型*/typedef struct /*校園景點(diǎn)圖結(jié)構(gòu)體定義*/vertexType vexsM; /*頂點(diǎn)值類型*/edgeType edgsMM; /*邊權(quán)值類型-距離*/ int vexNum, edgNum; /*圖頂點(diǎn)總數(shù)與邊數(shù)*/mgraphType; /*函數(shù)一覽表*/void main(); /*主函數(shù)*/ int menu(); /*主菜單*/void Creat_Map(mgraphType *g); /*從文件讀取信息建立圖*/void Dis_Map(); /*顯示校園景點(diǎn)地圖*

48、/void Admin_Menu(mgraphType *g); /*管理員菜單*/void Tour_Menu(mgraphType *g); /*游客菜單*/ int judeg_Innum(int num); /*判斷用戶輸入的編號(hào)是否合理及對(duì)應(yīng)景點(diǎn)是否開(kāi)放*/void Search_Intro(mgraphType *g); /*景點(diǎn)信息查詢*/void ShortestPath_FLD(mgraphType *g); /*弗洛伊德算法求任意景點(diǎn)間最短的路徑*/void Floyd_Print(mgraphType,int,int); /*遞歸實(shí)現(xiàn)打印兩點(diǎn)間的最短路徑*/void Sh

49、ortestPath_Print(mgraphType); /*輸出并打印兩點(diǎn)間的最短路徑*/void Dfs_Allpath(mgraphType,int,int); /*深度優(yōu)先遍歷查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的所有路徑*/void Allpath_Print(mgraphType *g); /*查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的所有路徑并打印*/void Bestpath_Multispot(mgraphType); /*多景點(diǎn)間求最佳路徑*/void Dfs_Coila(mgraphType *g, int i); /*深度遍歷找關(guān)節(jié)點(diǎn)*/void Coila_Query(mgraphType *g); /*求校園交通圖關(guān)節(jié)點(diǎn)*/void System_Exit(int *quit); /*退出系統(tǒng)函數(shù)*/*校園景點(diǎn)圖的讀取與創(chuàng)建*/void Creat_M