C++综合案例练习

2024-07-10 13:45| 来源: 网络整理| 查看: 265

1 问题描述如今生活水平提高，大家都喜欢在假期中到一个旅游景点参观，在旅游景区中经常听到游客打听从一个景点到另一个景点的最短路径和最短距离，这类不喜欢按照导游图来游览的游客常常需要一个景区管理系统来挑选自己喜欢的旅游景点，再规划一个最短路径和最短距离来游览，一边节省时间跟提高旅游效率。

2 数据结构的设计建立一个景区旅游信息管理系统，实现如下功能：

创建景区景点分布图通过一个邻接矩阵（实质是一个二维数组,m[i][j]表示从i到j的权值大小，为零表示没有直达的路径）记录景区景点的分布图.

输出景区景点分布图（邻接矩阵）通过扫描邻接矩阵输出景区景点分布图

输出导游线路图：深度优先策略首先通过遍历景点，通过用户给出的一个入口景点c，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略（递归），这个也是正常的游客的心理

判断导游线路图有无回路：拓扑排序（查找入度大于1的景点）为了使导游线路图能够优化，可以通过拓扑排序判断图中有无回路，若有回路则打印输出回路中的景点，供人工优化

求两个景点间的最短路径和最短距离：floyd算法在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离

输出道路修建规划图：prime算法在景区建设中，道路建设是其中一个重要的内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题，通过prime算法来求最小生成树通过修改后添加的功能：

将景区景点分布图安装指定的文件名（可以景区名字命名）保存到默认的目录file下在这里我遇到了路径格式问题，通过查询资料得以解决这个问题

从默认目录file下读取指定文件名的景区景点分布图这样就减少了每次都要创建景区景点分布图，也方便从已有的景区景点分布图导入系统，不用手动新建，实际应用中更加的方便人性化

为当前的景区添加景点道路一开始没有将景区景点的路径清零，以至于添加景点道路后，再从新导入景点较少的景区景点分布图，再添加景点道路的时候发现之前的道路依然存在，因此在添加景点道路之前要将道路景区清零

3 算法设计（核心代码）

//深度优先搜索导游线路 int visited[M]={0}; int np=0;//找到的景点个数 int p[M];//表示各个景点的入度值 void DFS(int c){ //c为景点编号 np++;//每递归调用一次就自加一次，作为判断是否到了最后一个景点 p[c]++; if(np==S.count){ //到了最后一个景点 cout"; } visited[c]=1; for(int i=0;i DFS(i); if(S.count>np){ cout visited[i]=0; p[i]=0;//入度置初值为0 } np=0; cout for(j=0;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] //（i==j&&S.mat.m[i][j]=INF path[i][j]=-1; } } } //k注意放到最外层，让A[i][j]检测都经过每一个k for(k=0;k for(j=0;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){ couti; i--; if(iS.count-1){ cout coutj; j--; if(jS.count-1){ cout 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 cout checked(); cout if(S.mat.m[i][j]==0&&i!=j){ A[i][j]=INF; }else if(i==j){ A[i][j]=0; }else{ A[i][j]=S.mat.m[i][j]; } } } for(i=0;i min=INF; //从Ai[j]中选出最小的值存放在min for(j=0;j min=Ai[j]; k=j;//记录最小的值的列j:k=j，为了下面标志此路已选 } } if(min if(A[k][j]!=0&&A[k][j]

【本文地址】

公司简介

联系我们