數據結構與OOP景區(qū)旅游信息管理系統(tǒng)-

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

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

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

4、        程序正確性驗證（指邊界測試數據，即程序對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數據能夠得出滿足要求的結果）：五、          課程設計過程中出現的主要問題、原因及解決方法：六、          課程設計的主要收獲：七、       

5、0;  對今后課程設計的建議：/代碼：#include <iostream>using namespace std;#include<conio.h>/getch#include<cstdlib>/清屏函數頭文件#define M 100#define INF 999666333/*函數聲明*/void Welcome();/歡迎界面void returnMainFace();/返回主界面函數void MainFace();/主界面void create_graph();/創(chuàng)建景區(qū)景點圖void print_graph();/輸出景區(qū)景點圖void

6、 guide_line();/導游線路void DFS(int c);/深度優(yōu)先搜索導游線路void checked();/檢查是否存在一個合法的景區(qū)景點分布圖void Num_Name();/打印景點編號與景點名稱的對應信息void Floyd(int AMM,int pathMM);/Floyd算法void Y_N();/選項判斷函數void check_circuit();/判斷回路/*定義數據結構*/struct Matrix int mMM;/景點鄰接矩陣 string PnameM;/各個景點的名稱;typedef struct string Sname;/景區(qū)名稱 int cou

7、nt;/景點總數量 int edge;/道路數量 Matrix mat;/鄰接矩陣Scenic;/*景區(qū)數據類型為全局變量*/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ū)的景點總數目：" cin>>

8、;S.count; cout<<"n*請輸入景區(qū)的道路總數目：" 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)先搜索導游線路int visitedM=0;int np=0;/找到的景點個數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()/導游線路 checked(); cout<<"n*請輸入起始景點的景點編號：" int c; cin>>c; c-; for(int i=0;i<S.count;i+) visitedi=0; pi=0;/入度置初值為0 np=0; cout<<"*形成的導游線路圖（采用深度優(yōu)先策略）如下所示：nnt" DFS(c);/*/void check_circuit()/判斷回路 checked(); if(np=0) cout

16、<<"n*缺少合法的導游線路圖！n*請先生成一個合法的導游線路圖！n" returnMainFace(); bool f=true; for(int i=0;i<S.count;i+) if(pi>1) if(f) cout<<"n*該導游線路圖存在回路n線路中的重復走過的景點顯示如下：nt" f=false; cout<<"編號："<<i+1<<" ，"<<"景點名稱："<<S.mat.Pnamei

17、<<endl; if(f) cout<<"nt*未找到存在于該導游線路圖中的回路。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、輸出導游線路圖；n" cout<<"t4、判斷

26、導游線路圖有無回路；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;/導游線路 case '4': check_circuit();break;/判斷回路 case '5': min_d