C++实现景区旅游信息管理系统
//深度优先搜索导游线路
int visited[M]={0};
int np=0;//找到的景点个数
int p[M];//表示各个景点的入度值
void DFS(int c){
//c为景点编号
np++;//每递归调用一次就自加一次，作为判断是否到了最后一个景点
p[c]++;
if(np==S.count){
//到了最后一个景点
cout< returnMainFace(); }else{ cout< } visited[c]=1; for(int i=0;i if(S.mat.m[c][i]>0&&visited[i]==0){ DFS(i); if(S.count>np){ cout< p[c]++; } } } if(np==S.count) returnMainFace(); } void guide_line()//导游线路 { checked(); cout<<" *请输入起始景点的景点编号："; int c; cin>>c; c--; for(int i=0;i visited[i]=0; p[i]=0;//入度置初值为0 } np=0; cout<<"*形成的导游线路图（采取深度优先策略）如下所示： "; 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 for(j=0;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] 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 for(i=0;i for(j=0;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<<" -景点1："; cin>>i; i--; if(i<0||i>S.count-1){ cout<<"*请输入合法的景点编号: "; }else{ flag=false; } } flag=true; while(flag){ cout<<" -景点2："; cin>>j; j--; if(j<0||j>S.count-1){ cout<<"*请输入合法的景点编号: "; }else{ flag=false; } } if(A[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<<" *从 "< cout< for(s=d-1;s>=0;s--){//将剩下的景点（apath[M]数组剩下的元素）打印出来 cout<<"-->"< } cout<<" ，最短距离为："< }else if(i==j){ cout<<" *景点输入不合法，输入的两个景点不能相同! "; }else{ cout<<" *这两个景点间不存在路径 "; } cout<<" 是否继续执行最短路径和最短距离的查询（Y/N）"; Y_N(); } returnMainFace(); } //道路修建规划图、最小生成树(prime算法) void build_road() { checked(); cout<<" *道路修建规划图（prime算法）规划如下： "; //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 for(j=0;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 Ai[i]=A[0][i];//取第一行存四个Ai[i]，就是一个景点到所有景点的权值 closest[i]=0;//0 } for(i=1;i min=INF; //从Ai[j]中选出最小的值存放在min for(j=0;j if(Ai[j]!=0&&Ai[j] min=Ai[j]; k=j;//记录最小的值的列j:k=j，为了下面标志此路已选 } } if(min cout<<" -第 "<<++num<<" 条路： 从"< sum+=min;//sum累计道路长度，即是已选的权值 } Ai[k]=0;//标志为已选的边的权值，避免重复选择 //例子：对比a到c和b到c的权值，取最小存进Ai[j]中 for(j=0;j if(A[k][j]!=0&&A[k][j] Ai[j]=A[k][j]; closest[j]=k;//点编号数组，记录下一条路的起点景点的编号 } } } cout<<"*修建道路的总长度为："< returnMainFace(); }