數(shù)據(jù)結(jié)構(gòu)與OOP景區(qū)旅游信息管理系統(tǒng)-

1、精品文檔/*15、景區(qū)旅游信息管理系統(tǒng)【問題描述】在旅游景區(qū)， 經(jīng)常會遇到游客打聽從一個景點到另一個景點的最短路徑和最短距離， 這類游客不喜歡按照導(dǎo)游圖的線路來游覽， 而是挑選自己感興趣的景點游覽。 為于幫助這類游客信息查詢， 就需要計算出所有景點之間最短路徑和最短距離。 算法采用迪杰斯特拉算法或弗洛伊德算法均可。 建立一個景區(qū)旅游信息管理系統(tǒng)， 實現(xiàn)的主要功能包括制訂旅游景點導(dǎo)游線路策略和制訂景區(qū)道路鋪設(shè)策略。任務(wù)中景點分布是一個無向帶權(quán)連通圖，圖中邊的權(quán)值是景點之間的距離。（ 1）景區(qū)旅游信息管理系統(tǒng)中制訂旅游景點導(dǎo)游線路策略，首先通過遍歷景點，給出一個入口景點， 建立一個導(dǎo)游線路圖， 導(dǎo)

2、游線路圖用有向圖表示。 遍歷采用深度優(yōu)先策略，這也比較符合游客心理。（ 2）為了使導(dǎo)游線路圖能夠優(yōu)化，可通過拓樸排序判斷圖中有無回路，若有回路，則打印輸出回路中的景點，供人工優(yōu)化。（ 3）在導(dǎo)游線路圖中，還為一些不愿按線路走的游客提供信息服務(wù)，比如從一個景點到另一個景點的最短路徑和最短距離。在本線路圖中將輸出任意景點間的最短路徑和最短距離。（ 4）在景區(qū)建設(shè)中，道路建設(shè)是其中一個重要內(nèi)容。道路建設(shè)首先要保證能連通所有景點，但又要花最小的代價，可以通過求最小生成樹（ prime ，克魯斯卡爾）來解決這個問題。本任務(wù)中假設(shè)修建道路的代價只與它的里程相關(guān)。【基本要求】本任務(wù)應(yīng)有如下功能模塊：創(chuàng)建景區(qū)

3、景點分布圖；輸出景區(qū)景點分布圖（鄰接矩陣）輸出導(dǎo)游線路圖；深度優(yōu)先策略判斷導(dǎo)游線路圖有無回路；拓樸排序（查找入度大于1 的景點）求兩個景點間的最短路徑和最短距離；弗洛伊德算法輸出道路修建規(guī)劃圖。 prime主程序用菜單選項供用戶選擇功能模塊。*/論文內(nèi)容包括：1、 課程設(shè)計題目：2、 課程設(shè)計內(nèi)容：3、 算法設(shè)計：4、 程序正確性驗證（指邊界測試數(shù)據(jù)，即程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果）：5、 課程設(shè)計過程中出現(xiàn)的主要問題、原因及解決方法：6、 課程設(shè)計的主要收獲：5歡迎下載。7、 對今后課程設(shè)計的建議:/代碼：#include <iostre

4、am>using namespace std;#include<conio.h>getch#include<cstdlib>清屏函數(shù)頭文件#define M 100#define INF 999666333/*函數(shù)聲明*/ void Welcome。;/歡迎界面void returnMainFace();/返回主界面函數(shù)void MainFace();/ 主界面 void create_graph();/ 創(chuàng)建景區(qū)景點圖 void print_graph();/ 輸出景區(qū)景點圖 void guide_line();/導(dǎo)游線路void DFS(int c);/深度優(yōu)

5、先搜索導(dǎo)游線路void checked。，檢查是否存在一個合法的景區(qū)景點分布圖void Num_Name();/ 打印景點編號與景點名稱的對應(yīng)信息 void Floyd(int AMM,int pathMM);/Floyd算法void Y_N();/選項判斷函數(shù)void check_circuit();/ 判斷回路/*定義數(shù)據(jù)結(jié)構(gòu)*/ struct Matrixint mMM;/景點鄰接矩陣string PnameM;/各個景點的名稱;typedef struct string Sname;/ 景區(qū)名稱int count;/景點總數(shù)量int edge;/道路數(shù)量Matrix mat;/ 鄰接矩

6、陣 Scenic;/*景區(qū)數(shù)據(jù)類型為全局變量*/_O2歡迎下載Scenic S;/*/ 創(chuàng)建一個景區(qū)鄰接矩陣void create_graph()if(S.count>0)cout<<"n* 當(dāng)前已存在一個景區(qū)景點分布圖！ n* 繼續(xù)操作將覆蓋該景區(qū)景點分布 圖！ ( Y/N ) "Y_N();cout<<"n* 請輸入景區(qū)的名稱： "cin>>S.Sname;cout<<"n* 請輸入該景區(qū)的景點總數(shù)目： "cin>>S.count;cout<<"

7、;n* 請輸入景區(qū)的道路總數(shù)目： "cin>>S.edge;int i,j;for(i=0;i<S.count;i+)for(j=0;j<S.count;j+)S.mat.mij=0;cout<<"n* 請輸入道路兩邊連接的兩個景點編號、名稱及道路的長度n"cout<<"t (格式：景點輸入請按照小號在前大號在后的原則，景點編號從1 開始)for(i=0;i<S.edge;i+)cout<<"n* 第 "<<i+1<<" 條道路 n&q

8、uot;int n1,n2;/ 編號輸入從1 開始，矩陣下標(biāo)從零開始cout<<"t- 景點 1 編號： "cin>>n1;n1-;cout<<"t-景點1 名稱："cin>>S.mat.Pnamen1;cout<<"t-景點2 編號："cin>>n2;n2-;cout<<"t- 景點 2 名稱： "cin>>S.mat.Pnamen2;cout<<"t-兩景點之間的道路長度："cin&g

9、t;>S.mat.mn1n2;S.mat.mn2n1=S.mat.mn1n2;)cout<<"n*景區(qū)創(chuàng)建成功！"returnMainFace();)void print_graph()/以鄰接矩陣的形式輸出景點分布checked();cout<<"n*景區(qū)景點分布圖(鄰接矩陣表示)查詢成功！ n"cout<<"* 景區(qū)名稱："<<S.Sname<<endl;int i,j;cout<<"nt "for(i=0;i<S.count;

10、i+)cout<<"-")cout<<endl;cout<<"t| 編號 |"/cout<<" |"for(i=0;i<S.count;i+)cout<<' '<<i+1<<' ')cout<<T<<endl<<"t|"for(i=0;i<S.count;i+)cout<<"-")cout<<'|

11、9;<<endl;for(i=0;i<S.count;i+)for(j=0;j<S.count;j+)if(j=0)cout<<"t| "<<i+1<<" | "<<S.mat.mij<<' ')elsecout<<' '<<S.mat.mij<<''_ 。4歡迎下載精品文檔7歡迎下載。cout<<'|'<<endl;cout<<&quo

12、t;t "for(i=0;i<S.count;i+)cout<<"-"Num_Name();或景點到自身路徑不需要！cout<<" 注： nt'0' 表示兩個景點間沒有直接到達(dá)的路徑，n"returnMainFace(); /*/ 深度優(yōu)先搜索導(dǎo)游線路int visitedM=0;int np=0;/找到的景點個數(shù)int pM;/表示各個景點的入度值void DFS(int c)np+;pc+;if(np=S.count)cout<<S.mat.Pnamec<<endl;re

13、turnMainFace();elsecout<<S.mat.Pnamec<<" -> "visitedc=1;for(int i=0;i<S.count;i+)if(S.mat.mci>0&&visitedi=0) DFS(i);if(S.count>np)cout<<S.mat.Pnamec<<"->" pc+;if(np=S.count)returnMainFace(); void guide_line()/ 導(dǎo)游線路 checked();cout<

14、<"n* 請輸入起始景點的景點編號：int c;cin>>c;c-;for(int i=0;i<S.count;i+)visitedi=0;pi=0;/ 入度置初值為 0np=0;nnt"cout<<"* 形成的導(dǎo)游線路圖(采用深度優(yōu)先策略)如下所示：DFS(c);/*/ void check_circuit()/ 判斷回路checked();if(np=0)cout<<"n* 缺少合法的導(dǎo)游線路圖！ n* 請先生成一個合法的導(dǎo)游線路圖！ n" returnMainFace();bool f=tr

15、ue;for(int i=0;i<S.count;i+)if(pi>1)if(f)cout<<"n*該導(dǎo)游線路圖存在回路 n 線路中的重復(fù)走過的景點顯示如下：nt"f=false;cout<<" 編號： "<<i+1<<"， "<<" 景點名稱： "<<S.mat.Pnamei<<endl;if(f)精品文檔cout<<"nt* 未找到存在于該導(dǎo)游線路圖中的回路。 n"returnMain

16、Face();void Floyd(int AMM,int pathMM)int i,j,k;for(i=0;i<S.count;i+)for(j=0;j<S.count;j+)if(S.mat.mij=0&&i!=j)Aij=INF;else if(i=j)Aij=0;elseAij=S.mat.mij;if(i!=j&&S.mat.mij<INF)pathij=i;elsepathij=-1;/*for(i=0;i<S.count;i+)for(j=0;j<S.count;j+)cout<<pathij<<

17、;' 'cout<<endl;*/for(k=0;k<S.count;k+)for(i=0;i<S.count;i+)for(j=0;j<S.count;j+)if(Aij>Aik+Akj)Aij=Aik+Akj;。 pathij=pathkj;/*for(i=0;i<S.count;i+)for(j=0;j<S.count;j+)cout<<pathij<<' 'cout<<endl;*/*/ void min_distance()/ 最短路徑、距離checked();/int

18、 AMM,pathMM;int pathMM;int AMM;Floyd(A,path);/Dispathwhile(true)system("cls");Num_Name();int i,j,k,s;int apathM,d;cout<<"* 請輸入要查詢的最短路徑和最短距離的兩個景點的編號： n"cout<<"t- 景點 1 ： "cin>>i;i-;cout<<"t- 景點 2 ： "cin>>j;j-;if(Aij<INF&&

19、i!=j)cout<<"n*從 "<<S.mat.Pnamei<<" 到 "<<S.mat.Pnamej<<" 的最短路徑為： "k=pathij;d=0;apathd=j;while(k!=-1&&k!=i)d+;apathd=k;k=pathik;d+;apathd=i;cout<<S.mat.Pnameapathd;/cout<<apathd;for(s=d-1;s>=0;s-)cout<<" ->

20、; "<<S.mat.Pnameapaths;/cout<<','<<apaths;cout<<" ，最短距離為： "<<Aij<<endl;else if(i=j)cout<<"n* 景點編號輸入不合法！ n"elsecout<<"n*這兩個景點間不存在路徑n"cout<<"n 是否繼續(xù)執(zhí)行最短路徑和最短距離的查詢( Y/N ) "Y_N();returnMainFace(); v

21、oid build_road()/ 道路修建規(guī)劃圖、最小生成樹( prime 算法)/Primchecked();cout<<"n* 道路修建規(guī)劃圖( prime 算法)規(guī)劃如下： n"int lowcostM,min,closestM,i,j,k,v=0,sum=0,num=0;int AMM;for(i=0;i<S.count;i+)for(j=0;j<S.count;j+)if(S.mat.mij=0&&i!=j)Aij=INF;else if(i=j)11歡迎下載。精品文檔Aij=0;elseAij=S.mat.mij;for

22、(i=0;i<S.count;i+)lowcosti=Avi;closesti=v;for(i=1;i<S.count;i+)min=INF;for(j=0;j<S.count;j+)if(lowcostj!=0&&lowcostj<min) min=lowcostj; k=j;if(min<INF)cout<<"t-第 "<<+num<<" 條路：從 "<<S.mat.Pnameclosestk<<" 到"<<S.m

23、at.Pnamek<<" ，該條道路長度為： "<<min<<endl; sum+=min; lowcostk=0; for(j=0;j<S.count;j+) if(Akj!=0&&Akj<lowcostj)lowcostj=Akj;closestj=k;cout<<"* 修建道路的總長度為： "<<sum<<endl;returnMainFace();void MainFace()/ 主界面system("cls");# 歡迎下。精

24、品文檔11歡迎下。cout<<"n 主菜單： n"cout<<"t1 、創(chuàng)建景區(qū)景點分布圖； n"cout<<"t2 、輸出景區(qū)景點分布圖（鄰接矩陣） ； n"cout<<"t3 、輸出導(dǎo)游線路圖； n"cout<<"t4 、判斷導(dǎo)游線路圖有無回路； n"cout<<"t5 、求兩個景點間的最短路徑和最短距離； n"cout<<"t6 、輸出道路修建規(guī)劃圖； n"cout&

25、lt;<"t0 、退出。 n"cout<<"n* 請輸入操作選擇： "char c;c=getch();cout<<c<<endl;while(!(c>='0'&&c<='6')cout<<"* 輸入有誤，請重新輸入：請重新輸入:c=getch();cout<<c<<endl;switch(c)case '1':create_graph();break;case '2':print_graph();break;case '3':guide_line();break;/case '4':check_circuit();break;/case '5':min_distance();break;/case '6':build_road();break;/case '0':cout<