校園導(dǎo)游咨詢

1、HUBEI NORMAL UNIVERSITY課程設(shè)計論文Course ' s Thesis課程名稱數(shù)據(jù)結(jié)構(gòu)專 業(yè)通信工程班級0803班學(xué) 生 蔡兵學(xué)號_0j設(shè)計題目 校園導(dǎo)游咨詢指導(dǎo)教師孫玉霞老師時間2011年3月22日年度 2011 年第二 學(xué)期目錄一、課程目的二、基本要求三、實驗內(nèi)容及步驟1、概要設(shè)計2、詳細設(shè)計(1)建立模型(邏輯結(jié)構(gòu))(2)建立模塊之間的關(guān)系(存儲結(jié)構(gòu))(3)算法四、源程序清單五、測試結(jié)果六、課程設(shè)計總結(jié)及心得體會實驗題目：校園導(dǎo)游咨詢一、課程目的為用戶提供路徑咨詢和景點查詢，根據(jù)用戶指定的始點和終點輸出相應(yīng)路徑或者根據(jù)用戶指定的景點輸出景點的信息。二、基本要

2、求(1)設(shè)計校園平面圖，在校園景點選 10個左右景點。以圖中頂點表示校園內(nèi)各景 點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關(guān)信息。(2)為來訪客人提供圖中任意景點相關(guān)信息的查詢。(3)為來訪客人提供任意景點的問路查詢， 即查詢?nèi)我鈨蓚€景點之間的一條最短路 徑。附加要求：a、界面友好，函數(shù)功能要劃分好b、總體設(shè)計應(yīng)畫一流程圖c、程序要加必要的注釋d、要提供程序測試方案三、實驗內(nèi)容及步驟1、概要設(shè)計：在設(shè)計這個校園導(dǎo)游系統(tǒng)前考慮到整個信息的結(jié)點和操作，可以通過鄰接矩陣 借助圖的相關(guān)知識來完成。按照要求分為三個模塊，圖的信息的初始化，圖各個景點信息的查詢和景點間的最短路徑查詢

3、功能void introduce。用來查詢各景點的相關(guān)信息int shortestdistance()用來查詢?nèi)我鈨蓚€景點之間的最短路徑和經(jīng)過的景點void floyed()用來計算任意兩個景點之間的最短路徑void display(int i,int j)用來顯示任意景點之間的最短路徑和經(jīng)過的景點/*包含頭文件*/#include<string >/*定義符號常量*/#define INT_MAX 10000#define n 10/*定義全局變量*/int costnn;/* 邊的值 */int shortestnn;/* 兩點間的最短距離*/int pathnn;/* 經(jīng)過的

4、景點 */2、詳細設(shè)計：(1)建立模型(邏輯結(jié)構(gòu)：圖)(2)(3)建立模塊之間的關(guān)系(存儲結(jié)構(gòu)：鄰接矩陣)算法這個程序的關(guān)鍵代碼就利用Floyd算法求最短路徑并將路徑存放起來。Floyd算法的算法思想：設(shè)矩陣cost用來存放帶權(quán)無向圖G的權(quán)值，即矩陣元素 costij中存放著序號為i的結(jié)點到序號為j的結(jié)點之間的權(quán)值，可以通過遞推構(gòu)造 一個矩陣序列A0, A1, A2,，AN來求每對結(jié)點之間的最短路徑。其中， Akij 表示從結(jié)點Vi到結(jié)點Vj的路徑上所經(jīng)過的結(jié)點序號不大于k的最短路徑長度。初始時有A0ij=costij。當(dāng)已經(jīng)求出Ak,要遞推求解Ak+1時，可分為兩種情況來 考慮：一種清楚是該

5、結(jié)點序號為k+1的結(jié)點，此時該路徑長度與從結(jié)點Vi到結(jié)點Vj的路徑上所經(jīng)過的結(jié)點序號不大于k的最短路徑長度相同；另一種情況是該路徑經(jīng)過結(jié)點序號k+1的結(jié)點，此時該路徑可分為兩段，一段是從結(jié)點Vi到結(jié)點Vk+1的最短路徑，另一段是從結(jié)點Vk+1到結(jié)點Vj的最短路徑，此時的最短路徑長度等于這兩段最短路徑長度之和。這兩種情況的路徑長度較小者，就是要求的從結(jié)點Vi到結(jié)點Vj的路徑上所經(jīng)過的結(jié)點序號不大于k+1的最短路徑長度。Floyd具體算法設(shè)計 void floyed() int i,j,k； for(i=1;i<=n;i+) for(j=1;j<=n;j+) shortestij=co

6、stij; path皿=0;for(k=1;k<=n;k+) for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(shortestij>(shortestik+shortestkj) shortestij=shortestik+shortestkj; pathij=k; path皿i=k; )四、源程序清單#include <string> #define INT_MAX 10000#define n 10int costnn;int shortestnn;int pathnn;void introduce。；int shortestd

7、istance();void floyed();void display(int i,int j);void main()int i,j,q;char k;printf("t 歡迎來到湖北師范學(xué)院 nn");printf("t-按1進入校園導(dǎo)游指示系統(tǒng)，否則請再次輸入-n");PR:printf("t 請輸入你的選擇 nt");scanf("%d",&q);if(q!=1)printf("t 輸入錯誤，請再次輸入 n");goto PR;elsefor(i=0;i<=n;i+)fo

8、r(j=0;j<=n;j+)costij=INT_MAX;cost12=cost21=3;cost23=cost32=1;cost34=cost43=2;cost45=cost54=1;cost56=cost65=1;cost36=cost63=2;cost14=cost41=5;cost17=cost71=7；cost47=cost74=1;cost75=cost57=1;cost78=cost87=2;cost89=cost98=1;cost59=cost95=2;cost85=cost58=2;cost810=cost108=1;cost11=cost22=cost33=cost4

9、4=cost55=0;cost66=cost77=cost88=cost99=cost1010=0;while(1)printf(歡迎使用校園導(dǎo)游系統(tǒng)！n");n"）;湖北師范學(xué)院printf（"printf（"1.景點信息查詢請按i （introduc）鍵n"）;printf（"2.景點最短路徑查詢請按 s （shortestdistance）鍵n"）;printf（"3.退出系統(tǒng)請按e （exit）鍵n"）;printf（"學(xué)校景點列表:n"）;printf（"1:學(xué)校大

10、門 n"）;printf（" 2:圖書館 n"）;printf（"3:教育大樓 n"）;printf（"4:科教大廈 n"）;printf（"5:實驗樓 n"）;printf（"6:外語樓 n"）;printf（" 7:花壇 n"）;printf（"8:籃球場 n"）;printf（"9:足球場 n"）;printf（"10:食堂 n"）;printf（"請選擇服務(wù):"）;scanf（&

11、quot;n%c",&k）;switch（k）case 'i':printf（"進入景點信息查詢:"）;introduce。；break;case 's':printf("進入最短路徑查詢：”)；shortestdistance();break;case 'e':exit(0);default:printf("輸入信息錯誤！n請輸入字母i或s或e.n");break;void introduce。int a;printf("您想查詢哪個景點的詳細信息？請輸入景點編號:&

12、quot;);scanf("%d",&a);printf("n");switch(a)case 1:printf("1:學(xué)校大門nn學(xué)校的正門，氣勢宏偉。n'n");break;case 2:printf（"2:圖書館nn學(xué)校信息資源中心。n'n"）;break;case 3:printf("3:教育大樓 nn學(xué)生自學(xué)自修的天堂。n'n");break;case 4:printf("4:科教大廈 nn全校學(xué)生公共教學(xué)樓。nn");break;c

13、ase 5:printf("5:實驗樓 nncase 6:printf("6:外語樓 nncase 7:printf("7:花壇 nncase 8:printf("8:籃球場 nncase 9:printf("9:足球場 nncase 10:printf("10:食堂nn計算機機房及各種實驗設(shè)施。n'n");break;外國文化交流中心。n'n");break;美麗校園的縮影。n'n");break;籃球健兒的搖籃。nn");break;校內(nèi)最開闊的地方。nnn"

14、;);break;學(xué)生就餐的地方 。n'n");break;default:printf("景點編號輸入錯誤！請輸入1->10的數(shù)字編號！ nn"); break;int shortestdistance()int i,j;printf("請輸入要查詢的兩個景點的編號(1->10的數(shù)字編號并用','間隔):");scanf("%d,%d",&i,&j);if(i>n|i<=0|j>n|j<0)printf("輸入信息錯誤！nn")

15、;printf("請輸入要查詢的兩個景點的編號(1->10的數(shù)字編號并用','間隔):n");scanf("%d,%d",&i,&j);elsefloyed();display(i,j);return 1;void floyed()int i,j,k；for(i=1;i<=n;i+)for(j=1;j<=n;j+)shortestij=costij;pathij=0;for(k=1;k<=n;k+)for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(shortestij

16、>(shortestik+shortestkj)shortestij=shortestik+shortestkj;pathij=k;pathji=k;void display(int i,int j)int a,b;a=i;b=j；printf("您要查詢的兩景點間最短路徑是：nn");if(shortestij!=INT_MAX)if(i<j)printf("%d",b);while(path皿!=0)printf("<-%d",path皿);if(i<j)j=pathij;elsei=pathji;prin

17、tf("<-%d",a);printf("nn");printf("(%d->%d)最短距離是:%d 米nn",a,b,shortestab);elseprintf("%d",a);while(pathij!=0)printf("->%d",pathij);if(i<j)j=pathij;elsei=pathji;printf("->%d",b);printf("nn");printf("(%d->%d)最短距離是:%5d 米nn",a,b,shortestab);elseprintf（"輸入錯誤！不存在此路！nn"）;printf（"n"）;五、測試結(jié)果校園導(dǎo)游的主頁面輸入1時進入校園導(dǎo)游系統(tǒng)查詢景點