校園導(dǎo)航系統(tǒng)---算法與分析課程設(shè)計

1、<p>　　算法設(shè)計與分析課程設(shè)計</p><p>　　題目： 校園導(dǎo)航問題 </p><p>　　文檔： </p><p>　　物聯(lián)網(wǎng)工程 學(xué)院 物聯(lián)網(wǎng)工程 專業(yè)</p><p>　　學(xué) 號

2、 </p><p>　　學(xué)生姓名 </p><p>　　班 級 物聯(lián)網(wǎng)1101 </p><p><b>　　二〇一三年十二月</b></p><p>　　設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，

3、且路長也可能不同，找出從任意場所到達(dá)另一場所的最佳路（最短路徑）。</p><p>　　本系統(tǒng)為用戶提供以下功能: </p><p>　　(一)、查詢了解學(xué)校概況，為導(dǎo)游參觀者提供關(guān)于學(xué)校的相關(guān)信息。</p><p>　　(二)、查詢校園各個場所和景點(diǎn)信息; </p><p>　　(三)、為導(dǎo)游者或外來人員參觀人員提供校園交通信息，方便用戶走

4、訪學(xué)校。完成需要操作時，退出系統(tǒng)</p><p>　　校園導(dǎo)航查詢系統(tǒng)的開發(fā)方法總結(jié)如下：</p><p>　　(1) 需求分析，了解學(xué)校各個場所與場所或者是各個景點(diǎn)與景點(diǎn)之間的信息，路徑和距離，考慮該如何設(shè)計才能滿足用戶需求。</p><p>　　(2) 概要設(shè)計，對調(diào)查得到的數(shù)據(jù)進(jìn)行分析，根據(jù)其要求實(shí)現(xiàn)的功能分析系統(tǒng)結(jié)構(gòu)和界面將實(shí)現(xiàn)的基本功能。</p>

5、;<p>　　(3) 詳細(xì)設(shè)計，設(shè)計系統(tǒng)界面并編輯實(shí)現(xiàn)其各個功能的代碼。</p><p>　　(4) 調(diào)試分析，在設(shè)計完成后，調(diào)試系統(tǒng)運(yùn)行的狀況，修改完善系統(tǒng),然后進(jìn)行測試。</p><p><b>　　一、需求分析</b></p><p>　　1學(xué)校以及各景點(diǎn)介紹模塊</p><p>　　采用一維數(shù)組將學(xué)

6、校景點(diǎn)依次排放好編號G.vex[i].number=i 在選擇校園介紹的時候，彈出G.vex[0]校園簡介。在選擇各景點(diǎn)信息的時候，可按編號查詢</p><p>　　2查詢最短路徑（主要）</p><p>　　查出出發(fā)地到想要到達(dá)的景點(diǎn)的最短路徑，初步構(gòu)想采用最經(jīng)典的迪杰斯特拉算法最短路徑函數(shù)</p><p><b>　　3查詢各點(diǎn)距離</b>

7、</p><p>　　將所有景點(diǎn)的距離顯示出來。</p><p><b>　　4主菜單頁面顯示</b></p><p>　　提供使用者選擇功能界面，按照提示進(jìn)行操作。</p><p><b>　　5退出</b></p><p>　　完成需要操作時，退出系統(tǒng)</p>

8、<p><b>　　校園導(dǎo)航系統(tǒng)模式圖</b></p><p><b>　　概要設(shè)計</b></p><p><b>　　2.1算法設(shè)計說明</b></p><p>　　校園導(dǎo)航模型是由各個景點(diǎn)和景點(diǎn)以及場所和場所之間的路徑組成的，所以這完全可以用數(shù)據(jù)結(jié)構(gòu)中的圖來模擬。用圖的結(jié)點(diǎn)代表景點(diǎn)

9、或場所，用圖的邊代表景點(diǎn)或場所之間的路徑。所以首先應(yīng)創(chuàng)建圖的存儲結(jié)構(gòu)。結(jié)點(diǎn)值代表景點(diǎn)信息，邊的權(quán)值代表景點(diǎn)間的距離。結(jié)點(diǎn)值及邊的權(quán)值采用圖存儲。本系統(tǒng)需要查詢景點(diǎn)信息和求一個景點(diǎn)到另一個景點(diǎn)的最短路徑長度及路線，為方便操作，所以給每個景點(diǎn)一個代碼，用結(jié)構(gòu)體類型實(shí)現(xiàn)。計算路徑長度，最短路線和最佳路徑時可分別用迪杰斯特拉（Dijkastra）算法和哈密而頓回路算法實(shí)現(xiàn)。最后switch</p><p>　　選擇語句選

10、擇執(zhí)行瀏覽景點(diǎn)信息或查詢最短路徑和距離。</p><p>　　2.1.1學(xué)校以及各景點(diǎn)介紹模塊</p><p>　　采用了圖的鄰接矩陣存儲結(jié)構(gòu)，首先初始化每一個景點(diǎn)名稱（一維數(shù)組）for(i=1;i<G.vexnum;++i) G.vex[i].number=i ……</p><p><b>　　景點(diǎn)介紹功能流程圖</b></p&g

11、t;<p>　　2.1.2查詢最短路徑（主要）</p><p>　　算法的主要思想是按路徑長度遞增的次序產(chǎn)生最短路徑的算法。中心思想是假設(shè)s為已求得最短路徑的終點(diǎn)的集合，則下一條最短路徑或者是?。╲,x）或者是中間經(jīng)過s中是頂點(diǎn)而最后到達(dá)頂點(diǎn)x的路徑。</p><p>　　arcs表示弧上的權(quán)值。若不存在，則置arcs為∞。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，初始狀態(tài)為

12、空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)vi可能達(dá)到的最短路徑長度的初值為D=arcs[Locate Vex(G,v),i] vi∈V</p><p>　　選擇vj，使得D[j]=Min{D | vi∈V-S} </p><p>　　(3修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長度</p><p><b>　　路徑查詢流程圖</b>&l

13、t;/p><p>　　2.1.3查詢各點(diǎn)距離</p><p>　　由于圖的結(jié)構(gòu)比較復(fù)雜，任意兩個點(diǎn)之間都可能存在聯(lián)系。因此無法以數(shù)據(jù)</p><p>　　元素在存儲區(qū)中的物理位置來表示元素之間的關(guān)系，但是卻可以借助數(shù)組的數(shù)據(jù)</p><p>　　類型表示元素之間的關(guān)系。</p><p><b>　　2.1.4主函

14、數(shù)</b></p><p>　　循環(huán)體用開關(guān)語句，該語句的條件值ck是當(dāng)用戶選擇菜單通過調(diào)用主菜單函數(shù)得到，返回值整數(shù)作開關(guān)語句的條件。根據(jù)該值調(diào)用相應(yīng)的各功能函數(shù)，同時設(shè)置一個退出程序點(diǎn)，執(zhí)行完用戶的某項(xiàng)功能后繼續(xù)顯示菜單，當(dāng)返回值為e</p><p>　　時函數(shù)結(jié)束程序，以免造成死循環(huán)。</p><p>　　2.2數(shù)據(jù)結(jié)構(gòu)與函數(shù)考慮</p>

15、;<p><b>　　2.2.1數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　定義結(jié)構(gòu)體類型，將多個相關(guān)的變量包裝成為一個整體使用。</p><p>　　#define Max 32767 </p><p>　　#define NUM 20 </p><p><b>　　自定義頂點(diǎn)的類型</b>

16、;</p><p>　　typedef struct VertexType{ </p><p>　　int number; // 景點(diǎn)編號</p><p>　　char *sight;// 景點(diǎn)名稱</p><p>　　}VertexType;</p><p><b>　　自定義圖的類型</b>&

17、lt;/p><p>　　typedef struct{</p><p>　　VertexType vex[NUM]; // 圖中的頂點(diǎn)，即為景點(diǎn)</p><p>　　int arcs[NUM][NUM]; // 圖中的邊，即為景點(diǎn)間的距離</p><p>　　int vexnum; // 頂點(diǎn)數(shù)</p><p><b

18、>　　}MGraph;</b></p><p><b>　　把圖定義為全局變量</b></p><p><b>　　MGraph G;</b></p><p>　　int P[NUM][NUM]; 輔助變量存儲最短路徑長度</p><p>　　long int D[NUM];<

19、;/p><p><b>　　2.2.2 </b></p><p><b>　　使用的系統(tǒng)頭文件</b></p><p>　　#include "stdio.h" /*I/O 函數(shù)*/ </p><p>　　#include "stdlib.h" /*使用syste

20、m（）exit（）atoi（）malloc（）free（）函*/ </p><p>　　#include "string.h" /*字符串函數(shù)，strcpy（）strlen（）strcmp（）*/ </p><p><b>　　三、主程序</b></p><p>　　#include <stdio.h></

21、p><p>　　#include <string.h></p><p>　　#include <stdlib.h></p><p>　　#define Max 32767</p><p>　　#define NUM 20 </p><p>　　typedef struct VertexType

22、{ </p><p>　　int number; </p><p>　　char *sight; </p><p>　　}VertexType; </p><p>　　typedef struct{ </p><p>　　VertexType vex[NUM]; </p><p>　　int a

23、rcs[NUM][NUM]; </p><p>　　int vexnum; </p><p>　　}MGraph; </p><p>　　MGraph G; </p><p>　　int P[NUM][NUM]; </p><p>　　long int D[NUM]; </p><p>

24、;　　void CreateMGraph(int v)//創(chuàng)建圖的函數(shù),v是函數(shù)入口</p><p><b>　　{ </b></p><p><b>　　int i,j; </b></p><p>　　G.vexnum=v; </p><p>　　for(i=1;i<G.vexnum;++i

25、) </p><p>　　G.vex[i].number=i; </p><p>　　G.vex[0].sight="各個地點(diǎn)名字";</p><p>　　G.vex[1].sight="江南大學(xué)校北門"; </p><p>　　G.vex[2].sight="第一食堂"; &l

26、t;/p><p>　　G.vex[3].sight="江南大學(xué)東偏門"; </p><p>　　G.vex[4].sight="設(shè)計學(xué)院"; </p><p>　　G.vex[5].sight="體育中心"; </p><p>　　G.vex[6].sight="物聯(lián)網(wǎng)工程學(xué)院

27、"; </p><p>　　G.vex[7].sight="圖書館";</p><p>　　G.vex[8].sight="江南大學(xué)東門"; </p><p>　　G.vex[9].sight="國家重點(diǎn)實(shí)驗(yàn)室";</p><p>　　G.vex[10].sight=&qu

28、ot;第二教學(xué)樓"; </p><p>　　G.vex[11].sight="第四食堂"; </p><p>　　G.vex[13].sight="臻善樓"; </p><p>　　G.vex[12].sight="江南大學(xué)南門"; </p><p>　　for(i=1;i

29、<G.vexnum;++i) </p><p><b>　　{ </b></p><p>　　for(j=1;j<G.vexnum;++j) </p><p>　　G.arcs[i][j]=Max; </p><p><b>　　} </b></p><p&

30、gt;　　G.arcs[1][2]=G.arcs[2][1]=200; </p><p>　　G.arcs[1][3]=G.arcs[3][1]=210; </p><p>　　G.arcs[1][5]=G.arcs[5][1]=521;</p><p>　　G.arcs[2][4]=G.arcs[4][2]=299; </p><p>　　

31、G.arcs[2][5]=G.arcs[5][2]=450; </p><p>　　G.arcs[2][3]=G.arcs[3][2]=869; </p><p>　　G.arcs[3][5]=G.arcs[5][3]=620; </p><p>　　G.arcs[3][8]=G.arcs[8][3]=756; </p><p>　　G.ar

32、cs[4][5]=G.arcs[5][4]=355; </p><p>　　G.arcs[4][6]=G.arcs[6][4]=221; </p><p>　　G.arcs[5][7]=G.arcs[7][5]=225; </p><p>　　G.arcs[5][8]=G.arcs[8][5]=900; </p><p>　　G.arcs[6

33、][7]=G.arcs[7][6]=280; </p><p>　　G.arcs[6][9]=G.arcs[9][6]=241; </p><p>　　G.arcs[7][8]=G.arcs[8][7]=440; </p><p>　　G.arcs[7][10]=G.arcs[10][7]=350; </p><p>　　G.arcs[8][

34、10]=G.arcs[10][8]=570; </p><p>　　G.arcs[9][10]=G.arcs[10][9]=1300; </p><p>　　G.arcs[9][11]=G.arcs[11][9]=998; </p><p>　　G.arcs[9][12]=G.arcs[12][9]=1200; </p><p>　　G.ar

35、cs[10][11]=G.arcs[11][10]=639; </p><p>　　G.arcs[10][12]=G.arcs[12][10]=805; </p><p>　　G.arcs[11][12]=G.arcs[12][11]=283; </p><p>　　G.arcs[12][13]=G.arcs[13][12]=296; </p>&l

36、t;p><b>　　} </b></p><p>　　void Map()//地圖展示函數(shù)</p><p><b>　　{ </b></p><p>　　printf("\t ************************江南大學(xué)大學(xué)地圖導(dǎo)航系統(tǒng)*******************

37、 \n");</p><p>　　printf(" ━━━━━━━━━━━━━━━1 江南大學(xué)北大門━━━━━━━━━━ \n"); </p><p>　　printf(" ┃ ┃

38、 ┃ \n"); </p><p>　　printf(" ┃ ┃ ┃ \n"); </p><p>　　printf(" 2第一食堂 ━━━━━━━━━━━

39、━━━━━━━━━━━━━━ 3江南大學(xué)東偏門 \n"); </p><p>　　printf(" ┃ ┃ ┃ \n"); </p><p>　　printf(" ┃

40、 ┃ ┃ \n"); </p><p>　　printf(" 4設(shè)計學(xué)院━━━━━━━━━━━━5體育中心━━━━━━━━━━━━┃ \n");</p><p>　　printf(&

41、quot; ┃ ┃ ┃ \n");</p><p>　　printf(" ┃ ┃ ┃

42、 \n"); </p><p>　　printf(" ┃ ┃ ┃ \n"); </p><p>　　printf(" 6物聯(lián)網(wǎng)工程學(xué)院━━━━━━━━━7圖書館 ━━━━━━━━━ 8江南大

43、學(xué)東門 \n"); </p><p>　　printf(" ┃ ┃ ┃ \n"); </p><p>　　printf(" ┃

44、 ┃ ┃ \n"); </p><p>　　printf(" ┃ ┃ ┃ \n"); </p><p&g

45、t;　　printf(" 9國家重點(diǎn)實(shí)驗(yàn)室 10第二教學(xué)樓━━━━━━━━━━┃ \n"); </p><p>　　printf(" ┃ ┃ ┃ \n&quo

46、t;); </p><p>　　printf(" ┃ ┃ ┃ \n"); </p><p>　　printf(" ━━━━━━━━━━━━━━━━┃ ━━━━━━━━━━┃

47、 \n");</p><p>　　printf(" ┃ ┃ \n"); </p><p>　　printf("

48、 ┃━━━11第四食堂 \n"); </p><p>　　printf(" ┃ \n"); </p><p>　　

49、printf(" 13臻善樓━━━━━━━━━━━━━12江南大學(xué)南門 \n"); </p><p><b>　　} </b></p><p>　　void Info()//資料介紹函數(shù)</p><p><b>　　{ </b

50、></p><p>　　printf("1 江南大學(xué)校北大門 ：這是江南大學(xué)最有名的大門，是一座充滿歷史感的高大的牌坊，正上面寫著“江南大學(xué)”四個大字，背面寫著“江南第一學(xué)府”六個字\n");</p><p>　　printf("2 江南大學(xué)第一食堂\n");</p><p>　　printf("3

51、 江南大學(xué)東偏門： \n"); </p><p>　　printf("4 設(shè)計學(xué)院：\n"); </p><p>　　printf("5 體育中心：\n"); </p><p>　　printf("6 物聯(lián)網(wǎng)工程學(xué)院：\n"); </p><p>　　print

52、f("7 圖書館：高達(dá)15層的雄偉的圖書館 \n");</p><p>　　printf("8 江南大學(xué)東門： \n"); </p><p>　　printf("9 國家重點(diǎn)實(shí)驗(yàn)室： \n"); </p><p>　　printf("10 第二教學(xué)樓： \n")

53、; </p><p>　　printf("11 第四食堂: \n");</p><p>　　printf("13 臻善樓: \n");</p><p>　　printf("12 江南大學(xué)南門: \n");</p><p><b>　　}</b>

54、;</p><p>　　void ShortestPath(int num) // 迪杰斯特拉算法最短路徑函數(shù)num為入口點(diǎn)的編號</p><p><b>　　{ </b></p><p>　　int v,w,i,t; // i、w和v為計數(shù)變量</p><p>　　int final[NUM]; </p>

55、<p><b>　　int min; </b></p><p>　　for(v=1;v<NUM;v++)</p><p><b>　　{</b></p><p>　　final[v]=0; // 假設(shè)從頂點(diǎn)num到頂點(diǎn)v沒有最短路徑</p><p>　　D[v]=G.arcs[nu

56、m][v];// 將與之相關(guān)的權(quán)值放入D中存放</p><p>　　for(w=1;w<NUM;w++) // 設(shè)置為空路徑</p><p>　　P[v][w]=0;</p><p>　　if(D[v]<32767) //存在路徑</p><p><b>　　{</b></p><p>

57、;　　P[v][num]=1; //存在標(biāo)志置為一 </p><p>　　P[v][v]=1; //自身到自身</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　D[num]=0; </p><p>　　final[num]=

58、1; //初始化num頂點(diǎn)屬于S集合</p><p>　　// 開始主循環(huán)，每一次求得num到某個頂點(diǎn)的最短路徑，并將其加入到S集合</p><p>　　for(i=1;i<NUM;++i) //其余G.vexnum-1個頂點(diǎn)</p><p><b>　　{</b></p><p>　　min=Max; // 當(dāng)前

59、所知離頂點(diǎn)num的最近距離</p><p>　　for(w=1;w<NUM;++w) </p><p>　　if(!final[w]) // w頂點(diǎn)在v-s中</p><p>　　if(D[w]<min) // w頂點(diǎn)離num頂點(diǎn)更近</p><p><b>　　{</b></p><p&

60、gt;<b>　　v=w;</b></p><p><b>　　min=D[w];</b></p><p>　　} // 更新當(dāng)前最短路徑極其距離</p><p>　　final[v]=1; // 離num頂點(diǎn)更近的v加入到s集合</p><p>　　for(w=1;w<NUM;++w) &

61、lt;/p><p>　　if(!final[w]&&((min+G.arcs[v][w])<D[w])) // 不在s集合，并且比以前所找到的路徑都短就更新當(dāng)前路徑</p><p><b>　　{</b></p><p>　　D[w]=min+G.arcs[v][w]; </p><p>　　for(t

62、=0;t<NUM;t++)</p><p>　　P[w][t]=P[v][t];</p><p>　　P[w][w]=1;</p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　}</b>&l

63、t;/p><p>　　char Menu()//應(yīng)用主界面顯示函數(shù)</p><p><b>　　{</b></p><p><b>　　char c;</b></p><p><b>　　int flag;</b></p><p><b>　　do

64、{</b></p><p>　　system("cls");</p><p><b>　　flag=1;</b></p><p><b>　　Map();</b></p><p>　　printf("\t\t歡迎使用江南大學(xué)導(dǎo)航圖系統(tǒng)\n");&l

65、t;/p><p>　　printf("\t\t 1.查詢地點(diǎn)之間最短路徑 \n");</p><p>　　printf("\t\t 2.江南大學(xué)景點(diǎn)介紹\n");</p><p>　　printf("\t\t e.退出 \n");</p><p>　　printf("\t\t\

66、t請輸入您的選擇：");</p><p>　　scanf("%c",&c);</p><p>　　if(c=='1'||c=='2'||c=='e')//如果輸入為1,2,E中的一個，則返回C</p><p><b>　　flag=0;</b></p&g

67、t;<p><b>　　}</b></p><p>　　while(flag);</p><p><b>　　return c;</b></p><p><b>　　}</b></p><p>　　void Display(int sight1,int sight

68、2)//最短距離顯示函數(shù)</p><p><b>　　{ </b></p><p>　　int a,b,c,d,q=0; </p><p><b>　　a=sight2;</b></p><p>　　if(a!=sight1)</p><p><b>　　{<

69、/b></p><p>　　printf("\n\t從%s到%s的最短路徑是",G.vex[sight1].sight,G.vex[sight2].sight);</p><p>　　printf("\t(最短距離為 %d.m)\n\n\t",D[a]);</p><p>　　printf("\t%s"

70、;,G.vex[sight1].sight);</p><p><b>　　d=sight1;</b></p><p>　　for(c=0;c<NUM;++c)</p><p><b>　　{</b></p><p>　　P[a][sight1]=0;</p><p>

71、　　for(b=0;b<NUM;b++)</p><p><b>　　{</b></p><p>　　if(G.arcs[d][b]<Max&&P[a][b])</p><p><b>　　{</b></p><p>　　printf("-->%s&quo

72、t;,G.vex[b].sight);</p><p><b>　　q=q+1;</b></p><p>　　P[a][b]=0;</p><p><b>　　d=b;</b></p><p>　　if(q%8==0) printf("\n");</p><p

73、><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　

74、　void main()//主界面最短路線查詢顯示函數(shù)</p><p><b>　　{</b></p><p>　　int v0,v1;</p><p><b>　　char e;</b></p><p><b>　　char ck;</b></p><p&

75、gt;　　CreateMGraph(NUM);</p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　system("cls");</p><p>　　ck=Menu();</p><p>　　switch(

76、ck)</p><p><b>　　{</b></p><p>　　case '1': gate:</p><p>　　system("cls");</p><p><b>　　Map();</b></p><p><b>　　d

77、o</b></p><p><b>　　{</b></p><p>　　printf("\n\n\t\t\t請選擇出發(fā)地序號（1～13）：");</p><p>　　scanf("%d",&v0);</p><p>　　if(v0<1||v0>13)

78、</p><p>　　printf("\n\n\t\t\t\t輸入錯誤!\n");</p><p>　　}while(v0<1||v0>13);</p><p><b>　　do</b></p><p><b>　　{</b></p><p>

79、　　printf("\t\t\t請選擇目的地序號（1～13）：");</p><p>　　scanf("%d",&v1);</p><p>　　if(v1<1||v1>13||v1==v0)</p><p>　　printf("\n\n\t\t\t\t輸入錯誤!\n");</p&g

80、t;<p>　　}while(v1<1||v1>13||v1==v0);</p><p>　　ShortestPath(v0);</p><p>　　Display(v0,v1);</p><p>　　printf("\n\n\t\t\t\t按回車鍵繼續(xù),按e退回首頁\n");</p><p>　

81、　getchar();</p><p>　　scanf("%c",&e);</p><p>　　if(e=='e')</p><p><b>　　break;</b></p><p>　　goto gate;</p><p><b>　　cas

82、e'2':</b></p><p>　　system("cls");</p><p><b>　　Info();</b></p><p>　　printf("\n\n\t\t\t\t按回車鍵返回首頁...\n");</p><p>　　getchar()

83、;</p><p>　　getchar();</p><p><b>　　break;</b></p><p><b>　　};</b></p><p><b>　　}</b></p><p>　　while(ck!='e');</

84、p><p><b>　　}</b></p><p>　　四、程序調(diào)試及運(yùn)行結(jié)果貼圖</p><p><b>　　總結(jié)</b></p><p>　　通過這次設(shè)計，是我得以更好的掌握C語言的編程，對一些算法思想和實(shí)現(xiàn)方法有了更深的了解。在設(shè)計中，出現(xiàn)了一系列的問題，好多次都差點(diǎn)堅持不下去，但最終還是完成了！