图.cpp

一个用C++写的校园导游系统

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "iostream.h"
#define MAX 40
#define MAXEDGE   500
typedef struct ArcNode
{
	int data;   //该弧所得指向的顶点的位置
	ArcNode *nextarc;   //指向下一条弧的指针

}ArcNode,*ArcLink;
typedef struct VNode    //顶点信息
{
	
	char name[30];
	int num;
    char introduction[100];
	ArcLink  firstarc;  //指向第一条依附该顶点的弧的指针

}VNode,AdjList[MAX+1];
typedef struct ALGraph
{
	AdjList vdata;   
	int vexnum,arcnum;  //图的顶点数和弧数
}ALGraph;
int Edge[MAX][MAX];      //用来存放路径的权值
int n,e;
void CreateGraph(AdjList &g)    //创建图
{  //从文件读入图的信息，包括景点信息，和路的信息
    FILE *fp;
	int num;
	char name[20];
	char information[100];
	int i=1;
	int a,b,weight;
    ArcLink p,q;     //定义一条边的两个端点的临时指针

	fp=fopen("tuxinxi.txt","r");     //打开图信息文件
	if (fp==NULL)
	{
		printf("图信息文件不能打开.");
		exit(0);
	}

	for (i=1; i<=n; i++)         //对路的权值进行初始化
	{
		for (int j=1;j<=n;j++)
		{
			if(i==j) Edge[i][j] = 0;  //主对角线上的(自己对自己付为零);
			else
				Edge[i][j] = MAXEDGE;
		}
	}
	for(i=1;i<=n;i++)  //初始化邻接表，
	{
		
		g[i].firstarc=NULL;
		
	}
   for(i=1;i<=n;i++) //从文件读入顶点的信息
   {    fscanf(fp,"%d",&num);
		g[i].num=num;
		fscanf(fp,"%s",name);
		strcpy(g[i].name,name);
		fscanf(fp,"%s",information);
		strcpy(g[i].introduction,information);
	}
   for (int j=1;j<=e;j++)    //从文件中读入边的信息
   {
	   fscanf(fp,"%d",&a);    
	   fscanf(fp,"%d",&b);
	   fscanf(fp,"%d",&weight);
	   Edge[a][b]=weight;
	   Edge[b][a]=weight;
	   p=(ArcLink)malloc(sizeof(ArcNode));//为顶点申请空间
	   p->data=a;
	   p->nextarc=g[b].firstarc;    
	   g[b].firstarc=p;    //把p插进来
	   q=(ArcLink)malloc(sizeof(ArcNode));
	   q->data=b;
	   q->nextarc=g[a].firstarc;
	   g[a].firstarc=q;
   }
	fclose(fp);
	
}
void Browser(AdjList G)       //浏览整个景点
{
	int v;
	printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
	printf("┃编号┃景点名称 ┃简介 ┃\n");
	for(v=1;v<=n;v++)
		printf("┃%-4d┃%-16s┃%-56s┃\n",G[v].num,G[v].name,G[v].introduction);
    printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
}

int GetWeight(int v1, int v2)    //得到两个景点之间的路的权值
{
	if (v1<0 || v1>n|| v2<0 || v2>n)
	{
		printf("该地点不存在！！");
		return 0;
	}
	return Edge[v1][v2];
}

void DIJ(AdjList G, int v0, int distance[], int path[]) //迪杰特斯拉算法
{    //求v0到其余顶点的最短路径path[],distance []是用来存放各路径的权值
     //借助辅助数组s[]标志,是否当前顶点属于S(1,属于)
	int *s = new int[n];	
	int minDis=0, i=0, j=0, u=0;

	for (i=1; i<=n;i++)  //初始化distance[],s[],path[]
	{
		distance[i] = GetWeight(v0,i);
		s[i] = 0;
		if(i!=v0 && distance[i]<MAXEDGE) path[i] = v0;
		else path[i] =-1;   //v0到v0为-1
	}
	s[v0] = 1;   //v0入s集
	distance[v0]=0;  //v0到v0的距离为零
	for (i=1;i<n;i++)   //
	{  //开始主循环，每次求得v0到某个顶点v的最短距离，并将v并入s中
		minDis = MAXEDGE;  //当前所知v0顶点的最近距离，并设初值为MAXEGDE
		int u=v0;           //把v0给u
		for (j=1; j<=n; j++)
		{
			if (!s[j]  && distance[j]<minDis)//查找属于s[]并且求最小的路径
			{
				u = j;    //在s[]一直往下找
				minDis = distance[j];// 赋给最小路径
			}
		}
	
		s[u] = 1;      //离v0最近的景点，入s[]
		for(j=1;j<=n;j++)  //更新当前最短路径及距离
		{
			if(!s[j]&& GetWeight(u,j)<MAXEDGE )
			{
				int  newdist= distance[u]+GetWeight(u,j);
				if(newdist<distance[j])
				{
				    distance[j]=newdist;
					path[j] = u;      //记录下寻找最短的路
				}
			}
		}	
	}
  

}
void  ShortPath(AdjList g)   //求两点的最短路径
{
    int qidian,zhongdian;
	int distance[MAX];
	int path[MAX];

	int  minPath=0;
	int way[MAX];
	int q=0;int pre=0;
	printf("\n");
	printf("请输入要查询的景点的起点，终点:");
	scanf("%d,%d",&qidian,&zhongdian);

	DIJ(g,qidian,distance,path);
    
	int w = zhongdian;
    while (w != qidian)//遍历path[]并把到终点的路存放在way[]中
    {
        q++;
        way[q] = path[w];
        w = path[w];
    }
    printf("路径为:");      //输出路径
    for (int j = q; j >= 1; j--)
    {
        printf("%s-->",g[way[j]].name);
    }
   printf("%s",g[zhongdian].name);
   printf("\n");
   printf("最短路径为%d",distance[zhongdian]);
   printf("\n");
    

}
void Serach(AdjList G)  //查询景点信息
{
      int k,flag=1;
	   while(flag)
		{
			printf("请输入要查询的景点编号:");
			scanf("%d",&k);
			if(k<0||k>n)
			{
				printf("景点编号不存在!请重新输入景点编号:");
				scanf("%d",&k);
			}
			if(k>=0&&k<=n)
				flag=0;
		}
		printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
		printf("┃编号┃景点名称 ┃简介 ┃\n");
		printf("┃%-4d┃%-16s┃%-56s┃\n",G[k].num,G[k].name,G[k].introduction);
		printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
		

}

void DFS(AdjList g,int v,int visited[])  //从v个顶点深度优先搜索
{
	ArcLink p;
	int w;
	visited[v]=1;//做上访问过的标记
	printf("%s->",g[v].name);
	p=g[v].firstarc;    //取该顶点链表
	while(p)   //遍历该链表
	{

		w=p->data;
		 if(visited[w]==0)
			 DFS(g,w,visited);
		 p=p->nextarc;
	}
}
void  DFSTraverse(AdjList g)//深度优先遍历
{
	int visited[MAX+1];
	int v;
	int num,count=1;
	for(v=1;v<=n;v++)
	{
		visited[v]=0;   //初始化标志位
	}
	printf("请输入你要开始的景点:");
	scanf("%d",&num);
	
	 while(count<=n)
	 {   v=num;
		if(visited[v]==0)
		{
			DFS(g,v,visited);//对尚未访问的顶点调用ＤＦＳ
			v++;
		}
		count++;
	}

}
void   PrintPath(AdjList g,int path[],   int   length)      //打印路径   
{	
	for   (int i = 0; i<length; i++) 
	{
		 printf("%s-->",g[path[i]].name); 
	}
	printf("\n"); 
}   
void   SearchAllPath(AdjList G,  int  path[],  int   visited[],   int   v,   int   des,   int   length)     
{	//利用深度优先遍历，path[]记录路径，visited[]设访问标志，v起点，des终点，length，代表的是访问景点的长度
   if   (visited[v])   return; //若所有的景点都访问过，则终止  
	path[length-1]=v;    //开始记录路径 
	if   (v==des)        //若找到终点则，打印路径   
	{	
		PrintPath(G,path,length);   
	}   
	    else     
		  { 
		   visited[v]=1;   
		   for   (int i=1;i<=n;i++)     
			if   (GetWeight(v,i)!=MAXEDGE&&!visited[i])//两个景点之间有路，并且还未访问过，则深度遍历                                  
			{	
				SearchAllPath(G,path,visited,i,des,length+1);  
			}   
			visited[v] =0;   
	}   
}   
void InitGraph(AdjList &g)   //初始化图的景点
{
   	printf("请输入图中的顶点数:");
	scanf("%d",&n);
    printf("请输入道路的数目:");
	scanf("%d",&e);
	printf("\n");
	printf("用户可以自己写文件创建图的信息.");
	CreateGraph(g);
}
char  Menu()       //主菜单
{ 
	char c;
    int flag;
	do{
	printf("\n 西安邮电学院导游图\n");
	printf(" ┏━━━━━━━━━━━━━━━━━━━━┓\n");
	printf(" ┃ 1.创建导游系统  | \n"); 
        printf(" ┃ 2.浏览校园全景 ┃\n");
        printf(" ┃ 3.寻找某一起点的最佳路径 ┃\n");
	printf(" ┃ 4.选择出发点和目的地 ┃\n");
	printf(" ┃ 5.查看景点信息 ┃\n");
    printf("     ┃ 6.浏览出一个起点的所有路径 ┃\n");
	printf(" ┃ 7.退出系统 ┃\n");
	printf(" ┗━━━━━━━━━━━━━━━━━━━━┛\n");
    printf("请选择(1--7)-:");
    scanf("%c",&c);
    if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='6'||c=='7')
			 
				 flag=0;	
	  if(flag)
		  printf("输入错误,请重新选择.");
		  getchar();

	}while(flag);

    return c;
}
void narrate(AdjList g) /* 说明函数 */
{
	int i,k=0;
	printf("\n\t\t*****************欢迎使用校园导游程序***************\n");
	printf("\t__________________________________________________________________\n");
	printf("\t\t景点名称\t\t|\t景点描述\n");
	printf("\t________________________________|_________________________________\n");
	for(i=1;i<=n;i++)
	{
		printf("\t%c(%2d)%-10s\t\t|\t%-25s%c\n",2,i,g[i].name,g[i].introduction,2); /* 输出景点列表 */
		k=k+1;
	}
	printf("\t________________________________|_________________________________\n");
}
void main()        //主函数
{
    AdjList g;
    int v0,v1,i; int visited[MAX];
	int path[MAX];
	char c;
    system("color 5f");
    do
	{  
		c=Menu();
		switch(c)
		{
		case '1':
			system("cls");
		    InitGraph(g);
		    printf("\n\n\t\t\t\t请按任意键继续...\n");
			getchar();
			getchar();
			break;
		case '2':
			system("cls");
			Browser(g);
			break;
		case '3':
			system("cls");
			narrate(g);
			DFSTraverse(g);
			printf("\n\n\t\t\t\t请按任意键继续...\n");
			getchar();
			getchar();
			break;
        case  '4':
			system("cls");
			narrate(g);
			ShortPath(g);
			printf("\n\n\t\t\t\t请按任意键继续...\n");
			getchar();
			getchar();
			break;
		case  '5':
			 Serach(g);
			printf("\n\n\t\t\t\t请按任意键继续...\n");
			 getchar();
			 getchar();
             break;
		case  '6':
			  system("cls");
			  narrate(g);
			  printf("请输入查询起点,终点:");
	          scanf("%d,%d",&v0,&v1);
			  for   (i=1;   i<=n;   i++)   visited[i]=0;       //   初始化   
	          SearchAllPath(g,   path,   visited,  v0,  v1,   1);
			  printf("\n\n\t\t\t\t请按任意键继续...\n");
			  getchar();
			  getchar();
              break;
		case  '7':
			printf("\n");
            printf("\n");
			printf("\n");
			printf("\n");
			printf("                           谢谢使用.                   ");
			printf("\n");
			 break;
			 

		};
 }while(c!='6');
   
	
}