校園導(dǎo)游咨詢系統(tǒng)---數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(共35頁)

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

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

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

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

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

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

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

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

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

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

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

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

12、e vex[NUM]; /* 圖中的頂點，即為景點 */ ArcCell arcs[NUM][NUM]; /* 圖中的邊，即為景點間的距離 */ int vexnum,arcnum; /* 頂點數(shù)，邊數(shù) */ }MGraph; /* 定義圖的類型 2、該程序的算法如下： 1)void CreateUDN70321(MGraph&G) /* 造圖函數(shù) */ { //采用鄰接矩陣表示法，構(gòu)造無向網(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)造頂點向量 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);//輸入一條邊依附的頂點及權(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>的對稱弧<v2,v1> } Return OK; } 2)void narrate70321() /* 說明函數(shù) */ { k=0; printf("\n\t\t***************歡 迎 使 用 校 園 導(dǎo) 游 程 序*************\n"); printf

15、("\n\t\t*******************石**家**莊**經(jīng)**濟**學(xué)**院************************\n"); printf("\n\t\t制作者： 信息工程學(xué)院 1 顏建學(xué) ?。?！歡迎您使用?。?！\n"); printf("\n\t\t__________________________________________________________________\n"); printf("\t\t\t\t\t 景點名稱\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ù)編號景點在右邊，偶數(shù)編號景點在左邊 k=k+1; } printf("\t\t______________

17、___________________________________________________\n"); } 3) void ShortestPath70321(int num) { //用迪杰斯特拉算法求G的v0頂點到其余頂點的最短路徑P[v]及其帶權(quán)長度 D[v] //若P[v][w]為TRUE,則 w是從v0到v當(dāng)前求得最短路徑上的頂點 //final[v]為TRUE當(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; //開始主循環(huán)，每次求得v0到某個頂點的最短路徑，并加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) /* 如果景點二不和景點一輸入重合，則進行... */ { printf(從G.vex[sight1].sight到G.vex[sight2].sight的最短路徑是:);/* 輸出提示信息 */ printf(D[a]); /* 輸出sight1到sight2的最短路徑長度，存放在D[]數(shù)組中 */ printf(G.vex[sight1].sight); /* 輸出景點一的名稱 */ d=sight1; /* 將景點一的編號賦值給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]) /* 如果景點一和它的一個臨界點之間存在路徑且最短路徑 */ { printf(G.vex[b].sight); /* 輸出此節(jié)點的名稱 */ q=q+1; /* 計數(shù)變量加一，滿8控制輸出時的換行 */ P[a][b]=0;

22、 d=b; /* 將b作為出發(fā)點進行下一次循環(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); /* 計

23、算兩個景點之間的最短路徑 */ 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() /* 查詢子菜單 */ { do { flag=1; narrate70321(); scanf(&c); if(c=

25、='1'||c=='2'||c=='e') flag=0; }while(flag); return c; } 8) void search70321() /* 查詢景點信息 */ { 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(沒有找到！"); 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(沒有找到！"); } break; } }while(SearchMenu()!='e'); } 3、流程圖如下： 開始 造圖 輸入您的選擇 您的選擇是1？ 您的選擇是2？ 您的選擇是3？ 您的選擇是100？ 結(jié)束 輸入您的第一個景點選擇 輸入您的第二個景點選擇 您的選擇是e？

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

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

30、3 按100推出此環(huán)節(jié)，當(dāng)在選擇主菜單選擇2時，出現(xiàn)如下圖4所示子菜單： 圖4 當(dāng)輸入1時，則按景點編號查詢，當(dāng)輸入6（地球科學(xué)博物館）時，屏幕上打印出此景點信息：里面有著名的不尋常恐龍化石；當(dāng)輸入4（實驗樓）時，屏幕上打印出此景點信息：各專業(yè)實驗的重要場地；當(dāng)輸入12時，此景點不存在，屏幕上顯示：！??！沒*有*找*到?。。?；當(dāng)輸入20時，此景點不存在，屏幕上顯示：?。。]*有*找*到?。?！。如下圖5所示： 圖5 當(dāng)輸入2時，則按景點名稱查詢，當(dāng)輸入“圖書館”時，

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

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

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

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

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

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

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

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

39、嚴蔚敏．?dāng)?shù)據(jù)結(jié)構(gòu)題集（Ｃ語言版）[M]．清華大學(xué)出版社 2008年11月 [3]. 何欽銘．?dāng)?shù)據(jù)結(jié)構(gòu)課程設(shè)計[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); //景點個數(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請選擇起點景點(0～9)："); scanf("%d",&v0); if(v0==100)break; printf("\t\t請選擇終點景點(0～9)："); //景點編號 scanf("%d",&v1); if(v0

42、>9||v1>9) { printf("\n\t\tO(∩_∩)O 請重新輸入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 實際為x[0]=true HaMiTonian70321(1); //調(diào)用哈密爾頓函數(shù) 遍歷應(yīng)該從第一個景點開始！??！如果想要修改，必須從HaMiTonian()和NextValue()內(nèi)部修改 printf("\n\n\t\t\t\t請按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、="足球場"; G.vex[1].description="寬闊,非常適合運動"; G.vex[2].sight="燈光籃球場"; G.vex[2].description="籃球運動的最佳活動場所"; G.vex[3].sight="惠馨園"; G.vex[3].description="石家莊經(jīng)濟學(xué)院惠馨園一、二樓是學(xué)生餐飲中心，三樓是教職工餐飲中心，四樓是綜合辦公之地，五樓是文藝文化活動中心"; G.vex[4].sight="實驗樓&

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

47、quot;; G.vex[8].sight="圖書館"; G.vex[8].description="圖書館是莘莘學(xué)子學(xué)習(xí)的園地，里面有各科資料，每人可以任借五本書"; G.vex[9].sight="噴泉"; G.vex[9].description="學(xué)校的盛大節(jié)日時就可以看見"; 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)**濟**學(xué)**院**********************\n"); printf("\n\t\t制作者： 信息工程學(xué)院 1 顏建學(xué) !!!歡迎您使用!!!\n"); printf("\n\t\t_____

51、_____________________________________________________________\n"); printf("\t\t\t\t\t 景點名稱\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ù)編號景點在右邊，偶數(shù)編號景點在左邊 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】查詢景點路徑 ┃\n"); printf("\t\t\t┃ 【2】查詢景點信息 ┃\n"); printf("\t\t\t┃ 【3】推薦參觀路線 ┃\n"); printf("\t\t\t┃ 【e】退出 ┃\n"); printf("\t\t\t┗━━━━━━━━━━

59、━━━━━━┛\n"); printf("\t\t\t\t請輸入您的選擇："); 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請輸入您要查找的景點編號："); scanf("%d",&num); if(num!=100) { for(i=0;i<NUM;i++) { if(num==G.vex[i].number) { printf("\n\t\t您要查找景點信息如下:"); printf("\n\n\t\t\t%-25s\n",G.vex[i].description); break; }//if語句

62、 }//for語句 if(i==NUM) { printf("\n\t\t\t!!!沒*有*找*到!!!\n"); }//if語句 goto N; }//if語句 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請輸入您要查找的景點名稱："); 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您要查找景點信息如下:"); printf("\n\n\t\t\t%-25s\n",G.vex[i].description); break; }//if語句 }//f

64、or語句 if(i==NUM) { printf("\n\t\t\t!!!沒*有*找*到!!!\n"); }//if語句 goto S; break; }//switch語句 }while(c!='e');//do while 語句 } 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】按照景點編號查詢 ┃\n"); printf("\t\t\t┃ 【2】按照景點名稱查詢 ┃\n"); printf("\t\t\t┃ 【e】返回 ┃\n"); printf("\t\t\t

66、┗━━━━━━━━━━━━━━━━┛\n"); printf("\t\t\t\t請輸入您的選擇："); 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)//景點個數(shù)減1 景點個數(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;//景點個數(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++) // 景點個數(shù) printf("%s->",G.vex[x[i]-1].sight); printf("校園出口"); printf("\n"); } // 課程設(shè)計.cpp : Defines the entry point for the console application. // #include "StdAfx70321.h" #include "daoyouzix

70、unxitong70321.h" #define Max 20000 #define NUM 10 //景點個數(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