本文实例为大家分享了C++实现景区旅游信息管理系统的具体代码,供大家参考,具体内容如下
1 问题描述如今生活水平提高,大家都喜欢在假期中到一个旅游景点参观,在旅游景区中经常听到游客打听从一个景点到另一个景点的最短路径和最短距离,这类不喜欢按照导游图来游览的游客常常需要一个景区管理系统来挑选自己喜欢的旅游景点,再规划一个最短路径和最短距离来游览,一边节省时间跟提高旅游效率。
2 数据结构的设计建立一个景区旅游信息管理系统,实现如下功能:
1、创建景区景点分布图
通过一个邻接矩阵(实质是一个二维数组,m[i][j]表示从i到j的权值大小,为零表示没有直达的路径)记录景区景点的分布图.
2、输出景区景点分布图(邻接矩阵)
通过扫描邻接矩阵输出景区景点分布图
3、输出导游线路图:深度优先策略
首先通过遍历景点,通过用户给出的一个入口景点c,建立一个导游线路图,导游线路图用有向图表示。遍历采用深度优先策略(递归),这个也是正常的游客的心理
4、判断导游线路图有无回路:拓扑排序(查找入度大于1的景点)
为了使导游线路图能够优化,可以通过拓扑排序判断图中有无回路,若有回路则打印输出回路中的景点,供人工优化
5、求两个景点间的最短路径和最短距离:floyd算法
在导游线路图中,还为一些不愿按线路走的游客提供信息服务,比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离
6、输出道路修建规划图:prime算法
在景区建设中,道路建设是其中一个重要的内容。道路建设首先要保证能连通所有景点,但又要花最小的代价,可以通过求最小生成树来解决这个问题,通过prime算法来求最小生成树
通过修改后添加的功能:
7、将景区景点分布图安装指定的文件名(可以景区名字命名)保存到默认的目录file下
在这里我遇到了路径格式问题,通过查询资料得以解决这个问题
8、从默认目录file下读取指定文件名的景区景点分布图
这样就减少了每次都要创建景区景点分布图,也方便从已有的景区景点分布图导入系统,不用手动新建,实际应用中更加的方便人性化
9、为当前的景区添加景点道路
一开始没有将景区景点的路径清零,以至于添加景点道路后,再从新导入景点较少的景区景点分布图,再添加景点道路的时候发现之前的道路依然存在,因此在添加景点道路之前要将道路景区清零
3 算法设计(核心代码)//深度优先搜索导游线路
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.count;j++){
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<S.count;i++){
Ai[i]=A[0][i];//取第一行存四个Ai[i],就是一个景点到所有景点的权值
closest[i]=0;//0
}
for(i=1;i<S.count;i++){
min=INF;
//从Ai[j]中选出最小的值存放在min
for(j=0;j<S.count;j++){
if(Ai[j]!=0&&Ai[j]<min){
min=Ai[j];
k=j;//记录最小的值的列j:k=j,为了下面标志此路已选
}
}
if(min<INF){
cout<<"\t-第 "<<++num<<" 条路: 从"<<S.mat.Pname[closest[k]]<<" 到"<<S.mat.Pname[k]<<" , 该道路长度为:"<<min<<endl;
sum+=min;//sum累计道路长度,即是已选的权值
}
Ai[k]=0;//标志为已选的边的权值,避免重复选择
//例子:对比a到c和b到c的权值,取最小存进Ai[j]中
for(j=0;j<S.count;j++){
if(A[k][j]!=0&&A[k][j]<Ai[j]){
Ai[j]=A[k][j];
closest[j]=k;//点编号数组,记录下一条路的起点景点的编号
}
}
}
cout<<"*修建道路的总长度为:"<<sum<<endl;
returnMainFace();
}
4 运行与测试
通过创建不同的景区景点分布图来测试,测试结果正确无误。
5 总结与心得通过认真对待数据结构课程设计,认真思考如何用算法和代码来解决现实生活中的问题,认真参考优秀参考文献和优秀作品后,收获甚多。一开始,面对现实生活的问题,毫无头绪,不知如何入手来实现解决现实生活的问题,后来通过参考文献和别人的类似作品后,才发现原来数据结构算法是这样使用的,也因此解开之前在上数据结构课堂上的疑惑:数据结构如何运用在我们的工作代码上。总的来说,收获的东西确实不少,只要认真对待学习上的每一个环节,就一定会有收获。
通过老师的指导,此系统优化了很大哦,并且让我学会了很多东西,很多实际问题都没有考虑周全,老师都可以指出并要求我修改,正是因为修改,才让我学到了更多的知识,使我明白了,做课程设计,不单单但是做课程设计,还要通过这次课程设计来考虑实际问题,不断优化。