实验二：校园导游咨询
一、实验内容
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
二、实验原理、方法和手段
试构造出问题模型，并编程实现这一问题的求解。根据实验内容编程，上机调试、得出正确的运行程序；编译运行程序，观察运行情况和输出结果。
校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。提供图中任意景点问路查询，即求任意两个景点之间的最短路径。
三、实验步骤
1. 设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景
点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息；
2. 为来访客人提供图中任意景点相关信息的查询；
3. 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的
简单路径。
四、实验报告
记录数据结构与算法设计的过程及实验步骤、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。格式见实验报告模板。测试数据及测试结果请在上交的资料中写明。
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define MAXV 50
#define INF 32767
typedef int SpotsNum;
typedef char InfoType;
typedef struct{
int number; //编号
InfoType sight[50],description[500]; //景区名称，描述
} VertexType;
typedef struct{
int edges[MAXV][MAXV]; //路
int n,e; //顶点数，边数
VertexType vex[MAXV]; //景点信息
} MatGraph;
MatGraph map;//地图
int A[MAXV][MAXV];//邻接矩阵
int path[MAXV][MAXV];//路径长度
void init()
{
map.e=32;map.n=15;
for(int i=0;i<map.n;i++)//初始化map.edges
for(int j=0;j<map.n;j++)
map.edges[i][j]=(i==j?0:INF);
map.edges[0][1]=map.edges[1][0]=50;
map.edges[1][2]=map.edges[2][1]=30;
map.edges[2][3]=map.edges[3][2]=10;
map.edges[3][4]=map.edges[4][3]=10;
map.edges[4][5]=map.edges[5][4]=30;
map.edges[3][6]=map.edges[6][3]=15;
map.edges[6][7]=map.edges[7][6]=100;
map.edges[7][8]=map.edges[8][7]=100;
map.edges[5][8]=map.edges[8][5]=40;
map.edges[8][9]=map.edges[9][8]=60;
map.edges[6][11]=map.edges[11][6]=200;
map.edges[10][11]=map.edges[11][10]=30;
map.edges[11][12]=map.edges[12][11]=200;
map.edges[12][13]=map.edges[13][12]=80;
map.edges[12][14]=map.edges[14][12]=50;
map.edges[11][14]=map.edges[14][11]=120;
map.vex[0].number=0;
strcpy(map.vex[0].sight,"南门");
strcpy(map.vex[0].description,"河南财经政法大学南门为财大最大的门，门口设有公交站牌，可乘坐232，570等公交车");
map.vex[1].number=1;
strcpy(map.vex[1].sight,"国旗台");
strcpy(map.vex[1].description,"日常升国旗的地方");
map.vex[2].number=2;
strcpy(map.vex[2].sight,"行政楼");
strcpy(map.vex[2].description,"分为东配与西配楼，日常办公地点");
map.vex[3].number=3;
strcpy(map.vex[3].sight,"篮球场");
strcpy(map.vex[3].description,"篮球与网球运动的小型操场，称为南操场");
map.vex[4].number=4;
strcpy(map.vex[4].sight,"第一教学楼");
strcpy(map.vex[4].description,"第一教学楼，共有六层，有大教室和小教室，其中教一219是教一最大的教室，用来开报告会和文艺表演");
map.vex[5].number=5;
strcpy(map.vex[5].sight,"第二教学楼");
strcpy(map.vex[5].description,"与第一教学楼并排而立，六层，一百二十七个教室");
map.vex[6].number=6;
strcpy(map.vex[6].sight,"第一餐厅");
strcpy(map.vex[6].description,"第一学生餐厅，主卖：面食，米饭，烩菜，甜粥，大饼以及饮料");
map.vex[7].number=7;
strcpy(map.vex[7].sight,"图书馆");
strcpy(map.vex[7].description,"图书馆是学校的文献信息资源中心，建筑面积约为4.7万平方米，阅览座位约为5000个，2016年年初投入使用。");
map.vex[8].number=8;
strcpy(map.vex[8].sight,"实验楼");
strcpy(map.vex[8].description,"由A，B座大楼接连而成，有机房，科学实验研究室等设施");
map.vex[9].number=9;
strcpy(map.vex[9].sight,"教学科研楼");
strcpy(map.vex[9].description,"分为AB楼，数学学院，外语学院，文化传播学院的办公地点均设置在此");
map.vex[10].number=10;
strcpy(map.vex[10].sight,"西操场");
strcpy(map.vex[10].description,"供'长跑，跳高，足球，篮球，排球'等同时使用的综合操场，日常上体育课的地点");
map.vex[11].number=11;
strcpy(map.vex[11].sight,"第二餐厅");
strcpy(map.vex[11].description,"共分三层，一楼是基本餐饮，二楼是风味美食，三楼是民族餐厅");
map.vex[12].number=12;
strcpy(map.vex[12].sight,"第三餐厅");
strcpy(map.vex[12].description," 第三餐厅有托斯卡纳意大利西餐厅，一楼为基本餐厅，二楼为自选餐厅和涮锅等餐饮，三楼为学校的创业孵化园，暂未投入使用");
map.vex[13].number=13;
strcpy(map.vex[13].sight,"东体育馆");
strcpy(map.vex[13].description,"设有万人看台，大屏幕，为运动会举办的地点，16年暑假举办大运会的地方");
map.vex[14].number=14;
strcpy(map.vex[14].sight,"怡苑");
strcpy(map.vex[14].description,"大四，研究生专用宿舍，三栋楼房皆为十一层，有电梯，独卫，比较豪华");
}
void Qallspots()
{
printf("\t\n河南财经政法大学一共%d景点：\n",map.n);
for(int i=0;i<map.n;i++)
printf("\t %d:%s\n",map.vex[i].number,map.vex[i].sight);
}
void Qspots()//景点查询
{
printf("\n河南财经政法大学一共%d景点：\n",map.n);
printf("\n\t请输入您要查询的景点编号(输入-1表示返回上一层)：");
int op;
while(scanf("%d",&op),op!=-1)
{
if(op<0||op>map.n)
printf(" 输入错误\n");
else
printf("\t\t%d、%s:%s\n",map.vex[op].number,map.vex[op].sight,map.vex[op].description);
printf("\n\t请输入您要查询的景点编号(输入-1表示返回上一层)：");
}
}
void Dispath(int temp)
{
printf("\n\t输入您现在的位置和将要去的位置编码(输入-1 -1表示返回上一层)：");
int i,j;
while(scanf("%d%d",&i,&j),i!=-1,j!=-1)
{
int k,s;
int apath[MAXV],d; //存放一条最短路径中间顶点(反向)及其顶点个数
if(A[i][j]!=INF && i!=j) //若顶点i和j之间存在路径
{
if(temp==1)
printf("\t\t从%s到%s的路径为:",map.vex[i].sight,map.vex[j].sight);
k=path[i][j];
d=0;
apath[d]=j; //路径上添加终点
while(k!=-1 && k!=i) //路径上添加中间点
{
d++;
apath[d]=k;
k=path[i][k];
}
d++;
apath[d]=i; //路径上添加起点
if(temp==1)
{
printf("%s",map.vex[apath[d]].sight);//输出起点
for(s=d-1;s>=0;s--) //输出路径上的中间顶点
printf("->%s",map.vex[apath[s]].sight);
printf("\n\n\n");
}
else
printf("\t\t路径长度为:%d\n\n\n",A[i][j]);
}
printf("\t输入您现在的位置和将要去的位置编码(输入-1 -1表示返回上一层)：");
}
}
void Floyd() //Floyd算法
{
int i,j,k;
for(i=0;i<map.n;i++)//构建邻接矩阵
for(j=0;j<map.n;j++)
{
A[i][j]=map.edges[i][j];
if(i!=j&&map.edges[i][j]<INF)
path[i][j]=i; //顶点i到j有边时
else
path[i][j]=-1; //顶点i到j没有边时
}
for(k=0;k<map.n;k++) //依次考察所有顶点
for(i=0;i<map.n;i++)
for(j=0;j<map.n;j++)
if(A[i][j]>A[i][k]+A[k][j])
{
A[i][j]=A[i][k]+A[k][j]; //修改最短路径长度
path[i][j]=path[k][j]; //修改最短路径
}
}
void Menu()//操作菜单
{
int op;
do{
printf("\n\n\n1：浏览河南财经政法大学校园全景\n");
printf("2：查看河南财经政法大学景点信息\n");
printf("3：查询河南财经政法大学两景点之间的最短路径\n");
printf("4：查询河南财经政法大学两景点之间的最短距离\n");
printf("5：退出系统\n");
printf("请输入您的选择：");
scanf("%d",&op);
switch(op)
{
case 1:
Qallspots();//浏览全景
break;
case 2:
Qspots();//查看景点信息
break;
case 3:
Dispath(1); //输出两景点之间的最短路径
break;
case 4:
Dispath(2);//两景点最短距离
break;
case 5:goto end; //退出系统
default :printf("输入错误\n");break;
}
}while(1);
end:;
}
int main()
{
init();
Floyd();
Menu();
}
