精选_基于C++的景区旅游信息管理系统_源码打包

# 基于C++的景区旅游信息管理系统 # 1 问题描述 如今生活水平提高，大家都喜欢在假期中到一个旅游景点参观，在旅游景区中经常听到游客打听从一个景点到另一个景点的最短路径和最短距离，这类不喜欢按照导游图来游览的游客常常需要一个景区管理系统来挑选自己喜欢的旅游景点，再规划一个最短路径和最短距离来游览，一边节省时间跟提高旅游效率。 # 2 数据结构的设计 - 建立一个景区旅游信息管理系统，实现如下功能： - **创建景区景点分布图** - 通过一个邻接矩阵（实质是一个二维数组,m[i][j]表示从i到j的权值大小，为零表示没有直达的路径）记录景区景点的分布图 - **输出景区景点分布图（邻接矩阵）** - 通过扫描邻接矩阵输出景区景点分布图 - **输出导游线路图：深度优先策略** - 首先通过遍历景点，通过用户给出的一个入口景点c，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略（递归），这个也是正常的游客的心理 - **判断导游线路图有无回路：拓扑排序（查找入度大于1的景点）** - 为了使导游线路图能够优化，可以通过拓扑排序判断图中有无回路，若有回路则打印输出回路中的景点，供人工优化 - **求两个景点间的最短路径和最短距离：floyd算法** - 在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离 - **输出道路修建规划图：prime算法** - 在景区建设中，道路建设是其中一个重要的内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题，通过prime算法来求最小生成树 通过修改后添加的功能： - **将景区景点分布图安装指定的文件名（可以景区名字命名）保存到默认的目录file下** - 在这里我遇到了路径格式问题，通过查询资料得以解决这个问题 - **从默认目录file下读取指定文件名的景区景点分布图** - 这样就减少了每次都要创建景区景点分布图，也方便从已有的景区景点分布图导入系统，不用手动新建，实际应用中更加的方便人性化 - **为当前的景区添加景点道路** - 一开始没有将景区景点的路径清零，以至于添加景点道路后，再从新导入景点较少的景区景点分布图，再添加景点道路的时候发现之前的道路依然存在，因此在添加景点道路之前要将道路景区清零 # 3 算法设计（核心代码） ```C++ //深度优先搜索导游线路 int visited[M]={0}; int np=0;//找到的景点个数 int p[M];//表示各个景点的入度值 void DFS(int c){ //c为景点编号 np++;//每递归调用一次就自加一次，作为判断是否到了最后一个景点 p[c]++; if(np==S.count){ //到了最后一个景点 cout<<S.mat.Pname[c]<<endl; returnMainFace(); }else{ cout<<S.mat.Pname[c]<<"-->"; } visited[c]=1; for(int i=0;i<S.count;i++){ if(S.mat.m[c][i]>0&&visited[i]==0){ DFS(i); if(S.count>np){ cout<<S.mat.Pname[c]<<"-->"; p[c]++; } } } if(np==S.count) returnMainFace(); } void guide_line()//导游线路 { checked(); cout<<"\n*请输入起始景点的景点编号："; int c; cin>>c; c--; for(int i=0;i<S.count;i++){ visited[i]=0; p[i]=0;//入度置初值为0 } np=0; cout<<"*形成的导游线路图（采取深度优先策略）如下所示：\n\n\t"; DFS(c); } //Floyd（佛洛依德）算法，A[M][M]表示最短距离，path[M][M]表示辅助数组，记住前驱 void Floyd(int A[M][M],int path[M][M]){ int i,j,k; for(i=0;i<S.count;i++){ for(j=0;j<S.count;j++){ if(S.mat.m[i][j]==0&&i!=j){ //如果两点之间没有边相连，则权为无穷大 A[i][j]=INF;//INF=999666333 }else if(i==j){ A[i][j]=0; }else{ //S.mat.m[i][j]表示两个景点之间的道路长度 A[i][j]=S.mat.m[i][j]; } //给所有的path[i][j]赋值 if(i!=j&&S.mat.m[i][j]<INF){ path[i][j]=i; }else{ //（i==j&&S.mat.m[i][j]=INF path[i][j]=-1; } } } //k注意放到最外层，让A[i][j]检测都经过每一个k for(k=0;k<S.count;k++){ for(i=0;i<S.count;i++){ for(j=0;j<S.count;j++){ if(A[i][j]>A[i][k]+A[k][j]){//如果i->j的权值大于i->k->j的权值 A[i][j]=A[i][k]+A[k][j]; path[i][j]=path[k][j];//path[k][j]=k前驱?k是指向的下一个景点 } } } } } void min_distance()//最短路径、距离 { checked(); int A[M][M],path[M][M]; Floyd(A,path);//A是一个景点到另一个景点的最短路径的长度 while(true){ Num_Name();//编号对应的景点名称 int i,j,k,s; int apath[M],d;//apath[M]是记录路径的数组 bool flag=true; while(flag){ cout<<"\t-景点1："; cin>>i; i--; if(i<0||i>S.count-1){ cout<<"*请输入合法的景点编号:\n"; }else{ flag=false; } } flag=true; while(flag){ cout<<"\t-景点2："; cin>>j; j--; if(j<0||j>S.count-1){ cout<<"*请输入合法的景点编号:\n"; }else{ flag=false; } } if(A[i][j]<INF&&i!=j){ k=path[i][j];//k是指向的下一个景点 d=0;//路径有d+2个景点,是数组apath的下标 //将待输出的路径的点存放在栈apath中 apath[d]=j;//最后一个景点 while(k!=-1&&k!=i){ d++; apath[d]=k; //再继续判断还有没有景点 k=path[i][k]; } d++; apath[d]=i;//加上第一点 cout<<"\n*从 "<<S.mat.Pname[i]<<" 到"<<S.mat.Pname[j]<<" 最短路径为："; cout<<S.mat.Pname[apath[d]];//apath[M]数组最后一个，就是第一个起点,相当于栈 for(s=d-1;s>=0;s--){//将剩下的景点（apath[M]数组剩下的元素）打印出来 cout<<"-->"<<S.mat.Pname[apath[s]]; } cout<<" ，最短距离为："<<A[i][j]<<endl;//Floyd算法已经将最短路径算出来存放到了A[i][j](将INF的值用最短路径代替了) }else if(i==j){ cout<<"\n*景点输入不合法，输入的两个景点不能相同!\n"; }else{ cout<<"\n*这两个景点间不存在路径\n"; } cout<<"\n是否继续执行最短路径和最短距离的查询（Y/N）"; Y_N(); } returnMainFace(); } //道路修建规划图、最小生成树(prime算法) void build_road() { checked(); cout<<"\n*道路修建规划图（prime算法）规划如下：\n"; //Ai[M]表示待选边的权值,邻接矩阵的一行,closest[M]：点编号数组，记录下一条路的起点景点的编号 intAi[M],min,closest[M],i,j,k,sum=0,num=0;//num表示第几条路 int A[M][M]; //赋权值 for(i=0;i<S.count;i++){ for(j=0;j<S.cou