數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—校園導(dǎo)航報(bào)告

1、下載可編輯課程設(shè)計(jì)報(bào)告學(xué)院、系：大學(xué)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系專業(yè)：軟件工程班級(jí)：2008級(jí)9班課程設(shè)計(jì)科目數(shù)據(jù)結(jié)構(gòu)學(xué)生：04080904 喆指導(dǎo)教師：婁雅芳完成時(shí)間：2010 年 10 月-12 月.專業(yè) .整理 .下載可編輯校園導(dǎo)航系統(tǒng)設(shè)計(jì)報(bào)告一、設(shè)計(jì)任務(wù)與目標(biāo)設(shè)計(jì)要求：設(shè)計(jì)你的學(xué)校的平面圖，至少包括10 個(gè)以上的場(chǎng)所，每?jī)蓚€(gè)場(chǎng)所間可以有不同的路，且路長(zhǎng)也可能不同，找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路徑（最短路徑）。本系統(tǒng)是一個(gè)涉及大學(xué)學(xué)院相關(guān)景點(diǎn)和場(chǎng)所查詢系統(tǒng), 是為了方便人們能夠更快更準(zhǔn)地獲得學(xué)校各個(gè)景點(diǎn)和場(chǎng)所的詳細(xì)信息。本系統(tǒng)為用戶提供以下功能:( 一) 、查詢了解學(xué)校概況，為導(dǎo)游參觀者提

2、供關(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) 調(diào)試，在設(shè)計(jì)完成后，調(diào)試系統(tǒng)運(yùn)行的狀況，修改完善系統(tǒng) , 然后進(jìn)行測(cè)試。二、方案設(shè)計(jì)與論證校園旅游模型是由各個(gè)景點(diǎn)

3、和景點(diǎn)以及場(chǎng)所和場(chǎng)所之間的路徑組成的，所以這完全可以用數(shù)據(jù)結(jié)構(gòu)中的圖來模擬。用圖的結(jié)點(diǎn)代表景點(diǎn)或場(chǎng)所，用圖的.專業(yè) .整理 .下載可編輯邊代表景點(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)需要查詢景點(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、打開

4、導(dǎo)航在屏幕顯示輸出學(xué)校各個(gè)景點(diǎn)場(chǎng)所選查擇詢相學(xué)應(yīng)校數(shù)簡(jiǎn)介字，導(dǎo)航參觀路線和各2、主菜單個(gè)景點(diǎn)與場(chǎng)所之間的距離回車返回主菜選擇屏幕所設(shè)菜單單進(jìn)入子菜單選擇景點(diǎn)與場(chǎng)所，查詢了解景點(diǎn)與選擇相應(yīng)數(shù)字3、子菜單場(chǎng)所信息，及景點(diǎn)與場(chǎng)所之間的最短路徑退出系統(tǒng)4、退出導(dǎo)航三、算法說明（一）設(shè)計(jì)功能的實(shí)現(xiàn)接下來根據(jù)以上搭建的程序框架完成各個(gè)模塊的算法1、首先是抽象數(shù)據(jù)類型的定義：.專業(yè) .整理 .下載可編輯圖的抽象數(shù)據(jù)類型的定義：ADTMgragh數(shù)據(jù)對(duì)象 V:V是具有相同特征的數(shù)據(jù)元素的集合，稱為定點(diǎn)集數(shù)據(jù)關(guān)系 R=VRVR= | V, W V, 表示從 V 到 W的邊2、 基本操作：CreateUDN(&G

5、,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)算法。四、全部源程序清單#include stdio.h#include iostream.h#include malloc.h#include conio.h#include stdlib.h#defineNum11/最多頂點(diǎn)個(gè)數(shù)#defineuplimit100000/定義一個(gè)無窮

6、大的值struct inttint value;inttEdgeNumNum;/Edge為帶權(quán)鄰接矩陣inttdistNum;/dist為最短路程inttpathNum;/path為最短路徑上.專業(yè) .整理 .下載可編輯該頂點(diǎn)的前一頂點(diǎn)的頂點(diǎn)號(hào)inttSNum;/S為已求得的在最短路徑上的頂點(diǎn)號(hào)intt DNum;/* 生成地圖，輸入地圖的基本信息*/voidBuildMap()inti,j;/*初始化平面圖矩陣*/for(i=0;i11;i+)for(j=0;j11;j+)Edge00.value=0,Edge01.value=25,Edge02.value=25 ;Edge03.value

7、=90,Edge04.value=uplimit,Edge05.value=uplimit ;Edge06.value=10,Edge07.value=uplimit,Edge08.value=uplimit;Edge09.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.v

8、alue=21;Edge19.value=16,Edge110.value=uplimit;Edge20.value=25,Edge21.value=10,Edge22.value=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,Edge

9、32.value=uplimit ;Edge33.value=0,Edge34.value=uplimit,Edge35.value=uplimit ;.專業(yè) .整理 .下載可編輯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.va

10、lue=9 ;Edge46.value=uplimit,Edge47.value=uplimit,Edge48.value=uplimit;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

11、.value=uplimit;Edge60.value=10,Edge61.value=10,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=u

12、plimit,Edge74.value=uplimit,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.val

13、ue=0;Edge89.value=22,Edge810.value=10;.專業(yè) .整理 .下載可編輯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,E

14、dge102.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=Edgesi.value;/鄰接矩陣第

15、 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 中具有最短路徑的頂點(diǎn)u/*如果有路徑比目前的最小值還小，則替換這

16、個(gè)最小值*/if (!Sj.value & distj.valuemin).專業(yè) .整理 .下載可編輯u=j;min=distj.value;Su.value=1;/將頂點(diǎn) u 加入集合S，表示它已在最短路徑上for (int w=0;w11;w+)/修改if(!Sw.value&Edgeuw.valueuplimit&distu.value+Edgeuw.valuedistw.value)distw.value=distu.value+Edgeuw.value;pathw.value=u;void bh()/顯示場(chǎng)所名稱coutt0.女生公寓1.圖書館2.體育館 endl;coutt3.校東

17、門4.一教學(xué)樓5.教師公寓 endl;coutt6.食堂7.體育場(chǎng)8.校南門 endl;coutt9.大學(xué)生活動(dòng)中心10.實(shí)驗(yàn)樓 endl;/*將頂點(diǎn)序列號(hào)轉(zhuǎn)換成場(chǎng)所名稱*/void Outpath(int c) switch(c)case 0: cout女生公寓 ;break;case 1: cout 圖書館 ;break;case 2: cout 體育館 ;break;case 3: cout 校東門 ;break;case 4: cout 一教學(xué)樓 ;break;case 5: cout 教師公寓 ;break;case 6: cout 食堂 ;break;case 7: cout 體育

18、場(chǎng) ;break;case 8: cout 校南門 ;break;case 9: cout 大學(xué)生活動(dòng)中心 ;break;case 10:cout實(shí)驗(yàn)樓 ;break;.專業(yè) .整理 .下載可編輯/* 輸出兩個(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)coutnt場(chǎng)所s,e之間的最短距離是：diste.valueendl;coutnt場(chǎng)所 s,e 之間的最短路徑是 :;for(; k!

19、=-1;k-)Outpath(Dk.value);if (k!=0)cout ;elsecoutnt場(chǎng)所 s 到場(chǎng)所 e 之間沒有路徑 !endl;void Begin()int flag=1;int s,e;while ( flag )bh();coutse;coutendl;if(s=0 & e=0)flag=0;elsecoutn場(chǎng)所號(hào)非法，請(qǐng)重新輸入！;ShortestDist(s);getdata(s,e);.專業(yè) .整理 .下載可編輯/* 顯示場(chǎng)所的具體信息 */void info(int c)/c為場(chǎng)所對(duì)應(yīng)的數(shù)字號(hào)switch(c)case 0:coutt 女生公寓，具體指桂園七

20、棟，住宿條件較好。endl;break;case 1:coutt 圖書館，部藏有豐富的書籍，供同學(xué)們學(xué)習(xí)參考，也可以自習(xí)。 endl;break;case 2:coutt 體育館，供同學(xué)們進(jìn)行體育活動(dòng)以及上體育課。endl;break;case 3:coutt 校東門，大學(xué)學(xué)院的正門。 endl; break;case 4:coutt 一教學(xué)樓，供同學(xué)們上課和自習(xí)使用。 endl; break;case 5:coutt 教師公寓，提供給單身的老師們居住。 endl; break;case 6:coutt 食堂，有兩層樓 , 是同學(xué)們用餐的地方。 endl; break;case 7:coutt

21、 體育場(chǎng)，是同學(xué)們開運(yùn)動(dòng)會(huì)和進(jìn)行體育賽事的地方。 endl;break;case 8:coutt 校南門，這是同學(xué)，老師比較集中的地方。晚上的時(shí)候這里最熱鬧。； endl;coutt另一邊是小店的集中地，相當(dāng)于一個(gè)小型商業(yè)街。.專業(yè) .整理 .下載可編輯endl;break;case 9:coutt 大學(xué)生活動(dòng)中心，這棟樓是辦公樓也是活動(dòng)中心，主要供各系的同學(xué)辦活動(dòng)使用； endl;coutt這棟樓的后面就是高爾夫球場(chǎng)，主要供旅游系的同學(xué)上課使用。 endl;break;case 10:coutt 實(shí)驗(yàn)樓，是同學(xué)們計(jì)算機(jī)上機(jī)，各系做實(shí)驗(yàn)的地方。 endl;break;case 11:syste

22、m(cls);break;default:coutt輸入不合法，請(qǐng)重新輸入!endl;break;void num()couttt*endl;couttt*校園導(dǎo)航系統(tǒng)*endl;couttt*endl;couttt 0.女生公寓 endl;couttt 1.圖書館 endl;couttt 2.體育館 endl;couttt 3.校東門 endl;couttt 4.一教學(xué)樓 endl;couttt 5.教師公寓 endl;couttt 6.食堂 endl;couttt 7.體育場(chǎng) endl;couttt 8.校南門 endl;couttt 9.大學(xué)生活動(dòng)中心 endl;couttt 10.實(shí)驗(yàn)

23、樓 endl;void main().專業(yè) .整理 .下載可編輯int c;char option=0;coutt-endl;coutt* * * * endl;coutt* * * * * * * * * * * * endl; coutt * * * * * * * * * * * * * * endl; coutt * * * * * * * * * * * * endl;coutt* * * * * * endl;coutt-endl;coutendl;coutendl;coutt*endl;coutttt歡迎光臨大學(xué)學(xué)院 endl;coutt*endl;coutendltendl;c

24、outttt1.顯示場(chǎng)所的編號(hào) endl;coutttt2.查看場(chǎng)所的具體信息 endl;coutttt3.找出最短路徑及計(jì)算路徑長(zhǎng)度endl;coutttt4.退出 endl;coutt endl;coutendloption;while (option!=0)switch(option)case 1:num();coutendltt*endl;coutttt1.顯示場(chǎng)所的編號(hào) endl;coutttt2.查看場(chǎng)所的具體信息 endl;coutttt3.找出最短路徑及計(jì)算路徑長(zhǎng)度endl;coutttt4.退出 endl;.專業(yè) .整理 .下載可編輯couttt*endl;coutoption;system(cls);/清屏break;case 2:/具體信息coutendl;coutendl;coutt請(qǐng)從 0 10 中選擇任意字母，查看所對(duì)應(yīng)場(chǎng)所的具體信息：endl;coutt選擇 11 則退出該命令 c;info(c);if(c=11)coutendltt*endl;coutttt1.顯示場(chǎng)所的編號(hào) endl;coutttt2.查看場(chǎng)所的具體信息 endl;coutttt3.找出最短路徑及計(jì)算路徑長(zhǎng)度endl;coutttt4.退出 endl;couttt*endl;coutoption;break;cas