數(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ū)景點分布圖；輸出景區(qū)景點分布圖（鄰接矩陣

3、）輸出導(dǎo)游線路圖；深度優(yōu)先策略判斷導(dǎo)游線路圖有無回路；拓樸排序（查找入度大于1的景點）求兩個景點間的最短路徑和最短距離；弗洛伊德算法輸出道路修建規(guī)劃圖。prime主程序用菜單選項供用戶選擇功能模塊。*/論文內(nèi)容包括：一、          課程設(shè)計題目：二、          課程設(shè)計內(nèi)容：三、          算法設(shè)計：四、

4、        程序正確性驗證（指邊界測試數(shù)據(jù)，即程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果）：五、          課程設(shè)計過程中出現(xiàn)的主要問題、原因及解決方法：六、          課程設(shè)計的主要收獲：七、       

5、0;  對今后課程設(shè)計的建議：/代碼：#include <iostream>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

6、 guide_line();/導(dǎo)游線路void DFS(int c);/深度優(yōu)先搜索導(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 Matrix int mMM;/景點鄰接矩陣 string PnameM;/各個景點的名稱;typedef struct string Sname;/景區(qū)名稱 int cou

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

8、;S.count; cout<<"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*第 &qu

9、ot;<<i+1<<" 條道路n" int n1,n2; /編號輸入從1開始，矩陣下標從零開始 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

10、; cout<<"t-兩景點之間的道路長度：" cin>>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;

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

12、=0;i<S.count;i+) cout<<"-" cout<<'|'<<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<<' ' else cout<<' '<<S.mat.mij<<' &#

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

14、+; pc+; if(np=S.count) cout<<S.mat.Pnamec<<endl; returnMainFace(); else cout<<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(

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

16、<<"n*缺少合法的導(dǎo)游線路圖！n*請先生成一個合法的導(dǎo)游線路圖！n" returnMainFace(); bool f=true; 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

17、<<endl; if(f) cout<<"nt*未找到存在于該導(dǎo)游線路圖中的回路。n" returnMainFace();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; else Aij=S.mat.mij; if(i!=j&&S.mat.mij<INF) pathij=i; e

18、lse pathij=-1; /* for(i=0;i<S.count;i+) for(j=0;j<S.count;j+) cout<<pathij<<' ' 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+

19、) cout<<pathij<<' ' cout<<endl; */*/void min_distance()/最短路徑、距離 checked(); /int AMM,pathMM; int pathMM; int AMM; Floyd(A,path); /Dispath while(true) system("cls"); Num_Name(); int i,j,k,s; int apathM,d; cout<<"*請輸入要查詢的最短路徑和最短距離的兩個景點的編號：n" cout<&

20、lt;"t-景點 1：" cin>>i; i-; cout<<"t-景點 2：" cin>>j; j-; if(Aij<INF&&i!=j) cout<<"n*從 "<<S.mat.Pnamei<<" 到 "<<S.mat.Pnamej<<" 的最短路徑為：" k=pathij; d=0;apathd=j; while(k!=-1&&k!=i) d+;apathd

21、=k; k=pathik; d+;apathd=i; cout<<S.mat.Pnameapathd; /cout<<apathd; for(s=d-1;s>=0;s-) cout<<" -> "<<S.mat.Pnameapaths; /cout<<','<<apaths; cout<<" ，最短距離為："<<Aij<<endl; else if(i=j) cout<<"n*景點編號輸入不合法！n

22、" else cout<<"n*這兩個景點間不存在路徑n" cout<<"n是否繼續(xù)執(zhí)行最短路徑和最短距離的查詢（Y/N）" Y_N(); returnMainFace();void build_road()/道路修建規(guī)劃圖、最小生成樹（prime算法） /Prim checked(); 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&l

23、t;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; else Aij=S.mat.mij; for(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<IN

24、F) cout<<"t-第 "<<+num<<" 條路：從 "<<S.mat.Pnameclosestk<<" 到 "<<S.mat.Pnamek<<" ，該條道路長度為："<<min<<endl; sum+=min; lowcostk=0; for(j=0;j<S.count;j+) if(Akj!=0&&Akj<lowcostj) lowcostj=Akj; closestj=

25、k; cout<<"*修建道路的總長度為："<<sum<<endl; returnMainFace();void MainFace()/主界面 system("cls"); cout<<"n主菜單：n" cout<<"t1、創(chuàng)建景區(qū)景點分布圖；n" cout<<"t2、輸出景區(qū)景點分布圖（鄰接矩陣）；n" cout<<"t3、輸出導(dǎo)游線路圖；n" cout<<"t4、判斷

26、導(dǎo)游線路圖有無回路；n" cout<<"t5、求兩個景點間的最短路徑和最短距離；n" cout<<"t6、輸出道路修建規(guī)劃圖；n" cout<<"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;/導(dǎo)游線路 case '4': check_circuit();break;/判斷回路 case '5': min_d