// 校园导游咨询
/*[问题描述]
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
[基本要求]
(1)设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
(2)为来访客人提供图中任意景点相关信息的查询。
(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
[实现提示]
一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。
一需求分析
1从武汉理工大学余家头校区平面图中选取10个大家熟悉的景点，抽象成一个无向带权图（如图所示）。以图中顶点表示景点，边上的权值表示两地的距离。
2本程序的目的是为用户提供路径咨询和景点查询。根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。
二、概要设计
1本文采用的数据结构
*/
/*包含头文件*/
// 数据结构课程设计.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include
#include
#define INT_MAX 10000
#define n 10 //定义全局变量
int cost[n][n];// 边的值
int shortest[n][n];//两点间的最短距离
int path[n][n];// 经过的景点
void introduce(); //自定义函数原型说明
int shortestdistance();
void floyed();
void display(int i,int j);
/*
（1）景点信息查询
（2）两景点的最短距离
（3）两个景点之间的路径
三、详细设计 */
void main() //主函数
{
int i,j;
char k;
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
cost[i][j]=INT_MAX;
cost[1][3]=cost[3][1]=200;
cost[1][2]=cost[2][1]=50;
cost[2][3]=cost[3][2]=150;
cost[2][4]=cost[4][2]=120;
cost[1][4]=cost[4][1]=150;
cost[4][5]=cost[5][4]=80;
cost[4][9]=cost[9][4]=120;
cost[5][9]=cost[9][5]=220;
cost[5][7]=cost[7][5]=180;
cost[5][6]=cost[6][5]=90;
cost[6][7]=cost[7][6]=50;
cost[7][8]=cost[8][7]=70;
cost[8][6]=cost[6][8]=130;
cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0;
cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;
while(1)
{
printf("----------------欢迎使用中原工学院校园导游系统!----------------\n");
printf("1.景点信息查询………请按 i (introduc)键\n");
printf("2.景点最短路径查询…请按 s (shortestdistance)键\n");
printf("3.退出系统……………请按 e (exit)键\n");
printf("学校景点列表:\n");
printf("1:学校正门 ");
printf("2:图书馆 ");
printf("3:行政楼");
printf("4:体育馆 ");
printf("5:操场\n");
printf("6:北
苑宿舍楼群 ");
printf("7:北苑餐厅 ");
printf("8:紫薇广场 ");
printf("9:滴水涌泉 ");
printf("10:南苑操场\n");
printf("请选择服务:");
scanf("\n%c",&k);
switch(k)
{
case 'i':
printf("进入景点信息查询:");
introduce();
break;
case 's':
printf("进入最短路径查询:");
shortestdistance();
break;
case 'e':
exit(0);
default:
printf("输入信息错误！\n请输入字母i或s或e.\n");
break;
}
}
}/*main*/
void introduce()
{/*景点介绍*/
int a;
printf("您想查询哪个景点的详细信息?请输入景点编号:");
scanf("%d",&a);
getchar();
printf("\n");
switch(a)
{
case 1:
printf("1:学校正门\n\n 学校的大门，前面一条宽敞的马路，它是107国道，学校大门后面就是宏伟高大的图书馆，两者相互衬托不仅显示出学校大门的气魄，也显示出图书馆的匠心独具。\n\n");break;
case 2:
printf("2:同学们学习的圣地，里面有各种各样的图书，让你随便挑选，同时我们的图书馆大楼设计的也像一个博士帽，它代表希望同学们都学有所成的意思，同时大楼中间有个大洞，代表上接天时下接地气\n\n");break;
case 3:
printf("3:行政楼\n\n");break;
case 4:
printf("4:体育馆\n\n 学生娱乐与锻炼的地方\n\n");break;
case 5:
printf("5:操场\n\n 学生上体育课及运动的场地，设有田径场、足球场、还有网球场，球场旁边还设有看台。\n\n");break;
case 6:
printf("6:北苑宿舍楼\n\n 学生睡觉生活休息的地方\n\n");break;
case 7:
printf("7:北苑餐厅\n\n 同学们就餐的地方，餐厅旁边还有一个北苑食堂，是私人开的类似饭店的餐厅\n\n");break;
case 8:
printf("8:紫薇广场\n\n 我们学校举办文艺活动及其他大型学校活动的地方。\n\n");break;
case 9:
printf("9:滴水涌泉\n\n 我们学校的标志性建筑之一，它代表的含义是滴水之恩当涌泉相报。\n\n\n");break;
case 10:
printf("10: 南苑操场\n\n 南苑的莘莘学子们上体育课及做课外活动的地方的地方。\n\n");break;
default:
printf("景点编号输入错误！请输入1->10的数字编号！\n\n"); break;
}
}/*introduce*/
int shortestdistance()
{/*要查找的两景点的最短距离*/
int i,j;
printf("请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):");
scanf("%d,%d",&i,&j);
if(i>n||i<=0||j>n||j<0)
{
printf("输入信息错误！\n\n");
printf(" 请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):\n");
scanf("%d,%d",&i,&j);
}
else
{
floyed();
display(i,j);
}
return 1;
}/*shortestdistance*/
void floyed()
{/*用floyed算法求两个景点的最短路径*/
int i,j,k;
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
shortest[i][j]=cost[i][j];
path[i][j]=0;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(
shortest[i][j]>(shortest[i][k]+shortest[k][j]))
{/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/
shortest[i][j]=shortest[i][k]+shortest[k][j];
path[i][j]=k;
path[j][i]=k;
}
}/*floyed*/
void display(int i,int j)
{/* 打印两个景点的路径及最短距离 */
int a,b;
a=i;
b=j;
printf("您要查询的两景点间最短路径是:\n\n");
if(shortest[i][j]!=INT_MAX)
{
if(i
printf("%d",b);
while(path[i][j]!=0)
{/* 把i到j的路径上所有经过的景点按逆序打印出来*/
printf("<-%d",path[i][j]);
if(i
else
i=path[j][i];
}
printf("<-%d",a);
printf("\n\n");
printf("(%d->%d)最短距离是:%d米\n\n",a,b,shortest[a][b]);
}
else
{
printf("%d",a);
while(path[i][j]!=0)
{/* 把i到j的路径上所有经过的景点按顺序打印出来*/
printf("->%d",path[i][j]);
if(i
else
i=path[j][i];
}
printf("->%d",b);
printf("\n\n");
printf("(%d->%d)最短距离是:%5d米\n\n",a,b,shortest[a][b]);
}
}
else
printf("输入错误！不存在此路！\n\n");
printf("\n");
}/*display*/