校园导游系统.cpp

[实验目的] 1. 熟悉图的存储结构 2. 掌握图的最短路径算法 [实验内容] 用无向网表示学校的校园景点平面图

#include<stdio.h>
#include<malloc.h>
#include<ctype.h>
#define VEXNUM 7
#define LEN 300
#define INF 256    //INF表无穷
typedef int AdjType;
struct VexType{
      char num[2];      //景点编号
	  char name[20];    //景点名称
      char info[100];    //景点介绍
};
typedef struct GraphMatrix{
	  int vexnum;           //图的顶点个数
	  VexType *vexs;   //顶点信息
	  AdjType **arcs; //边信息,存放边长
}*pGraphMatrix;
struct Edge{
	int start_vex,stop_vex;
	AdjType w;
};
typedef struct Path{
	AdjType length;
	int prevex;
}*PPath;
//****读取介绍****
VexType *creat_infos(int n)//各结点的信息
{
    int i;
	VexType* infos=(VexType *)malloc(sizeof(VexType)*n);
	if(!infos)
		printf("分配内存失败!");		
	FILE *fp=fopen("信息.txt","r");
    for(i=0;i<n;i++)
	   fscanf(fp,"%s%s",infos[i].num,infos[i].name);      
	fclose(fp);
	printf("\n");
	return infos;
}
void create_graph(pGraphMatrix g)//****建图****
{
	int i,j;
	if(!g)printf("分配内存失败!");
    FILE *fp=fopen("vexs.txt","r");
	g->vexnum=VEXNUM;
	g->vexs=creat_infos(g->vexnum);//创建结点信息
    
	g->arcs=(AdjType **)malloc(sizeof(AdjType*)*g->vexnum);//创建关系矩阵
	for(i=0;i<g->vexnum;i++)
	{
		g->arcs[i]=(AdjType *)malloc(sizeof(AdjType)*g->vexnum);
	    for(j=0;j<g->vexnum;j++)
		{
	        g->arcs[i][j]=0;
			fscanf(fp,"%d",&g->arcs[i][j]);
		}
	}putchar('\n');
    fclose(fp);
}
//****求最小生成树****
void prim(pGraphMatrix g,Edge* mst)
{
	int i,j,min,vx,vy,s,n;
	int w,minw;char ch;
	Edge edge;

	printf("请输入您想要的起始点（A/a，B/b，C/c，D/d，E/e，F/f，G/g）：");scanf("%c",&ch);	
    if(ch<=103&&ch>=97)s=ch-97;
	else if(ch<=71&&ch>=65)s=ch-65; else printf("输入错误！\n");
	
	for(i=0;i<g->vexnum;i++)mst[i].w=0;
	j=0; //引入j 
	for(i=0;i<g->vexnum;i++)//初始化mst
 	    if(s==i)continue;
		else {
			n=j++;
			mst[n].start_vex=s;
            mst[n].stop_vex=i;
            mst[n].w=g->arcs[s][i];
		}

	for(i=0;i<g->vexnum-1;i++)//求n-1条边
	{
		minw=INF;min=i;
		for(j=i;j<g->vexnum-1;j++)
			if(mst[j].w<minw)//从（vx,vy）(vx在U中，vy在V-U中)中选出最短的边
			{
				minw=mst[j].w;  min=j;
			}
			edge=mst[min];  mst[min]=mst[i];  mst[i]=edge;//第i条边与最短的边交换,把小的值往前移
			vx=mst[i].stop_vex;//加入新结点vx

			for(j=i+1;j<g->vexnum-1;j++)
				//调整mst[i+1]到mst[n-1]，看以新所向所向插入的结点为中点的路径长度是否比原来的短
			{
				vy=mst[j].stop_vex;  w=g->arcs[vx][vy];
				if(w<mst[j].w) { mst[j].w=w; mst[j].start_vex=vx; }//start_vex指直接的起点
			}
	}
}
//****求最短路径****
void dijkstra(pGraphMatrix g,PPath dist,int s)//S也是从0开始
{
	int i,j,min;
	AdjType minw;
    
	dist[s].length=0;dist[s].prevex=s;g->arcs[s][s]=1;//以输入的点为起点已经在集合U中

	for(i=0;i<g->vexnum;i++)//初始化V-U集合中顶点的距离值
	{
		if(i==s)continue;
		else{
		dist[i].length=g->arcs[s][i];
		if(dist[i].length!=INF)dist[i].prevex=s;
		else dist[i].prevex=-1; 
		}
	}

	for(i=0;i<g->vexnum;i++)//????
	{
		minw=INF;min=s;

		for(j=0;j<g->vexnum;j++)
			if(g->arcs[j][j]==0 && dist[j].length<minw)//选出距离值最小的顶点 
			{ minw=dist[j].length; min=j; }
			if(min==s)break;//从VS没有路径到V-U中的顶点
			g->arcs[min][min]=1;//集合V-U中路径最小的顶点为MIN，用1标记其已选入

			for(j=0;j<g->vexnum;j++)//调整集合V-U中顶点的最短路径
			{
				if(g->arcs[j][j]==1)continue;
				if(dist[j].length>dist[min].length+g->arcs[min][j])
				{
					dist[j].length=dist[min].length+g->arcs[min][j];//以加入的点为中点
					dist[j].prevex=min;
				}
			}
	}
}
//****输出****
void ouput_mst(pGraphMatrix g,Edge* mst,int n)//输出最短周游路径  
{
	int i; char c1,c2;
	printf("\n从指定点为起点的最佳周游方案如下：\n");
	for(i=0;i<n-1;i++)
	{
		c1=65+mst[i].start_vex;c2=mst[i].stop_vex+65;
       printf("\n %c(%s)-->%c(%s)路程为：%d00米\n",c1,g->vexs[mst[i].start_vex].name,c2,g->vexs[mst[i].stop_vex].name,mst[i].w);
	 }
}
void ouput_dist(pGraphMatrix g,PPath dist)//输出任两点间的最短路径 printf("fugsfduhg");
{
	int i,s,e,num=0,path[7];//S表起点下标，E表终点下标
    char ch1,ch2;

	printf("\n请输入您想要的起始点（A/a，B/b，C/c，D/d，E/e，F/f，G/g）：\n");scanf("%c",&ch1);//输入起点
	scanf("%c",&ch2);
    printf("请输入您想要到的景点（A/a，B/b，C/c，D/d，E/e，F/f，G/g）：\n");scanf("%c",&ch2);//输入终点
    if(ch1<=103&&ch1>=97)s=ch1-97;
	else if(ch1<=71&&ch1>=65)s=ch1-65; 
	else printf("输入错误！\n"); e=s+ch2-ch1;

    dijkstra(g,dist,s);
    //****输出路径****
	if(dist[e].length>=256)printf("无法到达目的地！");
	else {printf("从 %s(%s)到 %s(%s)的最短路程为：%d00米，具体路径如下：\n\n",
		g->vexs[s].num,g->vexs[s].name,g->vexs[e].num,g->vexs[e].name,dist[e].length);
	
	for(i=0;i<g->vexnum;i++)//得到路径的逆序
		path[i]=-1;
	for(i=g->vexnum-1;i>=0&&e!=dist[e].prevex;i--)
	{
		path[i]=e;
		e=dist[e].prevex;
	}   path[i]=s;

  for(i=0;i<g->vexnum-1;i++)
	{
	   if(path[i]==-1)continue;
		  else{ ch1=path[i]+65;
		   printf("%c (%s)--> ",ch1,g->vexs[path[i]].name);
		  }
		  num++;if(num%4==0)putchar('\n');
	}
	   ch1=path[i]+65;
    printf("%c (%s)",ch1,g->vexs[path[i]].name);
	putchar('\n');
	}
}
void output_info(pGraphMatrix g)
{
	char a; int b;
printf("\nA、大礼堂 B、综合楼 C、图书馆 D、博物馆 E、课室 F、工科楼 G、办公楼 H、返回 \n\n您想了解的景点是：\n");
getchar();     
	while(1)
	{scanf("%c",&a);toupper(a);if(a=='h'||a=='H')return;//break
	printf("\n1、英文版2、中文版 请选择：\n");
	scanf("%d",&b);
		switch(b)
	{
		case 1:
		switch(a)
		{
		case'a':
		case'A':printf("How grand the building is.It looks so glorious in the sunshine.It is round seen from the sky.This building has three storeys.It's used for holding important meeting or celebrating important  activities.The groundfloor has a room for students learning arts.\n");break;
		case'b':
		case'B':printf("It is on the opposite side of Assembly_hal.It has five storeys.Naturally,you can see from name that it's used for all kinds of scourses.So you can go there to enjoy atmosphere of different fields of sciences,such as ChineseMedicine,Computering and so on.\n");break;
		case'c':
		case'C':printf("Look,there is an old man with the dressing of HangDynasty.Oh no,it's not a real man,it's just a sculpture.It is ZhangZhongjin,a famous Chinese doctor who wrote the book 'Shang Han Lun'.Behind it is our library,which has five floors.Thouands of books are stored there.Every day many students go here to absorb knowledge.\n");break;
		case'd':
		case'D':printf("Oh,it's the building with so many strange things.It also displays many medals won by our students and teachers.Many kinds of important creature series are kept here,including herbal medicine.\n");break;
		case'e':
		case'E':printf("The office building is administration of the college.There are 13 floors and every floor belongs to different departerment.Many important things are disposed in the building.\n");break;
		case'f':
		case'F':printf("The teaching building is very important for students.Mostly all students take classes here. The building consists of District A .\n");break;
		case'g':
		case'G':printf("The engineering building is the network center of the college. \n");break;
		};break;
		case 2:
        switch(a)
		{
		case'a':
		case'A':printf("大礼堂是一座雄伟的圆形建筑.这个建筑有三层,通常用来举行一些重大的会议或者庆祝活动.底层有一个宽敞的大厅可以供一些学生练习音乐舞蹈什么的.\n");break;
		case'b':
		case'B':printf("综合楼在礼堂对面,它有五层楼.从它的名字你可以很自然的知道在这栋楼开设了各种各样的课程,你可以在其中感受到各种不同学科的氛围.\n");break;
		case'c':
		case'C':printf("图书馆前面的雕像是汉代的名医张仲景,他写的<<伤寒论>>是经典医学名篇.图书馆有五层,藏书丰富,但多为医药类书籍.\n");break;
		case'd':
		case'D':printf("博物馆,也许名不副实.当然,我们太少去参观了.据说陈列了许多药材,有名贵的,稀奇古怪的,也有常规药材.\n");break;
		case'e':
		case'E':printf("办公楼学校的行政部门所在地,它有13层楼,每一层都分属不同的部门.学校诸多重大的事情都是在这里处理的.\n");break;
		case'f':
		case'F':printf("教学楼是学生上课的重要场所,分A、B区。\n");break;
		case'g':
		case'G':printf("工科楼是学校的网络中心。\n");break;
		}
		}printf("\nA、大礼堂  B、综合楼  C、图书馆  D、博物馆  E、课室  F、工科楼  G、办公楼H、返回 \n您想了解的景点是：\n");
     scanf("%c",&a);toupper(a);
	}
}
void main()
{
	int i;
	pGraphMatrix g;    g=(pGraphMatrix)malloc(sizeof(GraphMatrix));//初始化
	PPath dist;     dist=(PPath)malloc(sizeof(Path));
	Edge* mst;    mst=(Edge*)malloc(sizeof(Edge));
    
    create_graph(g);
    printf("\n****************************欢迎进入广中医校园导航系统**************************\n\n");
    while(1)
	{
		printf("\t请选择：\n\n\t1、各景点信息查寻\t        2、总游览路线(最短路径)\t\n\n\t3、游览某一景点的最短路径\t0、退出\n");
		scanf("%d",&i); if(i==0){
			printf("\n******************************谢谢！欢迎再次使用！******************************\n");break;}
	switch(i)
	{
	case 1:output_info(g);break;
	case 2:prim(g,mst);ouput_mst(g,mst,g->vexnum);break;
	case 3:ouput_dist(g,dist);break;
	}		
	}
}