《校園導(dǎo)游咨詢(xún)系統(tǒng)---數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(共35頁(yè))》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《校園導(dǎo)游咨詢(xún)系統(tǒng)---數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(共35頁(yè))（35頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-----傾情為你奉上 石家莊經(jīng)濟(jì)學(xué)院 本科生課程設(shè)計(jì)報(bào)告書(shū) 　 題　 目 校園導(dǎo)游咨詢(xún)系統(tǒng) 姓　　名　 顏建學(xué) 學(xué)　　號(hào)　　 1 學(xué) 　院　　　 信息工程學(xué)院　 專(zhuān)　　業(yè)　　　 計(jì)算機(jī)方向　 指導(dǎo)教師　　　 XXXXXX 完成日期： 2012-07-5 校園導(dǎo)游咨詢(xún)系統(tǒng) 1 需求分析 本程序的主要目的是為了提供本學(xué)校的景點(diǎn)的路徑咨詢(xún)和來(lái)訪(fǎng)客人以及剛來(lái)報(bào)到的新生

2、提供一個(gè)快捷方便的路徑咨詢(xún)，快速有效的提高了用戶(hù)的熟悉度。。滿(mǎn)足用戶(hù)查詢(xún)的需要： 1、從石家莊經(jīng)濟(jì)學(xué)院的平面地圖中選取出10個(gè)有代表性的景點(diǎn)。 2、為來(lái)訪(fǎng)的客人提供圖中任意景點(diǎn)相關(guān)信息的查詢(xún)。當(dāng)用戶(hù)輸入正確時(shí)，為用戶(hù)輸出景點(diǎn)的相關(guān)信息；當(dāng)用戶(hù)輸入不合法時(shí)，提示用戶(hù)輸入有誤并返回讓用戶(hù)重新輸入。 3、為來(lái)訪(fǎng)的客人提供圖中任意景點(diǎn)的路徑查詢(xún)，即查詢(xún)?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短簡(jiǎn)單路徑。當(dāng)用戶(hù)輸入正確時(shí)，為用戶(hù)輸出任意兩景點(diǎn)的最短路徑；當(dāng)用戶(hù)輸入不合法時(shí)，提示用戶(hù)輸入有誤并返回讓用戶(hù)重新輸入。 4、為來(lái)訪(fǎng)客人推薦參觀路線(xiàn)。 2 概要設(shè)計(jì) 1、抽象數(shù)據(jù)類(lèi)型圖的定義如下： ADT Graph{

3、 數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱(chēng)為頂點(diǎn)集。 數(shù)據(jù)關(guān)系R： R={VR} VR={(v,w)|v,w∈V,(v,w)表示v和w之間存在路徑} 基本操作P： CreatGraph70321(&G,V,VR) 初始條件：V是圖的頂點(diǎn)集，VR是圖中邊的集合。 操作結(jié)果：按V和VR的定義構(gòu)造圖G。 DestroyGraph70321(&G) 初始條件：圖G存在。 操作結(jié)果：銷(xiāo)毀圖G。 LocateVex70321(G,u) 初始條件：圖G存在，u和G中頂點(diǎn)有相同特征。 操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其他信息。 G

4、etVex70321(G,v) 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。 操作結(jié)果：返回v的信息。 FirstEdge70321(G,v) 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。 操作結(jié)果：返回依附于v的第一條邊。若該頂點(diǎn)在G中沒(méi)有鄰接點(diǎn)，則返回“空”。 NextEdge70321(G,v,w) 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。 操作結(jié)果：返回依附于v的（相對(duì)于w的）下一條邊。若不存在，則返回“空”。 InsertVex70321(&G,v) 初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。 操作結(jié)果：在圖中增添新頂點(diǎn)v。 DeleteVex703

5、21(&G,v) 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。 操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的邊。 InsertEdge70321(&G,v,w) 初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。 操作結(jié)果：在G中增添邊(v,w). DeleteEdge70321(&G,v,w) 初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。 操作結(jié)果：在G中刪除邊(v,w)。 GetShortestPath70321(G,st,nd,&Path) 初始條件：圖G存在，st和nd是G中兩個(gè)頂點(diǎn)。 操作結(jié)果：若st和nd之間存在路徑，則以Path返回兩點(diǎn)之間一條最短路徑

6、，否則返回其他信息。 }ADT Graph 主程序 void main() {初始化； do{ 接受命令（輸入景點(diǎn)信息或輸出最短路徑）； 處理命令； }while（“命令”！=“退出”）； ｝ 2、　調(diào)用的函數(shù)有如下： void CreateUDN70321(int v,int a); /* 造圖函數(shù) */ void narrate70321(); /*說(shuō)明函數(shù)*/ void ShortestPath70321(int num); /*最短路徑函數(shù)*/ void output70321(int sight1,int s

7、ight2); /*輸出函數(shù)*/ char Menu70321(); /* 主菜單 */ void search70321(); /* 查詢(xún)景點(diǎn)信息 */ char SearchMenu70321(); /* 查詢(xún)子菜單 */ void HaMiTonian70321(int); /* 哈密爾頓圖的遍歷 */ void NextValue70321(int); void display70321(); /* 顯示遍歷結(jié)果 */ 3、運(yùn)行主界面： ***************歡 迎 使 用 校 園 導(dǎo) 游 程 序******

8、****** ******************石**家**莊**經(jīng)**濟(jì)**學(xué)**院******************** 制作者：信息工程學(xué)院 1 顏建學(xué) ?。?！歡迎您的使用?。?！ ———————————————————————————————— 景點(diǎn)名稱(chēng) ———————————————————————————————— （0）教學(xué)主樓 （1）足球場(chǎng) （2）燈光籃球場(chǎng) （3）惠馨園 （4）實(shí)驗(yàn)樓

9、 （5）計(jì)算機(jī)實(shí)驗(yàn)室 （6）地球科學(xué)博物館 （7）學(xué)術(shù)報(bào)告廳 （8）圖書(shū)館 （9）噴泉 ———————————————————————————————— ┏━━━━━━━━━━━━━━━┓ ┃ 1、查詢(xún)景點(diǎn)路徑 ┃ ┃ 2、查詢(xún)景點(diǎn)信息 ┃ ┃ 3、推薦參觀路線(xiàn) ┃ ┃ e、退出 ┃ ┗━━━━━━━━━━━━━━━┛ 子界

10、面如下： ┏━━━━━━━━━━━━━━━┓ ┃ 1、按照景點(diǎn)編號(hào)查詢(xún) ┃ ┃ 2、按照景點(diǎn)名稱(chēng)查詢(xún) ┃ ┃ e、返回 ┃ ┗━━━━━━━━━━━━━━━┛ 3、模塊圖表示如下： 主程序模塊 處理功能模塊 無(wú)向圖存儲(chǔ)模塊 為用戶(hù)輸出景點(diǎn)信息 為用戶(hù)輸出兩景點(diǎn)最佳路徑 推薦參觀路徑 3 詳細(xì)設(shè)計(jì) 從石家莊經(jīng)濟(jì)學(xué)院的平面地圖中選取出10個(gè)有代表性的景點(diǎn)，將其抽象成無(wú)向帶權(quán)網(wǎng)并用鄰接矩陣來(lái)表示。以圖中的頂點(diǎn)代表景點(diǎn)，存放景點(diǎn)名稱(chēng)、代號(hào)、簡(jiǎn)介等信息，權(quán)值代表兩地之間的距離。 1、 圖

11、的存儲(chǔ)結(jié)構(gòu)如下： #define Max 20000 #define NUM 9 typedef struct ArcCell{ int adj; /* 相鄰接的景點(diǎn)之間的路程 */ }ArcCell; /* 定義邊的類(lèi)型 */ typedef struct VertexType70321{ int number; /* 景點(diǎn)編號(hào) */ char *sight; /* 景點(diǎn)名稱(chēng) */ char *description; /* 景點(diǎn)描述 */ }VertexType; /* 定義頂點(diǎn)的類(lèi)型 */ typedef struct{ VertexTyp

12、e vex[NUM]; /* 圖中的頂點(diǎn)，即為景點(diǎn) */ ArcCell arcs[NUM][NUM]; /* 圖中的邊，即為景點(diǎn)間的距離 */ int vexnum,arcnum; /* 頂點(diǎn)數(shù)，邊數(shù) */ }MGraph; /* 定義圖的類(lèi)型 2、該程序的算法如下： 1)void CreateUDN70321(MGraph&G) /* 造圖函數(shù) */ { //采用鄰接矩陣表示法，構(gòu)造無(wú)向網(wǎng)G scanf(&G.vexnum,&G.arcnum,&IncInfo);// IncInfo為0則各弧不含其它信息 for(i=0;i<

13、 G.vexnum;++i)scanf(&G.vexs[i]);//構(gòu)造頂點(diǎn)向量 for(i=0;i< G.vexnum;++i)//初始化鄰接矩陣 for(j=0;j< G.vexnum;++j)G.arcs[]i[j]={INFINITY,NULL} for(k=0;k< G.arcnum;++k)//構(gòu)造鄰接矩陣 { scanf(&v1,&v2,&w);//輸入一條邊依附的頂點(diǎn)及權(quán)值 i=LocateVex(G,v1);j= LocateVex(G,v2);//確定V1和V2在G中的位置 G.arcs[i][j].adj=w

14、;//弧<v1,v2>的權(quán)值 If(IncInfo)Input(*G.arcs[i][j].info);//若弧含有相關(guān)信息，則輸入 G.arcs[j][i]= G.arcs[i][j];//置<v1,v2>的對(duì)稱(chēng)弧<v2,v1> } Return OK; } 2)void narrate70321() /* 說(shuō)明函數(shù) */ { k=0; printf("\n\t\t***************歡 迎 使 用 校 園 導(dǎo) 游 程 序*************\n"); printf

15、("\n\t\t*******************石**家**莊**經(jīng)**濟(jì)**學(xué)**院************************\n"); printf("\n\t\t制作者： 信息工程學(xué)院 1 顏建學(xué) ！??！歡迎您使用?。。n"); printf("\n\t\t__________________________________________________________________\n"); printf("\t\t\t\t\t 景點(diǎn)名稱(chēng)\t\t\n");

16、 printf("\t\t__________________________________________________________________\n"); for(i=0;i<NUM;i++) { printf("\t\t (%2d)%-15s\t\t",i,G.vex[i].sight); if(i%2==((NUM-1)%2))printf("\n");//奇數(shù)編號(hào)景點(diǎn)在右邊，偶數(shù)編號(hào)景點(diǎn)在左邊 k=k+1; } printf("\t\t______________

17、___________________________________________________\n"); } 3) void ShortestPath70321(int num) { //用迪杰斯特拉算法求G的v0頂點(diǎn)到其余頂點(diǎn)的最短路徑P[v]及其帶權(quán)長(zhǎng)度 D[v] //若P[v][w]為T(mén)RUE,則 w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn) //final[v]為T(mén)RUE當(dāng)且僅當(dāng)v屬于S，即已經(jīng) 求得從 v0到v的最短路徑 for(v=0;v<G.vexnum;++v) {

18、Final[v]=FALSE;D[v]= G.arcs[v0][v]; For(w=0;w< G.vexnum;++w)P[v][w]=FALSE; If (D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;} }//for D[v0]=0;final[v0]=TRUE; //開(kāi)始主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)的最短路徑，并加v到S集 For(i=1;i< G.vexnum;++i) { Min=INFINITY; For(w=0;w< G.vexnum;++w)

19、 If(!final[w]) If(D[w]<min){v=w;min=D[w];} Final[v]=TRUE; For(w=0;w< G.vexnum;++w) If(!final[w]&&(min+G.arcs[v][w]<D[w])) { D[w]= min+G.arcs[v][w]; P[w]=P[v];P[w][w]=TRUE; }//if }//for }// ShortestPath 4) void output70321(int sight1,int s

20、ight2) /* 輸出函數(shù) */ { if(sight2!=sight1) /* 如果景點(diǎn)二不和景點(diǎn)一輸入重合，則進(jìn)行... */ { printf(從G.vex[sight1].sight到G.vex[sight2].sight的最短路徑是:);/* 輸出提示信息 */ printf(D[a]); /* 輸出sight1到sight2的最短路徑長(zhǎng)度，存放在D[]數(shù)組中 */ printf(G.vex[sight1].sight); /* 輸出景點(diǎn)一的名稱(chēng) */ d=sight1; /* 將景點(diǎn)一的編號(hào)賦值給d */ fo

21、r(c=0;c<NUM;++c) { P[a][sight1]=0; for(b=0;b<NUM;b++) { if(G.arcs[d][b].adj<20000&&P[a][b]) /* 如果景點(diǎn)一和它的一個(gè)臨界點(diǎn)之間存在路徑且最短路徑 */ { printf(G.vex[b].sight); /* 輸出此節(jié)點(diǎn)的名稱(chēng) */ q=q+1; /* 計(jì)數(shù)變量加一，滿(mǎn)8控制輸出時(shí)的換行 */ P[a][b]=0;

22、 d=b; /* 將b作為出發(fā)點(diǎn)進(jìn)行下一次循環(huán)輸出，如此反復(fù) */ if(q%8==0) returnOK; } } } } 5)void main() /* 主函數(shù) */ { CreateUDN70321(NUM,11); do { switch(Menu()) { case '1': narrate70321(); scanf(v0); scanf(v1); ShortestPath70321(v0); /* 計(jì)

23、算兩個(gè)景點(diǎn)之間的最短路徑 */ Output70321(v0,v1); /* 輸出結(jié)果 */ break; case '2': search(); break; case '3': narrate70321(); HaMiTonian(x[0]); break; }; }while(Menu()!='e'); } 6) char Menu() /* 主菜單 */ { do { flag=1;

24、 narrate70321(); scanf(c); if(c=='1'||c=='2'||c=='3'||c=='e') flag=0; }while(flag); return c; } 7) char SearchMenu70321() /* 查詢(xún)子菜單 */ { do { flag=1; narrate70321(); scanf(&c); if(c=

25、='1'||c=='2'||c=='e') flag=0; }while(flag); return c; } 8) void search70321() /* 查詢(xún)景點(diǎn)信息 */ { do { switch 70321(SearchMenu()) { case '1': narrate70321(); scanf(&num); for(i=0;i<NUM;i++) { if(num=

26、=G.vex[i].number) { printf(G.vex[i].description); break; } } if(i==NUM) { printf(沒(méi)有找到！"); getchar70321(); } break; case '2': narrate70321(); scanf(name); for(i=0;i<NUM;i++) { if(!strcmp(name,G

27、.vex[i].sight)) { printfG.vex[i].description); break; } } if(i==NUM) { printf(沒(méi)有找到！"); } break; } }while(SearchMenu()!='e'); } 3、流程圖如下： 開(kāi)始 造圖 輸入您的選擇 您的選擇是1？ 您的選擇是2？ 您的選擇是3？ 您的選擇是100？ 結(jié)束 輸入您的第一個(gè)景點(diǎn)選擇 輸入您的第二個(gè)景點(diǎn)選擇 您的選擇是e？

28、 符合條件？ 計(jì)算最短路徑 輸出結(jié)果 按編號(hào)查詢(xún)？ 推薦最佳路徑 輸入景點(diǎn)編號(hào) 輸入景點(diǎn)名稱(chēng) 輸出結(jié)果 輸出結(jié)果 輸出結(jié)果 否 是 否 是 否 否 是 是 否 是 是 否 是 石家莊經(jīng)濟(jì)學(xué)院校園導(dǎo)游系統(tǒng)設(shè)計(jì)流程圖 信息工程學(xué)院 計(jì)算機(jī)三班 顏建學(xué) 1 4 編碼調(diào)試 校園導(dǎo)游咨詢(xún)系統(tǒng)主界面如下圖1所示，輸入1進(jìn)行景點(diǎn)路徑查詢(xún)，輸入2進(jìn)行景點(diǎn)信息查詢(xún)，輸入3時(shí)推薦參觀路線(xiàn)，輸入e時(shí)則退出本系統(tǒng)。 圖1 當(dāng)輸入1時(shí)進(jìn)入一個(gè)選擇子菜單（輸入錯(cuò)誤時(shí)，保持原有狀態(tài)），正確輸入起點(diǎn)（2）（燈光籃球場(chǎng)）和終點(diǎn)（4）（實(shí)驗(yàn)樓），屏幕將打印出兩景

29、點(diǎn)之間的最短路徑：燈光籃球場(chǎng)—〉惠馨園—〉實(shí)驗(yàn)樓，最短路徑為約430m。如下圖2所示： 圖2 當(dāng)輸入的景點(diǎn)代號(hào)不在（0-9）之間時(shí)，程序提示重新輸入，直到輸入正確。測(cè)試數(shù)據(jù)：當(dāng)起點(diǎn)輸入10終點(diǎn)輸入12時(shí)，景點(diǎn)不存在，程序提示重新輸入；當(dāng)起點(diǎn)輸入0（教學(xué)主樓）終點(diǎn)輸入12時(shí)，終點(diǎn)景點(diǎn)不存在，程序提示重新輸入；當(dāng)起點(diǎn)輸入0（教學(xué)樓）終點(diǎn)輸入8（圖書(shū)館）時(shí)，景點(diǎn)都存在，屏幕打印出兩景點(diǎn)最短路徑：教學(xué)樓—〉噴泉—〉學(xué)術(shù)報(bào)告廳—〉圖書(shū)館，最短路徑約為200m。如下圖3所示： 圖

30、3 按100推出此環(huán)節(jié)，當(dāng)在選擇主菜單選擇2時(shí)，出現(xiàn)如下圖4所示子菜單： 圖4 當(dāng)輸入1時(shí)，則按景點(diǎn)編號(hào)查詢(xún)，當(dāng)輸入6（地球科學(xué)博物館）時(shí)，屏幕上打印出此景點(diǎn)信息：里面有著名的不尋?？铸埢划?dāng)輸入4（實(shí)驗(yàn)樓）時(shí)，屏幕上打印出此景點(diǎn)信息：各專(zhuān)業(yè)實(shí)驗(yàn)的重要場(chǎng)地；當(dāng)輸入12時(shí)，此景點(diǎn)不存在，屏幕上顯示：?。?！沒(méi)*有*找*到?。。。划?dāng)輸入20時(shí)，此景點(diǎn)不存在，屏幕上顯示：?。?！沒(méi)*有*找*到?。?！。如下圖5所示： 圖5 當(dāng)輸入2時(shí)，則按景點(diǎn)名稱(chēng)查詢(xún)，當(dāng)輸入“圖書(shū)館”時(shí)，

31、屏幕上打印出此景點(diǎn)信息：圖書(shū)館是莘莘學(xué)子學(xué)習(xí)的園地，里面有各科資料，每人可以任借五本書(shū)；當(dāng)輸入“計(jì)算機(jī)實(shí)驗(yàn)室”時(shí)，屏幕上打印出此景點(diǎn)信息：計(jì)算機(jī)專(zhuān)業(yè)實(shí)驗(yàn)實(shí)習(xí)場(chǎng)所；當(dāng)輸入“教學(xué)三號(hào)樓”時(shí)，此景點(diǎn)不存在，屏幕上顯示：?。?！沒(méi)*有*找*到！?。?；如下圖6所示： 圖6 當(dāng)在選擇主菜單中輸入3時(shí)，則系統(tǒng)推薦旅游路徑： 1）教學(xué)主樓—〉足球場(chǎng)—〉燈光籃球場(chǎng)—〉惠馨園—〉實(shí)驗(yàn)樓—〉噴泉—〉學(xué)術(shù)報(bào)告廳—〉地球科學(xué)博物館—〉計(jì)算機(jī)實(shí)驗(yàn)室—〉圖書(shū)館—〉校園出口 2）教學(xué)主樓—〉足球場(chǎng)—〉燈光籃球場(chǎng)—〉惠馨園—〉實(shí)驗(yàn)樓—〉噴泉—〉學(xué)術(shù)報(bào)

32、告廳—〉圖書(shū)館—〉計(jì)算機(jī)實(shí)驗(yàn)室—〉地球科學(xué)博物館—〉校園出口 3）教學(xué)主樓—〉地球科學(xué)博物館—〉計(jì)算機(jī)實(shí)驗(yàn)室—〉圖書(shū)館—〉學(xué)術(shù)報(bào)告廳—〉噴泉—〉實(shí)驗(yàn)樓—〉惠馨園—〉燈光籃球場(chǎng)—〉足球場(chǎng)—〉校園出口 如下圖7所示 圖7 在選擇主菜單輸入錯(cuò)誤時(shí)，程序不作反應(yīng)，當(dāng)輸入e時(shí)，則退出，如下圖8所示 圖8 由于本人的設(shè)計(jì)能力有限，在設(shè)計(jì)過(guò)程中難免出現(xiàn)錯(cuò)誤。本程序在調(diào)試時(shí)，出現(xiàn)了一個(gè)很棘手的錯(cuò)誤，出現(xiàn)了結(jié)構(gòu)體變量G的重復(fù)定義，經(jīng)過(guò)自己的多次修改，沒(méi)有成功，最后在老師的幫助下，將

33、變量的定義從函數(shù)定義里放到了函數(shù)聲明里，成功的修改了那個(gè)問(wèn)題。當(dāng)然還有一些簡(jiǎn)單的語(yǔ)法錯(cuò)誤，這些錯(cuò)誤都是比較好改的，在此就不一一列舉了。 5 設(shè)計(jì)體會(huì) 本次課程設(shè)計(jì)使我提高了應(yīng)用計(jì)算能力、編寫(xiě)代碼的基本能力、繪畫(huà)流程圖能力，熟悉了規(guī)范和標(biāo)準(zhǔn)，同時(shí)對(duì)于本設(shè)計(jì)的課程都有了全面的復(fù)習(xí)，獨(dú)立思考的能力也有了提高。 1、當(dāng)寫(xiě)第一步需求分析時(shí)，本以為是問(wèn)題的簡(jiǎn)單描述，所以寫(xiě)的比較簡(jiǎn)單，但是讓老師驗(yàn)收沒(méi)有通過(guò)，經(jīng)過(guò)進(jìn)一步改進(jìn)，將問(wèn)題詳細(xì)化了，并正確而準(zhǔn)確的描述了校園導(dǎo)游的輸入輸出問(wèn)題，順利通過(guò)第一步的驗(yàn)收。概要設(shè)計(jì)還是比較簡(jiǎn)單的，畢竟還沒(méi)有到算法的描述部分，這一過(guò)程很簡(jiǎn)單的就通過(guò)了，但是自己感覺(jué)對(duì)主

34、界面的設(shè)計(jì)不是很滿(mǎn)意，然后幾經(jīng)思索，設(shè)計(jì)出了自己較為滿(mǎn)意的界面。當(dāng)前兩步完成后心里便有壓力了，因?yàn)樗惴枋鰧?duì)我來(lái)說(shuō)真的有點(diǎn)難。我多次查看書(shū)籍并上網(wǎng)查詢(xún)相關(guān)資料，終于把詳細(xì)設(shè)計(jì)部分做好了。在調(diào)試程序時(shí)有一個(gè)很棘手的問(wèn)題，結(jié)構(gòu)體變量G出現(xiàn)了重復(fù)定義，最初在函數(shù)定義的文件中，后來(lái)把定義放到了函數(shù)聲明那個(gè)文件中才通過(guò)了 2、 測(cè)試數(shù)據(jù)：當(dāng)輸入1時(shí)進(jìn)入一個(gè)選擇子菜單（輸入錯(cuò)誤時(shí)，保持原有狀態(tài)），正確輸入起點(diǎn)（2）（燈光籃球場(chǎng)）和終點(diǎn)（4）（實(shí)驗(yàn)樓），屏幕將打印出兩景點(diǎn)之間的最短路徑：燈光籃球場(chǎng)—〉惠馨園—〉實(shí)驗(yàn)樓，最短路徑為約430m。當(dāng)輸入的景點(diǎn)代號(hào)不在（0-9）之間時(shí)，程序提示重新輸入，直到輸入正

35、確。測(cè)試數(shù)據(jù)：當(dāng)起點(diǎn)輸入10終點(diǎn)輸入12時(shí)，景點(diǎn)不存在，程序提示重新輸入；當(dāng)起點(diǎn)輸入0（教學(xué)主樓）終點(diǎn)輸入12時(shí)，終點(diǎn)景點(diǎn)不存在，程序提示重新輸入；當(dāng)起點(diǎn)輸入0（教學(xué)樓）終點(diǎn)輸入8（圖書(shū)館）時(shí)，景點(diǎn)都存在，屏幕打印出兩景點(diǎn)最短路徑：教學(xué)樓—〉噴泉—〉學(xué)術(shù)報(bào)告廳—〉圖書(shū)館，最短路徑約為200m。當(dāng)輸入1時(shí)，則按景點(diǎn)編號(hào)查詢(xún)，當(dāng)輸入6（地球科學(xué)博物館）時(shí)，屏幕上打印出此景點(diǎn)信息：里面有著名的不尋?？铸埢?；當(dāng)輸入4（實(shí)驗(yàn)樓）時(shí)，屏幕上打印出此景點(diǎn)信息：各專(zhuān)業(yè)實(shí)驗(yàn)的重要場(chǎng)地；當(dāng)輸入12時(shí)，此景點(diǎn)不存在，屏幕上顯示：！??！沒(méi)*有*找*到！?。?；當(dāng)輸入20時(shí)，此景點(diǎn)不存在，屏幕上顯示：?。?！沒(méi)*有*找*

36、到?。?！。當(dāng)輸入2時(shí)，則按景點(diǎn)名稱(chēng)查詢(xún)，當(dāng)輸入“圖書(shū)館”時(shí)，屏幕上打印出此景點(diǎn)信息：圖書(shū)館是莘莘學(xué)子學(xué)習(xí)的園地，里面有各科資料，每人可以任借五本書(shū)；當(dāng)輸入“計(jì)算機(jī)實(shí)驗(yàn)室”時(shí)，屏幕上打印出此景點(diǎn)信息：計(jì)算機(jī)專(zhuān)業(yè)實(shí)驗(yàn)實(shí)習(xí)場(chǎng)所；當(dāng)輸入“教學(xué)三號(hào)樓”時(shí)，此景點(diǎn)不存在，屏幕上顯示：?。?！沒(méi)*有*找*到?。。?；當(dāng)在選擇主菜單中輸入3時(shí)，則系統(tǒng)推薦旅游路徑： 1）教學(xué)主樓—〉足球場(chǎng)—〉燈光籃球場(chǎng)—〉惠馨園—〉實(shí)驗(yàn)樓—〉噴泉—〉學(xué)術(shù)報(bào)告廳—〉地球科學(xué)博物館—〉計(jì)算機(jī)實(shí)驗(yàn)室—〉圖書(shū)館—〉出口 2）教學(xué)主樓—〉足球場(chǎng)—〉燈光籃球場(chǎng)—〉惠馨園—〉實(shí)驗(yàn)樓—〉噴泉—〉學(xué)術(shù)報(bào)告廳—〉圖書(shū)館—〉計(jì)算機(jī)實(shí)驗(yàn)室—〉地球科學(xué)

37、博物館—〉出口 3）教學(xué)主樓—〉地球科學(xué)博物館—〉計(jì)算機(jī)實(shí)驗(yàn)室—〉圖書(shū)館—〉學(xué)術(shù)報(bào)告廳—〉噴泉—〉實(shí)驗(yàn)樓—〉惠馨園—〉燈光籃球場(chǎng)—〉足球場(chǎng)—〉出口 在選擇主菜單輸入錯(cuò)誤時(shí)，程序不作反應(yīng)，當(dāng)輸入e時(shí)，則退出。 本程序的時(shí)間復(fù)雜度主要發(fā)生在求最短路徑時(shí)，即算法里面的for循環(huán)語(yǔ)句，for循環(huán)語(yǔ)句三層嵌套，所以時(shí)間復(fù)雜度為n3。 3、在圖的存儲(chǔ)時(shí)本程序采用的鄰接矩陣，也可以采用鄰接表；在求兩景點(diǎn)之間的最短路徑時(shí)本程序采用的迪杰斯特拉算法，也可以采用弗洛伊德算法。 4、在本次課程設(shè)計(jì)中讓我進(jìn)一步熟悉了各種算法的使用，但感到自己在算法設(shè)計(jì)中還存在很大的不足，寫(xiě)算法時(shí)無(wú)法脫離課本，更是需要老師、

38、同學(xué)的幫助，甚至有的算法不得不從網(wǎng)上查詢(xún)，今后自己將更努力學(xué)習(xí)這門(mén)語(yǔ)言，多接觸解決各種問(wèn)題的各種算法，這樣才能提高自己。 6 致謝 非常高興能和同學(xué)們一起在實(shí)驗(yàn)室做實(shí)驗(yàn)，感謝各位老師以及同學(xué)們對(duì)我的幫助，特別是老師循循善誘的教導(dǎo)和不拘一格的思路給予我無(wú)盡的啟迪；這次數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的每個(gè)實(shí)驗(yàn)細(xì)節(jié)和每個(gè)數(shù)據(jù)，都離不開(kāi)老師您的細(xì)心指導(dǎo)。在您們的幫助下讓我順利完成了這次課程設(shè)計(jì)。平時(shí)注重的理論知識(shí)多了些，造成我上機(jī)操作遇到了很多困難，但是老師和同學(xué)都很熱情的幫助我，在此我表示我誠(chéng)摯的謝意。 7 參考文獻(xiàn) [1]. 嚴(yán)蔚敏．?dāng)?shù)據(jù)結(jié)構(gòu)（Ｃ語(yǔ)言版）[M]．清華大學(xué)出版社 2008年11月 [2].

39、嚴(yán)蔚敏．?dāng)?shù)據(jù)結(jié)構(gòu)題集（Ｃ語(yǔ)言版）[M]．清華大學(xué)出版社 2008年11月 [3]. 何欽銘．?dāng)?shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)[M]．浙江大學(xué)出版社 2007年8月1 8 源程序 //daoyouzixunxitong70321.cpp: implementation of the daoyouzixunxitong70321 class. #include "StdAfx70321.h" #include "daoyouzixunxitong70321.h" int x[11]={0}; int P[NUM][NUM]; long int D[NUM];

40、 MGraph G; daoyouzixunxitong70321::~daoyouzixunxitong70321() { } void daoyouzixunxitong70321::main2() { int v0,v1; char ck; CreateUDN70321(NUM,11); //景點(diǎn)個(gè)數(shù)加1 //調(diào)用CreateUNM()函數(shù) do { ck=Menu70321();//調(diào)用Menu() switch(ck) { case '1': system("cls&q

41、uot;); narrate70321();//調(diào)用narrate函數(shù) printf("\n\n\t\tO(∩_∩)O 提示：輸入100退出此環(huán)節(jié)\n"); M:printf("\n\t\t請(qǐng)選擇起點(diǎn)景點(diǎn)(0～9)："); scanf("%d",&v0); if(v0==100)break; printf("\t\t請(qǐng)選擇終點(diǎn)景點(diǎn)(0～9)："); //景點(diǎn)編號(hào) scanf("%d",&v1); if(v0

42、>9||v1>9) { printf("\n\t\tO(∩_∩)O 請(qǐng)重新輸入v0,v1:\n"); goto M; } ShortestPath70321(v0); //調(diào)用ShortestPath()函數(shù) output70321(v0,v1); //調(diào)用output()函數(shù) goto M; break; case '2': search70321();//調(diào)用search()函數(shù) break; case '3': syst

43、em("cls"); narrate70321();//調(diào)用 narrate()函數(shù) x[0]=1; //此處必須為x[0]=1 實(shí)際為x[0]=true HaMiTonian70321(1); //調(diào)用哈密爾頓函數(shù) 遍歷應(yīng)該從第一個(gè)景點(diǎn)開(kāi)始?。。∪绻胍薷?，必須從HaMiTonian()和NextValue()內(nèi)部修改 printf("\n\n\t\t\t\t請(qǐng)按Enter繼續(xù)...\n"); getchar(); getchar(); b

44、reak; }; }while(ck!='e'); } void daoyouzixunxitong70321::CreateUDN70321(int v, int a) { int i,j; G.vexnum=v; G.arcnum=a; for(i=0;i<G.vexnum;++i) G.vex[i].number=i; G.vex[0].sight="教學(xué)主樓"; G.vex[0].description="學(xué)校領(lǐng)導(dǎo)， **** 辦公之地"; G.vex[1].sight

45、="足球場(chǎng)"; G.vex[1].description="寬闊,非常適合運(yùn)動(dòng)"; G.vex[2].sight="燈光籃球場(chǎng)"; G.vex[2].description="籃球運(yùn)動(dòng)的最佳活動(dòng)場(chǎng)所"; G.vex[3].sight="惠馨園"; G.vex[3].description="石家莊經(jīng)濟(jì)學(xué)院惠馨園一、二樓是學(xué)生餐飲中心，三樓是教職工餐飲中心，四樓是綜合辦公之地，五樓是文藝文化活動(dòng)中心"; G.vex[4].sight="實(shí)驗(yàn)樓&

46、quot;; G.vex[4].description="各專(zhuān)業(yè)試驗(yàn)的重要場(chǎng)地"; G.vex[5].sight="計(jì)算機(jī)實(shí)驗(yàn)室"; G.vex[5].description="計(jì)算機(jī)專(zhuān)業(yè)的實(shí)驗(yàn)實(shí)習(xí)場(chǎng)所"; G.vex[6].sight="地球科學(xué)博物館"; G.vex[6].description="里面有著名的不尋?？铸埢?quot;; G.vex[7].sight="學(xué)術(shù)報(bào)告廳"; G.vex[7].description="學(xué)術(shù)交流中心&

47、quot;; G.vex[8].sight="圖書(shū)館"; G.vex[8].description="圖書(shū)館是莘莘學(xué)子學(xué)習(xí)的園地，里面有各科資料，每人可以任借五本書(shū)"; G.vex[9].sight="噴泉"; G.vex[9].description="學(xué)校的盛大節(jié)日時(shí)就可以看見(jiàn)"; for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j) G.arcs[i][j].adj=Max; G.arcs[0][1].adj=G.a

48、rcs[1][0].adj=50; G.arcs[0][9].adj=G.arcs[9][0].adj=50; G.arcs[1][2].adj=G.arcs[2][1].adj=50; G.arcs[2][3].adj=G.arcs[3][2].adj=130; G.arcs[3][4].adj=G.arcs[4][3].adj=300; G.arcs[0][5].adj=G.arcs[5][0].adj=50; G.arcs[2][5].adj=G.arcs[5][2].adj=100; G.arcs[0][6].adj=G.arcs[6][0].

49、adj=250; G.arcs[6][7].adj=G.arcs[7][6].adj=50; G.arcs[4][9].adj=G.arcs[9][4].adj=500; G.arcs[5][6].adj=G.arcs[6][5].adj=300; G.arcs[5][8].adj=G.arcs[8][5].adj=300; G.arcs[7][8].adj=G.arcs[8][7].adj=50; G.arcs[7][9].adj=G.arcs[9][7].adj=100; } void daoyouzixunxitong70321::narra

50、te70321() { int i,k=0; printf("\n\t\t***************歡 迎 使 用 校 園 導(dǎo) 游 程 序*************\n"); printf("\n\t\t******************石**家**莊**經(jīng)**濟(jì)**學(xué)**院**********************\n"); printf("\n\t\t制作者： 信息工程學(xué)院 1 顏建學(xué) !!!歡迎您使用!!!\n"); printf("\n\t\t_____

51、_____________________________________________________________\n"); printf("\t\t\t\t\t 景點(diǎn)名稱(chēng)\t\t\n"); printf("\t\t__________________________________________________________________\n"); for(i=0;i<NUM;i++) { printf("\t\t 【%2d】%-15s\t\t",i,G.vex[i].sigh

52、t); if(i%2==((NUM-1)%2))printf("\n");//奇數(shù)編號(hào)景點(diǎn)在右邊，偶數(shù)編號(hào)景點(diǎn)在左邊 k=k+1; } printf("\t\t_________________________________________________________________\n"); } void daoyouzixunxitong70321::ShortestPath70321(int num) { int v,w,i,t; int final[NUM]; int min; for(v=0

53、;v<NUM;v++) { final[v]=0; D[v]=G.arcs[num][v].adj; for(w=0;w<NUM;w++) P[v][w]=0; if(D[v]<20000) { P[v][num]=1; P[v][v]=1; } } D[num]=0; final[num]=1; for(i=0;i<NUM;++i) { min=Max; for(w=0;w<NUM;++w) if(!fi

54、nal[w]) if(D[w]<min) { v=w; min=D[w]; } final[v]=1; for(w=0;w<NUM;++w) if(!final[w]&&((min+G.arcs[v][w].adj)<D[w])) { D[w]=min+G.arcs[v][w].adj; for(t=0;t<NUM;t++) P[w][t]=P[v][t]; P[w][w]=1;

55、 } } } void daoyouzixunxitong70321::output70321(int sight1, int sight2) { int a,b,c,d,q=0; a=sight2; if(a!=sight1) { printf("\n\t\t\t從( %s )到( %s )的最短路徑是:\n\n",G.vex[sight1].sight,G.vex[sight2].sight); printf("\t\t\t%s",G.vex[sight1].sight);

56、 d=sight1; for(c=0;c<NUM;++c) { gate:; P[a][sight1]=0; for(b=0;b<NUM;b++) { if(G.arcs[d][b].adj<20000&&P[a][b]) { printf("-->%s",G.vex[b].sight); q=q+1; P[a][b]=0; d=b; if(q%10==0) printf("\n");

57、 goto gate; } } } printf("\t(最短距離為 %dm.)\n\t",D[a]); } } char daoyouzixunxitong70321::Menu70321() { char c; int flag; do{ flag=1; system("cls"); narrate70321(); //調(diào)用 narrate()函數(shù) printf("\n"); printf("\t\t\t┏━

58、━━━━━━━━━━━━━━━┓\n"); printf("\t\t\t┃ 【1】查詢(xún)景點(diǎn)路徑 ┃\n"); printf("\t\t\t┃ 【2】查詢(xún)景點(diǎn)信息 ┃\n"); printf("\t\t\t┃ 【3】推薦參觀路線(xiàn) ┃\n"); printf("\t\t\t┃ 【e】退出 ┃\n"); printf("\t\t\t┗━━━━━━━━━━

59、━━━━━━┛\n"); printf("\t\t\t\t請(qǐng)輸入您的選擇："); scanf("%c",&c); if(c=='1'||c=='2'||c=='3'||c=='e') flag=0; }while(flag); return c; } void daoyouzixunxitong70321::search70321() { int num; int i; char c; char name[20];

60、 char a[4]="100"; do { system("cls"); c=SearchMenu70321(); //調(diào)用SearchMenu()函數(shù) switch (c) { case '1': system("cls"); narrate70321(); //調(diào)用 narrate()函數(shù) printf("\n\t\t\tO(∩_∩)O提示：輸入100退出此環(huán)節(jié)\n"); N: printf("\n

61、\t\t請(qǐng)輸入您要查找的景點(diǎn)編號(hào)："); scanf("%d",&num); if(num!=100) { for(i=0;i<NUM;i++) { if(num==G.vex[i].number) { printf("\n\t\t您要查找景點(diǎn)信息如下:"); printf("\n\n\t\t\t%-25s\n",G.vex[i].description); break; }//if語(yǔ)句

62、 }//for語(yǔ)句 if(i==NUM) { printf("\n\t\t\t!!!沒(méi)*有*找*到!!!\n"); }//if語(yǔ)句 goto N; }//if語(yǔ)句 break; case '2': system("cls"); narrate70321(); //調(diào)用 narrate()函數(shù) printf("\n\t\t\tO(∩_∩)O提示：輸入100退出此環(huán)節(jié)\n"); S:printf("\

63、n\t\t請(qǐng)輸入您要查找的景點(diǎn)名稱(chēng)："); scanf("%s",name); if(!strcmp(name,a))break; for(i=0;i<NUM;i++) { if(!strcmp(name,G.vex[i].sight)) { printf("\n\t\t您要查找景點(diǎn)信息如下:"); printf("\n\n\t\t\t%-25s\n",G.vex[i].description); break; }//if語(yǔ)句 }//f

64、or語(yǔ)句 if(i==NUM) { printf("\n\t\t\t!!!沒(méi)*有*找*到!!!\n"); }//if語(yǔ)句 goto S; break; }//switch語(yǔ)句 }while(c!='e');//do while 語(yǔ)句 } char daoyouzixunxitong70321::SearchMenu70321() { char c; int flag; do{ flag=1; system("cls"); narrate70321();

65、 //調(diào)用 narrate()函數(shù) printf("\n"); printf("\t\t\t┏━━━━━━━━━━━━━━━━┓\n"); printf("\t\t\t┃ 【1】按照景點(diǎn)編號(hào)查詢(xún) ┃\n"); printf("\t\t\t┃ 【2】按照景點(diǎn)名稱(chēng)查詢(xún) ┃\n"); printf("\t\t\t┃ 【e】返回 ┃\n"); printf("\t\t\t

66、┗━━━━━━━━━━━━━━━━┛\n"); printf("\t\t\t\t請(qǐng)輸入您的選擇："); scanf("%c",&c); if(c=='1'||c=='2'||c=='e') flag=0; }while(flag); return c; } void daoyouzixunxitong70321::HaMiTonian70321(int m) { if(m>10) return; L: NextValue7032

67、1(m);//調(diào)用NextValue()函數(shù) if(x[m]==0) return; if(m==9&&G.arcs[0][x[10]-1].adj!=20000)//景點(diǎn)個(gè)數(shù)減1 景點(diǎn)個(gè)數(shù)加1 display70321();//調(diào)用display()函數(shù) else HaMiTonian70321(m+1);//調(diào)用HaMiTonian()函數(shù) goto L; } void daoyouzixunxitong70321::NextValue70321(int k) { int j

68、; l:x[k]=(x[k]+1)%11;//景點(diǎn)個(gè)數(shù)加1 if(x[k]==0) return; if(G.arcs[x[k-1]-1][x[k]-1].adj!=20000) { for(j=0;j<k;j++) if(x[j]==x[k]) goto l; return; } else goto l; } void daoyouzixunxitong70321::display70321() { int i=0; prin

69、tf("\n\n"); for(i=0;i<10;i++) // 景點(diǎn)個(gè)數(shù) printf("%s->",G.vex[x[i]-1].sight); printf("校園出口"); printf("\n"); } // 課程設(shè)計(jì).cpp : Defines the entry point for the console application. // #include "StdAfx70321.h" #include "daoyouzix

70、unxitong70321.h" #define Max 20000 #define NUM 10 //景點(diǎn)個(gè)數(shù) int main(int argc, char* argv[]) { daoyouzixunxitong70321 A; system("color 5f");//屬于stdio.h system("mode con: cols=100 lines=100");//屬于stdio.h A.main2(); return 0; } // daoyouzixunxitong70

71、321.h: interface for the daoyouzixunxitong70321 class. #if !defined(AFX_DAOYOUZIXUNXITONG70321_H__C0CBBABA_ED55_44AF_AEBF_FA64A9__INCLUDED_) #define AFX_DAOYOUZIXUNXITONG70321_H__C0CBBABA_ED55_44AF_AEBF_FA64A9__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include "stdio.h" #include "stdlib.h" #include "string.h" #define Max 20000 #define NUM 10 typedef struct ArcCell { int adj; }ArcCell; typedef struct VertexType { int number