数据结构与OOP景区旅游信息管理系统

/*15、景区旅游信息管理系统【问题描述】在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。 （1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略，这也比较符合游客心理。（2）为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。（3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。（4）在景区建设中，道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树（prime，克鲁斯卡尔）来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。【基本要求】本任务应有如下功能模块：创建景区景点分布图；输出景区景点分布图（邻接矩阵）输出导游线路图；深度优先策略判断导游线路图有无回路；拓朴排序（查找入度大于1的景点）求两个景点间的最短路径和最短距离；弗洛伊德算法输出道路修建规划图。prime主程序用菜单选项供用户选择功能模块。*/论文内容包括：一、 课程设计题目：二、 课程设计内容：三、 算法设计：四、程序正确性验证（指边界测试数据，即程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果）：五、 课程设计过程中出现的主要问题、原因及解决方法：六、 课程设计的主要收获：七、 对今后课程设计的建议：/代码：#include using namespace std;#include/getch#include/清屏函数头文件#define M 100#define INF /*函数声明*/void Welcome();/欢迎界面void returnMainFace();/返回主界面函数void MainFace();/主界面void create_graph();/创建景区景点图void print_graph();/输出景区景点图void guide_line();/导游线路void DFS(int c);/深度优先搜索导游线路void checked();/检查是否存在一个合法的景区景点分布图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;/景区名称 int count;/景点总数量 int edge;/道路数量 Matrix mat;/邻接矩阵Scenic;/*景区数据类型为全局变量*/Scenic S;/*/创建一个景区邻接矩阵void create_graph() if(S.count0) coutn*当前已存在一个景区景点分布图！n*继续操作将覆盖该景区景点分布图！（Y/N）; Y_N(); coutS.Sname; coutS.count; coutS.edge; int i,j; for(i=0;iS.count;i+) for(j=0;jS.count;j+) S.mat.mij=0; coutn*请输入道路两边连接的两个景点编号、名称及道路的长度n; coutt（格式：景点输入请按照小号在前大号在后的原则，景点编号从1开始）; for(i=0;iS.edge;i+) coutn*第 i+1 条道路n; int n1,n2; /编号输入从1开始，矩阵下标从零开始 coutn1; n1-; coutS.mat.Pnamen1; coutn2; n2-; coutS.mat.Pnamen2; coutS.mat.mn1n2; S.mat.mn2n1=S.mat.mn1n2; coutn*景区创建成功！; returnMainFace();void print_graph()/以邻接矩阵的形式输出景点分布 checked(); coutn*景区景点分布图（邻接矩阵表示）查询成功！n; cout*景区名称：S.Snameendl; int i,j; coutnt -; for(i=0;iS.count;i+) cout-; coutendl; coutt|编号|; /cout | for(i=0;iS.count;i+) cout i+1 ; cout|endlt|-; for(i=0;iS.count;i+) cout-; cout|endl; for(i=0;iS.count;i+) for(j=0;jS.count;j+) if(j=0) coutt| i+1 | S.mat.mij ; else cout S.mat.mij ; cout|endl; coutt -; for(i=0;iS.count;i+) cout-; Num_Name(); cout注：nt0表示两个景点间没有直接到达的路径，或景点到自身路径不需要！n; returnMainFace();/*/深度优先搜索导游线路int visitedM=0;int np=0;/找到的景点个数int pM;/表示各个景点的入度值void DFS(int c) np+; pc+; if(np=S.count) coutS.mat.Pnamecendl; returnMainFace(); else coutS.mat.Pnamec ; visitedc=1; for(int i=0;i0&visitedi=0) DFS(i); if(S.countnp) coutS.mat.Pnamec; pc+; if(np=S.count)returnMainFace();void guide_line()/导游线路 checked(); coutc; c-; for(int i=0;iS.count;i+) visitedi=0; pi=0;/入度置初值为0 np=0; cout*形成的导游线路图（采用深度优先策略）如下所示：nnt; DFS(c);/*/void check_circuit()/判断回路 checked(); if(np=0) coutn*缺少合法的导游线路图！n*请先生成一个合法的导游线路图！n; returnMainFace(); bool f=true; for(int i=0;i1) if(f) coutn*该导游线路图存在回路n线路中的重复走过的景点显示如下：nt; f=false; cout编号：i+1 ，景点名称：S.mat.Pnameiendl; if(f) coutnt*未找到存在于该导游线路图中的回路。n; returnMainFace();void Floyd(int AMM,int pathMM) int i,j,k; for(i=0;iS.count;i+) for(j=0;jS.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.mijINF) pathij=i; else pathij=-1; /* for(i=0;iS.count;i+) for(j=0;jS.count;j+) coutpathij ; coutendl; */ for(k=0;kS.count;k+) for(i=0;iS.count;i+) for(j=0;jAik+Akj) Aij=Aik+Akj; pathij=pathkj; /* for(i=0;iS.count;i+) for(j=0;jS.count;j+) coutpathij ; coutendl; */*/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; couti; i-; coutj; j-; if(AijINF&i!=j) coutn*从 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; coutS.mat.Pnameapathd; /cout=0;s-) cout S.mat.Pnameapaths; /cout,apaths; cout ，最短距离为：Aijendl; else if(i=j) coutn*景点编号输入不合法！n; else coutn*这两个景点间不存在路径n; coutn是否继续执行最短路径和最短距离的查询（Y/N）; Y_N(); returnMainFace();void build_road()/道路修建规划图、最小生成树（prime算法） /Prim checked(); coutn*道路修建规划图（prime算法）规划如下：n; int lowcostM,min,closestM,i,j,k,v=0,sum=0,num=0; int AMM; for(i=0;iS.count;i+) for(j=0;jS.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;iS.count;i+) lowcosti=Avi; closesti=v; for(i=1;iS.count;i+) min=INF; for(j=0;jS.count;j+) if(lowcostj!=0&lowcostjmin) min=lowcostj; k=j; if(minINF) coutt-第 +num 条路：从 S.mat.Pnameclosestk 到 S.mat.Pnamek ，该条道路长度为：minendl; sum+=min; lowcostk=0; for(j=0;jS.count;j+) if(Akj!=0&Akjlowcostj) lowcostj=Akj; closestj=k; cout*修建道路的总长度为：sumendl; returnMainFace();void MainFace()/主界面 system(cls); coutn主菜单：n; coutt1、创建景区景点分布图；n; coutt2、输出景区景点分布图（邻接矩阵）；n; coutt3、输出导游线路图；n; coutt4、判断导游线路图有无回路；n; coutt5、求两个景点间的最短路径和最短距离；n; coutt6、输出道路修建规划图；n; coutt0、退出。n; coutn*请输入操作选择：; char c; c=getch(); coutc=0&c=6) cout*输入有误，请重新输入：; c=getch(); coutcendl; 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: coutnttt*按任意键关闭本系统*n; exit(0); void returnMainFace() coutnttt按任意键返回主菜单. .; getch(); system(cls); MainFace();void Welcome() coutnntt*欢迎使用景区旅游信息管理系统*nn; cout t t t 按任意键进入系统. .; getch(); MainFace();void checked() system(cls); if(S.count=1) cout