校園導(dǎo)航課程設(shè)計(jì)說明書

1、數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計(jì) 說 明 書學(xué)生姓名:學(xué) 號(hào)：學(xué) 院:軟件學(xué)院專 業(yè):信息管理與信息系統(tǒng)題 目:校園導(dǎo)航成績(jī)指導(dǎo)教師 一.設(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á)到以下目的：1)了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；2)初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；3)提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力； 4)訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范

2、進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。本系統(tǒng)為用戶提供以下功能:(一)、查詢了解學(xué)校概況，為導(dǎo)游參觀者提供關(guān)于學(xué)校的相關(guān)信息。(二)、查詢校園各個(gè)場(chǎng)所和景點(diǎn)信息;(三)、為導(dǎo)游者或外來人員參觀人員提供校園交通信息，方便用戶走訪學(xué)校。校園導(dǎo)航查詢系統(tǒng)的開發(fā)方法總結(jié)如下：(1) 調(diào)查，了解學(xué)校各個(gè)場(chǎng)所與 場(chǎng)所或者是各個(gè)景點(diǎn)與景點(diǎn)之間的信息，路徑和距離，從外來人員或者參觀者和走訪者的角度出發(fā)，該如何設(shè)計(jì)才能滿足用戶需求。(2) 分析，對(duì)調(diào)查得到的數(shù)據(jù)進(jìn)行分析，根據(jù)其要求實(shí)現(xiàn)的功能分析系統(tǒng)結(jié)構(gòu)和界面將實(shí)現(xiàn)的基本功能。(3) 設(shè)計(jì)與開發(fā)，設(shè)計(jì)系統(tǒng)界面并編輯實(shí)現(xiàn)其各個(gè)功能的代碼。(4

3、) 調(diào)試，在設(shè)計(jì)完成后，調(diào)試系統(tǒng)運(yùn)行的狀況，修改完善系統(tǒng),然后進(jìn)行測(cè)試。二.涉及內(nèi)容和要求 設(shè)計(jì)內(nèi)容：（1）設(shè)計(jì)學(xué)校的平面圖（至少包括10個(gè)以上的場(chǎng)所）。每?jī)蓚€(gè)場(chǎng)所間可以有不同的路，且路長(zhǎng)也可能不同；（2）提供起始點(diǎn)與終點(diǎn)能自動(dòng)找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路徑（最短路徑）。 設(shè)計(jì)要求：(1) 符合課題要求，實(shí)現(xiàn)相應(yīng)功能；(2) 要求界面友好美觀，操作方便易行；(3) 注意程序的實(shí)用性、安全性；三.本設(shè)計(jì)所采用的數(shù)據(jù)結(jié)構(gòu)校園旅游模型是由各個(gè)景點(diǎn)和景點(diǎn)以及場(chǎng)所和場(chǎng)所之間的路徑組成的，所以這完全可以用數(shù)據(jù)結(jié)構(gòu)中的圖來模擬。用圖的結(jié)點(diǎn)代表景點(diǎn)或場(chǎng)所，用圖的邊代表景點(diǎn)或場(chǎng)所之間的路徑。所以首先應(yīng)創(chuàng)建

4、圖的存儲(chǔ)結(jié)構(gòu)。結(jié)點(diǎn)值代表景點(diǎn)信息，邊的權(quán)值代表景點(diǎn)間的距離。結(jié)點(diǎn)值及邊的權(quán)值采用圖存儲(chǔ)。本系統(tǒng)需要查詢景點(diǎn)信息和求一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑長(zhǎng)度及路線，為方便操作，所以給每個(gè)景點(diǎn)一個(gè)代碼，用結(jié)構(gòu)體類型實(shí)現(xiàn)。計(jì)算路徑長(zhǎng)度，最短路線和最佳路徑時(shí)可用迪杰斯特拉（dijkastra）算法實(shí)現(xiàn)。最后用switch選擇語句選擇執(zhí)行瀏覽景點(diǎn)信息或查詢最短路徑和距離。1. 圖的存儲(chǔ)結(jié)構(gòu)常用的有4種，分別是數(shù)組表示法，鄰接表，十字鏈表，鄰接多重表。在此程序中運(yùn)用的是數(shù)組表示法：網(wǎng)的鄰接矩陣：aij= wi,j 若或(vi,vj)vr 反之 #define infinity int_max /最大值無窮大#d

5、efine max_vertex_num 20 /最大頂點(diǎn)個(gè)數(shù)typedef enumdg,dn,ag,an graphkind; /有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef struct arccell vrtype adj; infotype *info; /該弧相關(guān)信息的指針arccell,adjmatrixmax_vertex_nummax_vertex_num;tpyedef struct vertextype vexsmax_vertex_num; /頂點(diǎn)向量 adjmatrix arcs; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) graphk

6、ind kind; /圖的種類標(biāo)志mgraph;創(chuàng)建一個(gè)二維數(shù)組用來存儲(chǔ)兩個(gè)地點(diǎn)的距離，數(shù)組兩個(gè)下標(biāo)分別代表兩個(gè)地點(diǎn)的位置（起點(diǎn)與終點(diǎn)），若兩個(gè)地點(diǎn)之間沒有路線可走則用無窮大表示兩點(diǎn)之間沒有路，依據(jù)此條件完成初始化平面矩陣。例子：edge00.value=0 , edge01.value=25 , edge02.value=25 ; edge03.value=90, edge04.value=uplimit, edge05.value=uplimit ; edge06.value=10 , edge07.value=uplimit , edge08.value=uplimit; edge09.

7、value=uplimit, edge010.value=uplimit;2.迪杰斯特拉(dijkstra)算法思想:按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑.算法的一級(jí)實(shí)現(xiàn)：輔助數(shù)組d0.n-1di: 表示當(dāng)前所找到的從始點(diǎn)v到終點(diǎn)vi的最短路徑的長(zhǎng)度.算法的二級(jí)實(shí)現(xiàn): (用鄰接矩陣arcs來存儲(chǔ)有向圖)(1) s:表示已找到從v出發(fā)的最短路徑的終點(diǎn)的集合; di:表示當(dāng)前所找到的從v到終點(diǎn)vi的最短路徑的長(zhǎng)度. s=v; di=arcslocate-vex(g,v)i viv(2)選擇vj, 使得 dj=mindi| viv-s 令 s=sj(3)修改從v出發(fā)到集合v-s上任頂點(diǎn)vk可達(dá)的最短路徑

8、長(zhǎng)度. if dj+arcsj,kdk dk=dj+arcsjk(4)重復(fù)(2)、(3)共n-1次; 即可求得從v到圖上其余各頂點(diǎn)的最短路徑.以下為迪杰斯特拉算法void shortestdist(int s) for ( int i=0;i11;i+) /dist和path數(shù)組初始化 disti.value=edgesi.value; /鄰接矩陣第s行元素賦值到dist中 si.value=0; /已求出最短路徑的頂點(diǎn)集合初始化 if(i!=s & disti.valueuplimit) pathi.value=s; else pathi.value=-1; /路徑存放數(shù)組初始化 ss.va

9、lue=1; /頂點(diǎn)s加入頂點(diǎn)集合 dists.value=0; /* 循環(huán)計(jì)算該場(chǎng)所與鄰接場(chǎng)所之間的最短距離 */ for (i=0;i11-1;i+) /從頂點(diǎn)s確定n-1條路徑 float min=uplimit; int u=s; for (int j=0;j11;j+) /選擇當(dāng)前不在集合s中具有最短路徑的頂點(diǎn)u /* 如果有路徑比目前的最小值還小，則替換這個(gè)最小值 */ if (!sj.value & distj.valuemin) u=j; min=distj.value; su.value=1; /將頂點(diǎn)u加入集合s，表示它已在最短路徑上 for (int w=0;w11;w+

10、) /修改 if (!sw.value & edgeuw.valueuplimit & distu.value+edgeuw.valuedistw.value) distw.value=distu.value+edgeuw.value; pathw.value=u; 3.用switch語句，分支case語句出現(xiàn)友好界面，提示相關(guān)的輸入信息，為用戶的使用提供方便的輸入信息，例如：switch(c) case 0: printf(女生公寓);break; case 1: printf( 圖書館);break; case 2: printf( 體育館);break; case 3: printf(

11、一道門);break; case 4: printf( 一教學(xué)樓);break; case 5: printf( 男生公寓);break; case 6: printf( 食堂);break; case 7: printf( 體育場(chǎng));break; case 8: printf( 五道門);break; case 9: printf( 十號(hào)教學(xué)樓);break; case 10:printf(實(shí)驗(yàn)樓);break;四、功能模塊詳細(xì)設(shè)計(jì)（一）設(shè)計(jì)功能的實(shí)現(xiàn)接下來根據(jù)以上搭建的程序框架完成各個(gè)模塊的算法1、 首先是抽象數(shù)據(jù)類型的定義：圖的抽象數(shù)據(jù)類型的 定義：adt mgragh數(shù)據(jù)對(duì)象v: v是

12、具有相同特征的數(shù)據(jù)元素的 集合，稱為定點(diǎn)集數(shù)據(jù)關(guān)系r=vrvr= | v, wv, 表示從v到w的邊 2、 基本操作：createudn(&g,v,vr); / 創(chuàng)建圖初始條件：v是圖的頂點(diǎn)集，vr是圖中邊的 集合。操作結(jié)果：按v和vr的定義構(gòu)造圖 g。（二）主要算法設(shè)計(jì)及相關(guān)算法補(bǔ)充先創(chuàng)建圖存儲(chǔ)學(xué)校各個(gè)景點(diǎn)或場(chǎng)所，以圖的頂點(diǎn)表示景點(diǎn)或場(chǎng)所，以邊表示路徑，再利用迪杰斯特拉（dijkstra）算法求出校園各個(gè)地方的最短路徑，然后根據(jù)需要進(jìn)行補(bǔ)充相關(guān)算法。void buildmap() 生成地圖，輸入地圖的基本信息void shortestdist(int s) 找出場(chǎng)所間的最短距離void bh

13、() 顯示場(chǎng)所名稱void outpath(int c) 將頂點(diǎn)序列號(hào)轉(zhuǎn)換成場(chǎng)所名稱 void getdata(int s,int e) 輸出兩個(gè)場(chǎng)所之間的最短距離，和最短路徑void info(int c) c為場(chǎng)所對(duì)應(yīng)的數(shù)字號(hào)，輸出場(chǎng)所的具體信息，方便用戶的信息獲取void num()用于顯示校園導(dǎo)航系統(tǒng)的界面顯示，輸出10個(gè)地點(diǎn)的名稱void main()在主程序中運(yùn)用switch語句分別調(diào)用不同的子函數(shù)完成相應(yīng)的操作程序的具體操作流程：1. 打開導(dǎo)航，在屏幕上顯示出學(xué)校各個(gè)景點(diǎn)場(chǎng)所；2. 進(jìn)入主菜單，用switch語句選擇相應(yīng)的數(shù)字，查找學(xué)校簡(jiǎn)介，路線和個(gè)景點(diǎn)與場(chǎng)所之間的距離3. 進(jìn)入

14、子菜單，選擇相應(yīng)的數(shù)字，查詢了解景點(diǎn)與場(chǎng)所信息及景點(diǎn)與場(chǎng)所的最短距離4. 退出導(dǎo)航系統(tǒng)源程序:#include #include #include #include #include #define num 11 /最多頂點(diǎn)個(gè)數(shù) #define uplimit 100000 /定義一個(gè)無窮大的值 struct inttint value;intt edgenumnum; /edge為帶權(quán)鄰接矩陣 intt distnum; /dist為最短路程 intt pathnum; /path為最短路徑上該頂點(diǎn)的前一頂點(diǎn)的頂點(diǎn)號(hào) intt snum; /s為已求得的在最短路徑上的頂點(diǎn)號(hào) intt dnu

15、m; /d為輸出最短距離時(shí)的輔助數(shù)組 /* * 生成地圖，輸入地圖的基本信息 * */ void buildmap() int i,j; /* 初始化平面圖矩陣 */ for ( i=0;i11;i+) for ( j=0;j11;j+) edge00.value=0 , edge01.value=25 , edge02.value=25 ; edge03.value=90, edge04.value=uplimit, edge05.value=uplimit ; edge06.value=10 , edge07.value=uplimit , edge08.value=uplimit; ed

16、ge09.value=uplimit, edge010.value=uplimit; edge10.value=25 , edge11.value=0 , edge12.value=10 ; edge13.value=32, edge14.value=uplimit, edge15.value=uplimit ; edge16.value=10 , edge17.value=uplimit , edge18.value=21; edge19.value=16, edge110.value=uplimit; edge20.value=25 , edge21.value=10 , edge22.v

17、alue=0 ; edge23.value=uplimit, edge24.value=uplimit, edge25.value=uplimit ; edge26.value=uplimit, edge27.value=uplimit , edge28.value=uplimit; edge29.value=uplimit, edge210.value=uplimit; edge30.value=90 , edge31.value=32 , edge32.value=uplimit ; edge33.value=0 , edge34.value=uplimit, edge35.value=u

18、plimit ; edge36.value=uplimit, edge37.value=uplimit , edge38.value=26; edge39.value=uplimit, edge310.value=uplimit; edge40.value=uplimit, edge41.value=uplimit , edge42.value=uplimit ; edge43.value=uplimit, edge44.value=0, edge45.value=9 ; edge46.value=uplimit, edge47.value=uplimit , edge48.value=upl

19、imit; edge49.value=uplimit, edge410.value=60; edge50.value=uplimit , edge51.value=uplimit , edge52.value=uplimit ; edge53.value=uplimit, edge54.value=9, edge55.value=0 ; edge56.value=uplimit , edge57.value=15 , edge58.value=50; edge59.value=14, edge510.value=uplimit; edge60.value=10 , edge61.value=1

20、0 , edge62.value=uplimit; edge63.value=uplimit, edge64.value=uplimit, edge65.value=uplimit ; edge66.value=0 , edge67.value=35 , edge68.value=uplimit; edge69.value=30, edge610.value=uplimit; edge70.value=uplimit , edge71.value=uplimit , edge72.value=uplimit ; edge73.value=uplimit, edge74.value=uplimi

21、t, edge75.value=15 ; edge76.value=35 , edge77.value=0 , edge78.value=uplimit; edge79.value=13, edge710.value=uplimit; edge80.value=uplimit , edge81.value=21 , edge82.value=uplimit ; edge83.value=26, edge84.value=uplimit; edge85.value=50 ; edge86.value=uplimit , edge87.value=uplimit , edge88.value=0;

22、 edge89.value=22, edge810.value=10; edge90.value=uplimit , edge91.value=16 , edge92.value=uplimit ; edge93.value=uplimit, edge94.value=uplimit, edge95.value=14 ; edge96.value=30 , edge97.value=13 , edge98.value=22; edge99.value=0, edge910.value=uplimit; edge100.value=uplimit , edge101.value=uplimit

23、, edge102.value=uplimit; edge103.value=uplimit, edge104.value=60; edge105.value=uplimit ; edge106.value=uplimit , edge107.value=uplimit , edge108.value=10; edge109.value=uplimit, edge1010.value=0; /* 找出場(chǎng)所間的最短距離-迪杰斯特拉算法 */ void shortestdist(int s) for ( int i=0;i11;i+) /dist和path數(shù)組初始化 disti.value=edg

24、esi.value; /鄰接矩陣第s行元素賦值到dist中 si.value=0; /已求出最短路徑的頂點(diǎn)集合初始化 if(i!=s & disti.valueuplimit) pathi.value=s; else pathi.value=-1; /路徑存放數(shù)組初始化 ss.value=1; /頂點(diǎn)s加入頂點(diǎn)集合 dists.value=0; /* 循環(huán)計(jì)算該場(chǎng)所與鄰接場(chǎng)所之間的最短距離 */ for (i=0;i11-1;i+) /從頂點(diǎn)s確定n-1條路徑 float min=uplimit; int u=s; for (int j=0;j11;j+) /選擇當(dāng)前不在集合s中具有最短路徑的

25、頂點(diǎn)u /* 如果有路徑比目前的最小值還小，則替換這個(gè)最小值 */ if (!sj.value & distj.valuemin) u=j; min=distj.value; su.value=1; /將頂點(diǎn)u加入集合s，表示它已在最短路徑上 void bh() /顯示場(chǎng)所名稱 printf(0.女生公寓 1.圖書館 2.體育館n); printf(3.五道門 4.一號(hào)教學(xué)樓 5.男生公寓n); printf(6.食堂 7.體育場(chǎng) 8.一道門n); printf(9.十號(hào)教學(xué)樓 10.實(shí)驗(yàn)樓n); /*將頂點(diǎn)序列號(hào)轉(zhuǎn)換成場(chǎng)所名稱*/ void outpath(int c) switch(c)

26、case 0: printf(女生公寓);break; case 1: printf(圖書館);break; case 2: printf( 體育館);break; case 3: printf(五道門);break; case 4: printf(一號(hào)教學(xué)樓);break; case 5: printf( 男生公寓);break; case 6: printf(食堂);break; case 7: printf(體育場(chǎng));break; case 8: printf(一道門);break; case 9: printf( 十號(hào)教學(xué)樓);break; case 10:printf(實(shí)驗(yàn)樓);br

27、eak; /* 輸出兩個(gè)場(chǎng)所之間的最短距離，和最短路徑 */ void getdata(int s,int e) d0.value=e; int k; for (k=0;dk.value!=s;k+) dk+1.value=pathdk.value.value; if(se.value) printf(nt場(chǎng)所%d,%d之間的最短距離是：%d,s,e,diste.value); coutnt場(chǎng)所s,e之間的最短路徑是:; for(; k!=-1;k-) outpath(dk.value); if (k!=0) cout ; else printf(nt場(chǎng)所%d到場(chǎng)所%d之間沒有路徑!,s,e)

28、; void begin() int flag=1; int s,e; while ( flag ) bh(); printf(nt請(qǐng)輸入起始場(chǎng)所號(hào)與目的場(chǎng)所號(hào)：); scanf(%d%d,&s,&e); if(s=0 & e=0) flag=0; else printf(n場(chǎng)所號(hào)非法，請(qǐng)重新輸入！); shortestdist(s); getdata(s,e); /*顯示場(chǎng)所的具體信息*/void info(int c) /c為場(chǎng)所對(duì)應(yīng)的數(shù)字號(hào) switch(c)case 0: printf(t 女生公寓，住宿條件較好。); break; case 1: printf(t 圖書館，內(nèi)部藏有豐

29、富的書籍，供同學(xué)們學(xué)習(xí)參考，也可以自習(xí)。); break; case 2: printf(t 體育館，供同學(xué)們進(jìn)行體育活動(dòng)以及上體育課。); break; case 3: printf(t 校門。); break; case 4: printf(t 一號(hào)教學(xué)樓，供同學(xué)們上課和自習(xí)使用。); break; case 5: printf(t 男生公寓，提供居住。); break; case 6: printf(t 食堂，有兩層樓,是同學(xué)們用餐的地方。); break; case 7: printf(t 體育場(chǎng)，是同學(xué)們開運(yùn)動(dòng)會(huì)和進(jìn)行體育賽事的地方。); break; case 8: printf(

30、t 一道門，晚上的時(shí)候這里最熱鬧。); break; case 9: printf(t 十號(hào)教學(xué)樓，這棟樓供學(xué)習(xí)上課使用。); break; case 10: printf(t 實(shí)驗(yàn)樓，是同學(xué)們計(jì)算機(jī)上機(jī)，各系做實(shí)驗(yàn)的地方。); break;default: printf(t輸入不合法，請(qǐng)重新輸入!); break; void num()printf(*n); printf(* 校園導(dǎo)航系統(tǒng) *n); printf(*n); printf( 0.女生公寓n); printf( 1.圖書館n); printf( 2.體育館n); printf( 3.五道門n); printf( 4.一號(hào)教學(xué)樓n

31、); printf( 5.男生公寓n); printf( 6.食堂n); printf( 7.體育場(chǎng)n); printf( 8.一道門n); printf( 9.十號(hào)教學(xué)樓n); printf( 10.實(shí)驗(yàn)樓n); void main() int c; char option; printf(*n); printf(tt歡迎光臨中北大學(xué)n); printf(*n); printf(-n); printf(1.顯示場(chǎng)所的編號(hào)n); printf(2.查看場(chǎng)所的具體信息n); printf(3.找出最短路徑及計(jì)算路徑長(zhǎng)度n); printf(4.退出n); printf(-n); printf(what do you want to do?請(qǐng)輸入選擇：n); cinoption; while (option!=0) switch(option) case 1: num(); printf(tt*n); printf(ttt1.顯示場(chǎng)所的編號(hào)n); printf(ttt2.查看場(chǎng)所的具體信息n); printf(ttt3.找出最短路徑及計(jì)算路徑長(zhǎng)度n); printf(ttt4.退出n); printf(tt*n); printf(twhat do you want to do ?請(qǐng)輸入選擇:n); cinoption; system(cls