數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)_校園導(dǎo)航問(wèn)題(能通)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目: 校園導(dǎo)航問(wèn)題 學(xué) 院： 班 級(jí)： 學(xué) 生 姓 名： 學(xué) 生 學(xué) 號(hào)： 指 導(dǎo) 教 師： 2012年 12月5日課程設(shè)計(jì)任務(wù)書(shū)姓名班級(jí)學(xué)號(hào)設(shè)計(jì)題目校園導(dǎo)航問(wèn)題理論要點(diǎn)1、 利用數(shù)據(jù)結(jié)構(gòu)中所學(xué)頂點(diǎn)、邊路徑、圖、無(wú)向網(wǎng)知識(shí)，分別表示校園景點(diǎn)、景點(diǎn)距離、導(dǎo)航示意圖，實(shí)現(xiàn)校園導(dǎo)航。2、 根據(jù)路徑帶權(quán)圖分析最短路徑，實(shí)現(xiàn)校園各景點(diǎn)的最短距離。設(shè)計(jì)目標(biāo)1、實(shí)現(xiàn)校園景點(diǎn)信息查詢。2、實(shí)現(xiàn)校園景點(diǎn)最短路徑查詢。3、可以實(shí)現(xiàn)直接退出系統(tǒng)。研究方法步驟1、 想出編寫(xiě)思路2、 開(kāi)始編寫(xiě)程序3、 試著運(yùn)行程序4、 檢出錯(cuò)誤程序5、 找到解決方法預(yù)期結(jié)果實(shí)現(xiàn)當(dāng)初設(shè)計(jì)的目標(biāo)，只是保證實(shí)現(xiàn)景點(diǎn)信息查

2、詢和最短路徑查詢。計(jì)劃與進(jìn)步的安排1、2012年11月25日之前尋找到解決校園導(dǎo)航問(wèn)題思路2、2012年11月30日之前必須編寫(xiě)出程序3、2012年12月01日之前檢查程序的運(yùn)行并找出錯(cuò)誤程序4、2012年12月02日之前找到解決錯(cuò)誤的方法5、2012年12月05日寫(xiě)出數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告摘要 針對(duì)學(xué)?，F(xiàn)代化的實(shí)現(xiàn)，為了來(lái)訪我校的訪客能夠更方便的了解學(xué)校的景點(diǎn)，便于參觀也減少導(dǎo)游人員的數(shù)量，于是編寫(xiě)了這個(gè)校園導(dǎo)航系統(tǒng)。隨著現(xiàn)在科技的發(fā)展，智能化也不是一個(gè)名詞，而是實(shí)在的隨處可見(jiàn)的。算法設(shè)計(jì)與分析對(duì)于程序的實(shí)現(xiàn)起著非常重要的作用，思路才是程序的核心。我們完全可以乘科技發(fā)展的東風(fēng)，智能化的新生活而

3、奮斗，努力實(shí)現(xiàn)我們理想的社會(huì)生活，相關(guān)知識(shí)的學(xué)習(xí)，給了我們這個(gè)條件，更好地服務(wù)方便了人們?cè)谳^大校園面積的找地兒難問(wèn)題。這個(gè)程序的實(shí)現(xiàn)加深了對(duì)數(shù)據(jù)結(jié)構(gòu)算法的了解及C+的鞏固，同時(shí)為我校加快智能化進(jìn)程貢獻(xiàn)一份力，為更面大學(xué)添磚加瓦。這個(gè)校園導(dǎo)航系統(tǒng)利用算法設(shè)計(jì)里的圖來(lái)解決它將校園景點(diǎn)作為圖的結(jié)點(diǎn)將景點(diǎn)間的路徑作為圖的邊路徑距離作為邊的權(quán)值。這樣一來(lái)求兩景點(diǎn)間最短路徑的問(wèn)題就抽象成了求圖中一結(jié)點(diǎn)到另一結(jié)點(diǎn)的問(wèn)題。這也是計(jì)算機(jī)代替人工的一個(gè)實(shí)例也充分體現(xiàn)算法的重要。關(guān)鍵詞 算法設(shè)計(jì)與分析，路徑，權(quán)，無(wú)向圖 目錄摘要I課程設(shè)計(jì)題目11需求分析12概要設(shè)計(jì)13詳細(xì)設(shè)計(jì)24調(diào)試分析125用戶使用說(shuō)明126測(cè)

4、試結(jié)果137 總結(jié)體會(huì)15參考文獻(xiàn)16I數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)校園導(dǎo)航問(wèn)題1 需求分析1.1基本要求（a）設(shè)計(jì)校園平面圖，在校園景點(diǎn)選10個(gè)左右景點(diǎn)。以圖中頂點(diǎn)表示校園內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等有關(guān)信息。（b）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。（c）為來(lái)訪客人提供任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短路徑。1.2基本輸入(a)請(qǐng)使用服務(wù)：1.景點(diǎn)信息查詢請(qǐng)按 1 鍵 2.景點(diǎn)最短路徑查詢請(qǐng)按 2 鍵 3.退出系統(tǒng)請(qǐng)按 3 鍵(b)景點(diǎn)簡(jiǎn)介查詢（請(qǐng)輸入110）。請(qǐng)輸入查詢景點(diǎn)編號(hào)：(c)景點(diǎn)最短路徑查詢。請(qǐng)輸入要查詢的兩個(gè)景點(diǎn)的編號(hào)(1

5、->10的數(shù)字編號(hào)并用' '間隔):1.3輸入范圍使用服務(wù)：13，景點(diǎn)查詢：110，景點(diǎn)最短路徑查詢：110。2 概要設(shè)計(jì)2.1主要思想校園導(dǎo)航模型是由景點(diǎn)和景點(diǎn)之間的路徑組成的，所以這完全可以用數(shù)據(jù)結(jié)構(gòu)中的圖來(lái)模擬。用圖的結(jié)點(diǎn)代表景點(diǎn)，用圖的邊代表景點(diǎn)之間的路徑，結(jié)點(diǎn)值代表景點(diǎn)信息，邊的權(quán)值代表景點(diǎn)間的距離。結(jié)點(diǎn)值及邊的權(quán)值用順序表存儲(chǔ)，所以需要設(shè)計(jì)一個(gè)順序表類。本系統(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選擇語(yǔ)句

6、選擇執(zhí)行瀏覽推薦路線或查詢最短路徑并且主頁(yè)面會(huì)簡(jiǎn)單描述景點(diǎn)的信息。 2.2程序的主要功能（1）查詢功能： 查詢兩景點(diǎn)間的最短路徑需要寫(xiě)求最短路徑的函數(shù)來(lái)實(shí)現(xiàn)而對(duì)于最短路徑用上圖的邊的權(quán)值問(wèn)題由造圖函數(shù)實(shí)現(xiàn)造圖函數(shù)顯示功能模塊有說(shuō)明。 （2）顯示功能： 在校園導(dǎo)航系統(tǒng)的首頁(yè)就要顯示主要的選擇菜單而菜單則由主函數(shù)調(diào)用主菜單和造圖函數(shù)以及說(shuō)明函數(shù)來(lái)實(shí)現(xiàn)。在進(jìn)行查詢兩景點(diǎn)的路徑時(shí)也會(huì)顯示路徑則有一個(gè)輸出函數(shù)執(zhí)行。（3）退出系統(tǒng)： 選擇3可推出程序。 3詳細(xì)設(shè)計(jì)程序設(shè)計(jì)具體如下：#include<iostream>#include<string>using namespace s

7、td;#define MaxVertexNum 50 /*景點(diǎn)個(gè)數(shù)最大50*/#define MAXCOST 1000 /*定義路徑的無(wú)窮大*/#define T 8 /*目前景點(diǎn)個(gè)數(shù)*/typedef struct char name20; /*景點(diǎn)名稱*/ char number15; /*景點(diǎn)代號(hào)*/ char introduce100; /*景點(diǎn)簡(jiǎn)介*/Elemtype;typedef struct int num; /*頂點(diǎn)編號(hào)*/ Elemtype date; /*頂點(diǎn)信息*/Vertex; /*定義頂點(diǎn)*/typedef struct Vertex vexsMaxVertexNu

8、m; /*存放頂點(diǎn)的一維數(shù)組,數(shù)組第零個(gè)單元沒(méi)有用上*/ unsigned int edgesMaxVertexNumMaxVertexNum; /*存放路徑的長(zhǎng)度*/ int n,e;MGraph;MGraph MGr; /*全局變量,定義MGr為MGraph類型*/int shortestMaxVertexNumMaxVertexNum; /*定義全局變量存貯最小路徑*/int pathMaxVertexNumMaxVertexNum; /*定義存貯路徑*/void init() int i,j; MGr.vexs1.num=1; strcpy(MG,&q

9、uot;學(xué)校北門(mén)"); strcpy(MGr.vexs1.date.number,"001"); strcpy(MGroduce,"沒(méi)見(jiàn)過(guò)開(kāi)幾次，可能你將來(lái)當(dāng)主席了給你開(kāi)"); MGr.vexs2.num=2; strcpy(MG,"教學(xué)主樓"); strcpy(MGr.vexs2.date.number,"002"); strcpy(MGroduce,"學(xué)校主教學(xué)樓，我們上課的地方。")

10、; MGr.vexs3.num=3; strcpy(MG,"科技大廈"); strcpy(MGr.vexs3.date.number,"003"); strcpy(MGroduce,"上課、上自習(xí)的地方。"); MGr.vexs4.num=4; strcpy(MG,"圖書(shū)館"); strcpy(MGr.vexs4.date.number,"004"); strcpy(MGr.vexs4.date.

11、introduce,"借書(shū)自習(xí)的地方。"); MGr.vexs5.num=5; strcpy(MG,"體育場(chǎng)"); strcpy(MGr.vexs5.date.number,"005"); strcpy(MGroduce,"舉辦運(yùn)動(dòng)會(huì)的地方。"); MGr.vexs6.num=6; strcpy(MG,"第十八公寓"); strcpy(MGr.vexs6.date.number,"006

12、"); strcpy(MGroduce,"帥哥住的地方。"); MGr.vexs7.num=7; strcpy(MG,"信息報(bào)告大廳"); strcpy(MGr.vexs7.date.number,"007"); strcpy(MGroduce,"開(kāi)會(huì)、開(kāi)講座的地方。"); MGr.vexs8.num=8; strcpy(MG,"東湖"); strcpy(

13、MGr.vexs8.date.number,"008"); strcpy(MGroduce,"散心的好地方，風(fēng)景優(yōu)美。"); MGr.vexs9.num=9; strcpy(MG,"沁芳園"); strcpy(MGr.vexs9.date.number,"009"); strcpy(MGroduce,"吃飯的首選之地。"); MGr.vexs10.num=10; strcpy(MGr.vexs10.

14、,"理學(xué)院"); strcpy(MGr.vexs10.date.number,"010"); strcpy(MGroduce,"帥哥所在的院系。小六也在"); for(i=1;i<=T;i+) for(j=1;j<=T;j+) MGr.edgesij=MAXCOST; for(i=1;i<=T;i+) shortestii=0; /*初始化*/ MGr.edges12=MGr.edges21=100; MGr.edges25=MGr.edges52=50; MGr.

15、edges13=MGr.edges31=200; MGr.edges28=MGr.edges82=1500; MGr.edges57=MGr.edges75=50; MGr.edges78=MGr.edges87=700; MGr.edges67=MGr.edges76=500; MGr.edges34=MGr.edges43=50; MGr.edges46=MGr.edges64=450; MGr.edges49=MGr.edges94=20; MGr.edges310=MGr.edges103=10; MGr.edges11=MGr.edges22=MGr.edges33=MGr.edge

16、s44=MGr.edges55=0; MGr.edges66=MGr.edges77=MGr.edges88=MGr.edges99=MGr.edges1010=0; void introduce() int n; cout<<"請(qǐng)輸入查詢景點(diǎn)編號(hào)："<<endl; cin>>n; switch(n) case 1: cout<<"景點(diǎn)編號(hào)："<<MGr.vexs1.date.number<<"景點(diǎn)名稱："<<MG;

17、cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; case 2: cout<<"景點(diǎn)編號(hào)："<<MGr.vexs2.date.number<<"景點(diǎn)名稱："<<MG; cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; case 3: cout<

18、<"景點(diǎn)編號(hào)："<<MGr.vexs3.date.number<<"景點(diǎn)名稱："<<MG; cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; case 4: cout<<"景點(diǎn)編號(hào)："<<MGr.vexs4.date.number<<"景點(diǎn)名稱："<<MGr.vexs4.date.

19、name; cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; case 5: cout<<"景點(diǎn)編號(hào)："<<MGr.vexs5.date.number<<"景點(diǎn)名稱："<<MG; cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; case 6: co

20、ut<<"景點(diǎn)編號(hào)："<<MGr.vexs6.date.number<<"景點(diǎn)名稱："<<MG; cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; case 7: cout<<"景點(diǎn)編號(hào)："<<MGr.vexs7.date.number<<"景點(diǎn)名稱："<<MGr.vexs7

21、.; cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; case 8: cout<<"景點(diǎn)編號(hào)："<<MGr.vexs8.date.number<<"景點(diǎn)名稱："<<MG; cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; case

22、 9: cout<<"景點(diǎn)編號(hào)："<<MGr.vexs9.date.number<<"景點(diǎn)名稱："<<MG; cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; case 10: cout<<"景點(diǎn)編號(hào)："<<MGr.vexs10.date.number<<"景點(diǎn)名稱："<<M

23、G; cout<<"景點(diǎn)簡(jiǎn)介："<<MGroduce<<endl; break; default: cout<<"輸入序號(hào)錯(cuò)誤。" break; void floyd() int i,j,k; for(i=1;i<=T;i+) for(j=1;j<=T;j+) shortestij=MGr.edgesij; pathij=0; /*初始化數(shù)組*/ for(k=1;k<=T;k+) for(i=1;i<=T;i+)

24、for(j=1;j<=T;j+) if(shortestij>(shortestik+shortestkj) shortestij=shortestik+shortestkj; pathij=k; pathji=k;/*記錄經(jīng)過(guò)的路徑*/ /end_if /end_forvoid display(int i,int j)/* 打印兩個(gè)景點(diǎn)的路徑及最短距離 */ int a,b; a=i; b=j; cout<<"您要查詢的兩景點(diǎn)間最短路徑是:nn" if(shortestij!=MaxVertexNum) if(i<j) cout<<

25、;b; while(pathij!=0) /* 把i到j(luò)的路徑上所有經(jīng)過(guò)的景點(diǎn)按逆序打印出來(lái)*/ cout<<"<-"<<pathij; if(i<j) j=pathij; else i=pathji; cout<<"<-"<<a; cout<<"nn" cout<<a<<"->"<<b<<"最短距離是"<<shortestab<<"

26、;米"<<"nn" else cout<<a; while(pathij!=0) /* 把i到j(luò)的路徑上所有經(jīng)過(guò)的景點(diǎn)按順序打印出來(lái)*/ cout<<"->"<<pathij; if(i<j) j=pathij; else i=pathji; cout<<"->"<<b; cout<<"nn" cout<<a<<"->"<<b<<&

27、quot;最短距離是:"<<shortestab<<"米nn"<<endl; else cout<<"輸入錯(cuò)誤！不存在此路！nn" /*display*/int shortestdistance()/*要查找的兩景點(diǎn)的最短距離*/ int i,j; cout<<"請(qǐng)輸入要查詢的兩個(gè)景點(diǎn)的編號(hào)(1->10的數(shù)字編號(hào)并用' '間隔):" cin>>i>>j; if(i>T|i<=0|j>T|j<0)

28、cout<<"輸入信息錯(cuò)誤！nn" cout<<" 請(qǐng)輸入要查詢的兩個(gè)景點(diǎn)的編號(hào)(1->10的數(shù)字編號(hào)并用' '間隔):n" cin>>i>>j; else floyd(); display(i,j); return 1;/*shortestdistance*/ int main()system("color 2f"); char k; init(); cout<<"*n" cout<<"* Welcome *n

29、" cout<<"* *n" cout<<"* 黑科技校園導(dǎo)游咨詢 *n" cout<<"* *n" cout<<"* 學(xué)生：高旭強(qiáng) 班級(jí)：數(shù)學(xué)11-1班 學(xué)號(hào)：21 *n" cout<<"*n" while(1) cout<<"1.景點(diǎn)信息查詢請(qǐng)按 1 鍵n" cout<<"2.景點(diǎn)最短路徑查詢請(qǐng)按 2 鍵n" cout<<"3.退出系統(tǒng)請(qǐng)按 3 鍵n" cout<<"請(qǐng)選擇服務(wù):" cin>>k; switch(k) case '1': cout<<"景點(diǎn)簡(jiǎn)介查詢（請(qǐng)輸入110）。" introduce(); break; case '2': cout<<"景點(diǎn)最短路徑查詢。" shortestdistance(); break; case '3': exit(0);