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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：18 大小：304.00KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩17頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　算法設計與分析課程設計　　題目：校園導航問題 　　文檔： 　　物聯網工程學院物聯網工程專業(yè)　　學號

2、 　　學生姓名 　　班級物聯網1101 　　二〇一三年十二月　　設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，

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

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

5、;　　(3) 詳細設計，設計系統(tǒng)界面并編輯實現其各個功能的代碼。　　(4) 調試分析，在設計完成后，調試系統(tǒng)運行的狀況，修改完善系統(tǒng),然后進行測試。　　一、需求分析　　1學校以及各景點介紹模塊　　采用一維數組將學

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

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

8、　　校園導航系統(tǒng)模式圖　　概要設計　　2.1算法設計說明　　校園導航模型是由各個景點和景點以及場所和場所之間的路徑組成的，所以這完全可以用數據結構中的圖來模擬。用圖的結點代表景點

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

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

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

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

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

14、數　　循環(huán)體用開關語句，該語句的條件值ck是當用戶選擇菜單通過調用主菜單函數得到，返回值整數作開關語句的條件。根據該值調用相應的各功能函數，同時設置一個退出程序點，執(zhí)行完用戶的某項功能后繼續(xù)顯示菜單，當返回值為e　　時函數結束程序，以免造成死循環(huán)。　　2.2數據結構與函數考慮

15、;　　2.2.1數據結構　　定義結構體類型，將多個相關的變量包裝成為一個整體使用。　　#define Max 32767 　　#define NUM 20 　　自定義頂點的類型

16、;　　typedef struct VertexType{ 　　int number; // 景點編號　　char *sight;// 景點名稱　　}VertexType;　　自定義圖的類型&

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

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

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

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

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

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

23、rcs[NUM][NUM]; 　　int vexnum; 　　}MGraph; 　　MGraph G; 　　int P[NUM][NUM]; 　　long int D[NUM];

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

25、) 　　G.vex[i].number=i; 　　G.vex[0].sight="各個地點名字";　　G.vex[1].sight="江南大學校北門"; 　　G.vex[2].sight="第一食堂"; &l

26、t;/p>　　G.vex[3].sight="江南大學東偏門"; 　　G.vex[4].sight="設計學院"; 　　G.vex[5].sight="體育中心"; 　　G.vex[6].sight="物聯網工程學院

27、"; 　　G.vex[7].sight="圖書館";　　G.vex[8].sight="江南大學東門"; 　　G.vex[9].sight="國家重點實驗室";　　G.vex[10].sight=&qu

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

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

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

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

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

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

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

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

36、t;p>　　} 　　void Map()//地圖展示函數　　{ 　　printf("\t ************************江南大學大學地圖導航系統(tǒng)*******************

37、 \n");　　printf(" ━━━━━━━━━━━━━━━1 江南大學北大門━━━━━━━━━━ \n"); 　　printf(" ┃ ┃

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

39、━━━━━━━━━━━━━━ 3江南大學東偏門 \n"); 　　printf(" ┃ ┃ ┃ \n"); 　　printf(" ┃

40、 ┃ ┃ \n"); 　　printf(" 4設計學院━━━━━━━━━━━━5體育中心━━━━━━━━━━━━┃ \n");　　printf(&

41、quot; ┃ ┃ ┃ \n");　　printf(" ┃ ┃ ┃

42、 \n"); 　　printf(" ┃ ┃ ┃ \n"); 　　printf(" 6物聯網工程學院━━━━━━━━━7圖書館 ━━━━━━━━━ 8江南大

43、學東門 \n"); 　　printf(" ┃ ┃ ┃ \n"); 　　printf(" ┃

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

45、t;　　printf(" 9國家重點實驗室 10第二教學樓━━━━━━━━━━┃ \n"); 　　printf(" ┃ ┃ ┃ \n&quo

46、t;); 　　printf(" ┃ ┃ ┃ \n"); 　　printf(" ━━━━━━━━━━━━━━━━┃ ━━━━━━━━━━┃

47、 \n");　　printf(" ┃ ┃ \n"); 　　printf("

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

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

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

51、江南大學東偏門： \n"); 　　printf("4 設計學院：\n"); 　　printf("5 體育中心：\n"); 　　printf("6 物聯網工程學院：\n"); 　　print

52、f("7 圖書館：高達15層的雄偉的圖書館 \n");　　printf("8 江南大學東門： \n"); 　　printf("9 國家重點實驗室： \n"); 　　printf("10 第二教學樓： \n")

53、; 　　printf("11 第四食堂: \n");　　printf("13 臻善樓: \n");　　printf("12 江南大學南門: \n");　　}

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

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

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

57、;　　P[v][num]=1; //存在標志置為一 　　P[v][v]=1; //自身到自身　　}　　}　　D[num]=0; 　　final[num]=

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

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

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

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

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

63、t;/p>　　char Menu()//應用主界面顯示函數　　{　　char c;　　int flag;　　do

64、{　　system("cls");　　flag=1;　　Map();　　printf("\t\t歡迎使用江南大學導航圖系統(tǒng)\n");&l

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

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

67、t;　　}　　while(flag);　　return c;　　}　　void Display(int sight1,int sight

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

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

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

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

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

73、>　　}　　}　　}　　}　　}

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

75、gt;　　CreateMGraph(NUM);　　do　　{　　system("cls");　　ck=Menu();　　switch(

76、ck)　　{　　case '1': gate:　　system("cls");　　Map();　　d

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

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載