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

1、.算法設(shè)計(jì)與分析課程設(shè)計(jì)題目： 校園導(dǎo)航問(wèn)題 文檔： 物聯(lián)網(wǎng)工程 學(xué)院 物聯(lián)網(wǎng)工程 專(zhuān)業(yè)學(xué) 號(hào) 學(xué)生姓名 班 級(jí) 物聯(lián)網(wǎng)1101 二一三年十二月設(shè)計(jì)要求：設(shè)計(jì)你的學(xué)校的平面圖，至少包括10個(gè)以上的場(chǎng)所，每?jī)蓚€(gè)場(chǎng)所間可以有不同的路，且路長(zhǎng)也可能不同，找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路（最短路徑）。本系統(tǒng)為用戶(hù)提供以下功能: (一)、查詢(xún)了解學(xué)校概況，為導(dǎo)游參觀者提供關(guān)于學(xué)校的相關(guān)信息。(二)、查詢(xún)校園各個(gè)場(chǎng)所和景點(diǎn)信息; (三)、為導(dǎo)游者或外來(lái)人員參觀人員提供校園交通信息，方便用戶(hù)走訪學(xué)校。完成需要操作時(shí)，退出系統(tǒng) 校園導(dǎo)航查詢(xún)系統(tǒng)的開(kāi)發(fā)方法總結(jié)如下： (1) 需求分析，了解學(xué)校各個(gè)場(chǎng)所與場(chǎng)所或

2、者是各個(gè)景點(diǎn)與景點(diǎn)之間的信息，路徑和距離，考慮該如何設(shè)計(jì)才能滿(mǎn)足用戶(hù)需求。(2) 概要設(shè)計(jì)，對(duì)調(diào)查得到的數(shù)據(jù)進(jìn)行分析，根據(jù)其要求實(shí)現(xiàn)的功能分析系統(tǒng)結(jié)構(gòu)和界面將實(shí)現(xiàn)的基本功能。(3) 詳細(xì)設(shè)計(jì)，設(shè)計(jì)系統(tǒng)界面并編輯實(shí)現(xiàn)其各個(gè)功能的代碼。(4) 調(diào)試分析，在設(shè)計(jì)完成后，調(diào)試系統(tǒng)運(yùn)行的狀況，修改完善系統(tǒng),然后進(jìn)行測(cè)試。一、需求分析1學(xué)校以及各景點(diǎn)介紹模塊采用一維數(shù)組將學(xué)校景點(diǎn)依次排放好編號(hào)G.vexi.number=i 在選擇校園介紹的時(shí)候，彈出G.vex0校園簡(jiǎn)介。在選擇各景點(diǎn)信息的時(shí)候，可按編號(hào)查詢(xún)2查詢(xún)最短路徑（主要）查出出發(fā)地到想要到達(dá)的景點(diǎn)的最短路徑，初步構(gòu)想采用最經(jīng)典的迪杰斯特拉算法最短路

3、徑函數(shù)3查詢(xún)各點(diǎn)距離將所有景點(diǎn)的距離顯示出來(lái)。4主菜單頁(yè)面顯示提供使用者選擇功能界面，按照提示進(jìn)行操作。5退出完成需要操作時(shí)，退出系統(tǒng)校園導(dǎo)航系統(tǒng) 最短路徑查詢(xún)查詢(xún)各景點(diǎn)距離查詢(xún)校園所有景點(diǎn)路徑校園介紹，各景點(diǎn)介紹輸入起點(diǎn)與終點(diǎn)輸出最短路徑校園導(dǎo)航系統(tǒng)模式圖2、 概要設(shè)計(jì)2.1算法設(shè)計(jì)說(shuō)明 校園導(dǎo)航模型是由各個(gè)景點(diǎn)和景點(diǎn)以及場(chǎng)所和場(chǎng)所之間的路徑組成的，所以這完全可以用數(shù)據(jù)結(jié)構(gòu)中的圖來(lái)模擬。用圖的結(jié)點(diǎn)代表景點(diǎn)或場(chǎng)所，用圖的邊代表景點(diǎn)或場(chǎng)所之間的路徑。所以首先應(yīng)創(chuàng)建圖的存儲(chǔ)結(jié)構(gòu)。結(jié)點(diǎn)值代表景點(diǎn)信息，邊的權(quán)值代表景點(diǎn)間的距離。結(jié)點(diǎn)值及邊的權(quán)值采用圖存儲(chǔ)。本系統(tǒng)需要查詢(xún)景點(diǎn)信息和求一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)

4、的最短路徑長(zhǎng)度及路線(xiàn)，為方便操作，所以給每個(gè)景點(diǎn)一個(gè)代碼，用結(jié)構(gòu)體類(lèi)型實(shí)現(xiàn)。計(jì)算路徑長(zhǎng)度，最短路線(xiàn)和最佳路徑時(shí)可分別用迪杰斯特拉（Dijkastra）算法和哈密而頓回路算法實(shí)現(xiàn)。最后switch選擇語(yǔ)句選擇執(zhí)行瀏覽景點(diǎn)信息或查詢(xún)最短路徑和距離。 2.1.1學(xué)校以及各景點(diǎn)介紹模塊 采用了圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)，首先初始化每一個(gè)景點(diǎn)名稱(chēng)（一維數(shù)組）for(i=1;i<G.vexnum;+i) G.vexi.number=i SearchMenu子菜單輸入景點(diǎn)編號(hào)編號(hào)值=iI<num輸出景點(diǎn)介紹 輸出“錯(cuò)誤”結(jié)束景點(diǎn)介紹功能流程圖2.1.2查詢(xún)最短路徑（主要） 算法的主要思想是按路徑長(zhǎng)度遞

5、增的次序產(chǎn)生最短路徑的算法。中心思想是假設(shè)s為已求得最短路徑的終點(diǎn)的集合，則下一條最短路徑或者是?。╲,x）或者是中間經(jīng)過(guò)s中是頂點(diǎn)而最后到達(dá)頂點(diǎn)x的路徑。（1） arcs表示弧上的權(quán)值。若不存在，則置arcs為。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)vi可能達(dá)到的最短路徑長(zhǎng)度的初值為D=arcsLocate Vex(G,v),i viV（2） 選擇vj，使得Dj=MinD | viV-S (3修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度路徑查詢(xún)流程圖 2.1.3查詢(xún)各點(diǎn)距離由于圖的結(jié)構(gòu)比較復(fù)雜，任意兩個(gè)點(diǎn)之間都可能存在聯(lián)系。因此無(wú)

6、法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系，但是卻可以借助數(shù)組的數(shù)據(jù)類(lèi)型表示元素之間的關(guān)系。2.1.4主函數(shù)循環(huán)體用開(kāi)關(guān)語(yǔ)句，該語(yǔ)句的條件值ck是當(dāng)用戶(hù)選擇菜單通過(guò)調(diào)用主菜單函數(shù)得到，返回值整數(shù)作開(kāi)關(guān)語(yǔ)句的條件。根據(jù)該值調(diào)用相應(yīng)的各功能函數(shù)，同時(shí)設(shè)置一個(gè)退出程序點(diǎn)，執(zhí)行完用戶(hù)的某項(xiàng)功能后繼續(xù)顯示菜單，當(dāng)返回值為e時(shí)函數(shù)結(jié)束程序，以免造成死循環(huán)。2.2數(shù)據(jù)結(jié)構(gòu)與函數(shù)考慮2.2.1數(shù)據(jù)結(jié)構(gòu)定義結(jié)構(gòu)體類(lèi)型，將多個(gè)相關(guān)的變量包裝成為一個(gè)整體使用。#define Max 32767 #define NUM 20 自定義頂點(diǎn)的類(lèi)型typedef struct VertexType int num

7、ber; / 景點(diǎn)編號(hào)char *sight;/ 景點(diǎn)名稱(chēng)VertexType;自定義圖的類(lèi)型typedef structVertexType vexNUM; / 圖中的頂點(diǎn)，即為景點(diǎn)int arcsNUMNUM; / 圖中的邊，即為景點(diǎn)間的距離int vexnum; / 頂點(diǎn)數(shù)MGraph;把圖定義為全局變量MGraph G;int PNUMNUM; 輔助變量存儲(chǔ)最短路徑長(zhǎng)度long int DNUM;2.2.2 使用的系統(tǒng)頭文件#include "stdio.h" /*I/O 函數(shù)*/ #include "stdlib.h" /*使用system（）

8、exit（）atoi（）malloc（）free（）函*/ #include "string.h" /*字符串函數(shù)，strcpy（）strlen（）strcmp（）*/ 三、主程序 #include <stdio.h> #include <string.h> #include <stdlib.h> #define Max 32767 #define NUM 20 typedef struct VertexType int number; char *sight; VertexType; typedef struct VertexType

9、vexNUM; int arcsNUMNUM; int vexnum; MGraph; MGraph G; int PNUMNUM; long int DNUM; void CreateMGraph(int v)/創(chuàng)建圖的函數(shù),v是函數(shù)入口 int i,j; G.vexnum=v; for(i=1;i<G.vexnum;+i) G.vexi.number=i; G.vex0.sight="各個(gè)地點(diǎn)名字" G.vex1.sight="江南大學(xué)校北門(mén)" G.vex2.sight="第一食堂" G.vex3.sight="江

10、南大學(xué)東偏門(mén)" G.vex4.sight="設(shè)計(jì)學(xué)院" G.vex5.sight="體育中心" G.vex6.sight="物聯(lián)網(wǎng)工程學(xué)院" G.vex7.sight="圖書(shū)館" G.vex8.sight="江南大學(xué)東門(mén)" G.vex9.sight="國(guó)家重點(diǎn)實(shí)驗(yàn)室" G.vex10.sight="第二教學(xué)樓" G.vex11.sight="第四食堂" G.vex13.sight="臻善樓" G.vex12

11、.sight="江南大學(xué)南門(mén)" for(i=1;i<G.vexnum;+i) for(j=1;j<G.vexnum;+j) G.arcsij=Max; G.arcs12=G.arcs21=200; G.arcs13=G.arcs31=210; G.arcs15=G.arcs51=521; G.arcs24=G.arcs42=299; G.arcs25=G.arcs52=450; G.arcs23=G.arcs32=869; G.arcs35=G.arcs53=620; G.arcs38=G.arcs83=756; G.arcs45=G.arcs54=355; G

12、.arcs46=G.arcs64=221; G.arcs57=G.arcs75=225; G.arcs58=G.arcs85=900; G.arcs67=G.arcs76=280; G.arcs69=G.arcs96=241; G.arcs78=G.arcs87=440; G.arcs710=G.arcs107=350; G.arcs810=G.arcs108=570; G.arcs910=G.arcs109=1300; G.arcs911=G.arcs119=998; G.arcs912=G.arcs129=1200; G.arcs1011=G.arcs1110=639; G.arcs101

13、2=G.arcs1210=805; G.arcs1112=G.arcs1211=283; G.arcs1213=G.arcs1312=296; void Map()/地圖展示函數(shù) printf("t *江南大學(xué)大學(xué)地圖導(dǎo)航系統(tǒng)* n"); printf(" 1 江南大學(xué)北大門(mén) n"); printf(" n"); printf(" n"); printf(" 2第一食堂 3江南大學(xué)東偏門(mén) n"); printf(" n"); printf(" n"); p

14、rintf(" 4設(shè)計(jì)學(xué)院5體育中心 n"); printf(" n"); printf(" n"); printf(" n"); printf(" 6物聯(lián)網(wǎng)工程學(xué)院7圖書(shū)館 8江南大學(xué)東門(mén) n"); printf(" n"); printf(" n"); printf(" n"); printf(" 9國(guó)家重點(diǎn)實(shí)驗(yàn)室 10第二教學(xué)樓 n"); printf(" n"); printf("

15、; n"); printf(" n"); printf(" n"); printf(" 11第四食堂 n"); printf(" n"); printf(" 13臻善樓12江南大學(xué)南門(mén) n"); void Info()/資料介紹函數(shù) printf("1 江南大學(xué)校北大門(mén) ：這是江南大學(xué)最有名的大門(mén)，是一座充滿(mǎn)歷史感的高大的牌坊，正上面寫(xiě)著“江南大學(xué)”四個(gè)大字，背面寫(xiě)著“江南第一學(xué)府”六個(gè)字n"); printf("2 江南大學(xué)第一食堂n"); p

16、rintf("3 江南大學(xué)東偏門(mén)： n"); printf("4 設(shè)計(jì)學(xué)院：n"); printf("5 體育中心：n"); printf("6 物聯(lián)網(wǎng)工程學(xué)院：n"); printf("7 圖書(shū)館：高達(dá)15層的雄偉的圖書(shū)館 n"); printf("8 江南大學(xué)東門(mén)： n"); printf("9 國(guó)家重點(diǎn)實(shí)驗(yàn)室： n"); printf("10 第二教學(xué)樓： n"); printf("11 第四食堂: n");

17、printf("13 臻善樓: n"); printf("12 江南大學(xué)南門(mén): n");void ShortestPath(int num) / 迪杰斯特拉算法最短路徑函數(shù)num為入口點(diǎn)的編號(hào) int v,w,i,t; / i、w和v為計(jì)數(shù)變量int finalNUM; int min; for(v=1;v<NUM;v+)finalv=0; / 假設(shè)從頂點(diǎn)num到頂點(diǎn)v沒(méi)有最短路徑Dv=G.arcsnumv;/ 將與之相關(guān)的權(quán)值放入D中存放for(w=1;w<NUM;w+) / 設(shè)置為空路徑Pvw=0;if(Dv<32767) /存在路

18、徑Pvnum=1; /存在標(biāo)志置為一 Pvv=1; /自身到自身Dnum=0; finalnum=1; /初始化num頂點(diǎn)屬于S集合/ 開(kāi)始主循環(huán)，每一次求得num到某個(gè)頂點(diǎn)的最短路徑，并將其加入到S集合for(i=1;i<NUM;+i) /其余G.vexnum-1個(gè)頂點(diǎn)min=Max; / 當(dāng)前所知離頂點(diǎn)num的最近距離for(w=1;w<NUM;+w) if(!finalw) / w頂點(diǎn)在v-s中if(Dw<min) / w頂點(diǎn)離num頂點(diǎn)更近v=w;min=Dw; / 更新當(dāng)前最短路徑極其距離finalv=1; / 離num頂點(diǎn)更近的v加入到s集合for(w=1;w&l

19、t;NUM;+w) if(!finalw&&(min+G.arcsvw)<Dw) / 不在s集合，并且比以前所找到的路徑都短就更新當(dāng)前路徑Dw=min+G.arcsvw; for(t=0;t<NUM;t+)Pwt=Pvt;Pww=1; char Menu()/應(yīng)用主界面顯示函數(shù)char c;int flag;dosystem("cls");flag=1;Map();printf("tt歡迎使用江南大學(xué)導(dǎo)航圖系統(tǒng)n");printf("tt 1.查詢(xún)地點(diǎn)之間最短路徑 n");printf("tt 2

20、.江南大學(xué)景點(diǎn)介紹n");printf("tt e.退出 n");printf("ttt請(qǐng)輸入您的選擇：");scanf("%c",&c);if(c='1'|c='2'|c='e')/如果輸入為1,2,E中的一個(gè)，則返回Cflag=0;while(flag);return c;void Display(int sight1,int sight2)/最短距離顯示函數(shù) int a,b,c,d,q=0; a=sight2;if(a!=sight1)printf("n

21、t從%s到%s的最短路徑是",G.vexsight1.sight,G.vexsight2.sight);printf("t(最短距離為 %d.m)nnt",Da);printf("t%s",G.vexsight1.sight);d=sight1;for(c=0;c<NUM;+c)Pasight1=0;for(b=0;b<NUM;b+)if(G.arcsdb<Max&&Pab)printf("->%s",G.vexb.sight);q=q+1;Pab=0;d=b;if(q%8=0) printf("n");void main()/主界面最短路線(xiàn)查詢(xún)顯示函數(shù)int v0,v1;char e;char ck;CreateMGraph(NUM);dosystem("cls");ck=Menu();switch(ck)case '1': gate:system("cls");Map();doprintf(&quo