程序设计实训：校园导游模拟程序的设计
1） 问题描述：
设计一个校园导游程序，为来访的客人提供住处查询服务。
选取苦干（多于10个）个有代表性的景点抽象成一个无向带权图，以图中顶点表示校内景点，边上的权值表示两景点间的距离。
2） 具体功能要求：
按菜单项管理的主界面
菜单项及功能要求如下
1） 学校景点介绍：由一个子函数实现，输出学校全部景点的信息，包括景点编号、名称及简介。
2） 查看浏览路线：根据用户输入的起始景点编号，求出从该景点到其他景点的最短路径线路及距离，要求用DIJKSTRA算法完成。
3） 查询景点间最短路径：两个景点间的最短路径，要求用FLOYD算法完成。
4） 景点信息查询：根据用户输入的编号，输出其相关信息。
5） 更改基本信息：新增景点，删除边，重建图等。
6） 查询景点间可行路径：显示所有符合长度限制（如路径长度不大于5）的所有路径。（可选做）
7） 打印图
8） 退出
本附录中为程序运行时的效果说明。
实训报告格式及要求：
封面：
程序设计实训报告
（分组成员名单（姓名学号） 和分工）
内容：
一、 题目
校园导游程序 (3)
3） 问题描述：
设计一个校园导游程序，为来访的客人提供住处查询服务。
选取苦干（多于10个）个有代表性的景点抽象成一个无向带权图，以图中顶点表示校内景点，边上的权值表示两景点间的距离。
4） 具体功能要求：
按菜单项管理的主界面
菜单项及功能要求如下
9） 学校景点介绍：由一个子函数实现，输出学校全部景点的信息，包括景点编号、名称及简介。
10） 查看浏览路线：根据用户输入的起始景点编号，求出从该景点到其他景点的最短路径线路及距离，要求用DIJKSTRA算法完成。
11） 查询景点间最短路径：两个景点间的最短路径，要求用FLOYD算法完成。
12） 景点信息查询：根据用户输入的编号，输出其相关信息。
13） 更改基本信息：新增景点，删除边，重建图等。
14） 查询景点间可行路径：显示所有符合长度限制（如路径长度不大于5）的所有路径。（可选做）
15） 打印图
16） 退出
二、 需求分析
学校旅游成最近热门的话题，比如“清华大学”旅游，等等，让更多的同学，老师或者外校人员来本校访问，可以很容易的在学校参观等，为了让大家不会迷路，可以更轻松自如的对学校进行参观，故设计此小型学校导航系统。
三、 概要设计（存储结构设计，自定义函数介绍，系统框架图）
在查询景点间最短路径时运用了迪杰斯特算法，查询景点间所有路径则是运用了佛罗算法来实现的。定义了一个结构体作为一个存储信息的无向图。
typedef struct //景点信息存储
Status ViewInfo(int cost[MAXSIZE][MAXSIZE]) //景点路径长度
void floyed()/*用floyed算法求两个景点的最短路径*/
void display(int i,int j)/* 打印两个景点的路径及最短距离 */
void DFS(int k,int v1,int t,int cost[MAXSIZE][MAXSIZE])
{//k为当前景点编号,v1为终点编号,t为当前已经找到的以k为终点的路径上景点的个数
Status Allpath(int cost[MAXSIZE][MAXSIZE],int v0,int v1) //两点间的所有路径
Status ShowAll(Graph p[MAXSIZE]) //显示所有信息
Status IntroduceView(Graph p[MAXSIZE]) //查询景点信息
Status DeleteView(Graph p[MAXSIZE],int cost[MAXSIZE][MAXSIZE])//删除景点,n为现有景点的个数
Status UpdateUiew(Graph p[MAXSIZE]) //更新景点信息
Status UpdatePath(int cost[MAXSIZE][MAXSIZE]) //更新道路
void main()
{/*主函数*/
四、 详细设计及测试结论（算法的设计，测试遇到的问题，原因及解决办法）
用到了迪杰斯特算法和佛罗算法对路径最短进行优化，其中还加入了深度优先算法。
遇到的问题：总是报错，可是又很难找到出错的地方。这是对整个结构和思路的不清晰，最后多处因为一些很小的细节，比如符号，还有函数变量等等。。
五、 总结
附录：程序详细清单及测试图例。
/*
问题描述：
设计一个校园导游程序，为来访的客人提供住处查询服务。
选取苦干（多于10个）个有代表性的景点抽象成一个无向带权图，以图中顶点表示校内景点，边上的权值表示两景点间的距离。
2）具体功能要求：
按菜单项管理的主界面
菜单项及功能要求如下
1）学校景点介绍：由一个子函数实现，输出学校全部景点的信息，包括景点编号、名称及简介。
2）查看浏览路线：根据用户输入的起始景点编号，求出从该景点到其他景点的最短路径线路及距离，要求用DIJKSTRA算法完成。
3）查询景点间最短路径：两个景点间的最短路径，要求用FLOYD算法完成。
4）景点信息查询：根据用户输入的编号，输出其相关信息。
5）更改基本信息：新增景点，删除边，重建图等。
6）查询景点间可行路径：显示所有符合长度限制（如路径长度不大于5）的所有路径。（可选做）
7）打印图
8）退出
*/
/*包含头文件*/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
/*定义符号常量*/
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 50
#define INT_MAX 1000000
typedef int Status;
int cost[MAXSIZE][MAXSIZE];/* 边的值*/
int shortest[MAXSIZE][MAXSIZE];/* 两点间的最短距离*/
int path[MAXSIZE][MAXSIZE];/* 经过的景点*/
int T[MAXSIZE];
int n;
bool Visit[MAXSIZE];//访问标志数组
/*自定义函数原型说明*/
void introduce();
int shortestdistance();
void floyed();
void display(int i,int j);
typedef struct //景点信息存储
{
int num;//景点编号
char name[40];//景点名称
char info[100];//景点信息
}Graph;
Status ViewInfo(int cost[MAXSIZE][MAXSIZE]) //景点路径长度
{
int i,j;
for(i=0;i<=MAXSIZE;i++) //给各景点之间的路径赋上最大值
{
for(j=0;j<=MAXSIZE;j++)
{
if(i==j)
cost[i][j]=0;
else
cost[i][j]=INT_MAX;
}
}
cost[1][2]=cost[2][1]=250;
cost[2][3]=cost[3][2]=160;
cost[2][4]=cost[4][2]=200;
cost[3][4]=cost[4][3]=110;
cost[1][4]=cost[4][1]=400;
cost[2][5]=cost[5][2]=300;
cost[5][10]=cost[10][5]=100;
cost[5][6]=cost[6][5]=260;
cost[6][7]=cost[7][6]=100;
cost[7][8]=cost[8][7]=360;
cost[7][9]=cost[9][7]=270;
cost[8][9]=cost[9][8]=450;
return OK;
}
void floyed()/*用floyed算法求两个景点的最短路径*/
{
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;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之间有最短路径时
{/* 把i到j的路径上所有经过的景点按逆序打印出来*/
printf("<–%d",path[i][j]);
if(i
j=path[i][j];
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
j=path[i][j];
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*/
int shortestdistance()
{/*要查找的两景点的最短距离*/
int i,j;
printf("请输入要查询的两个景点的编号并用','间隔):");
scanf("%d,%d",&i,&j);
if(i>n||i<=0||j>n||j<0)
{
printf("输入信息错误！\n\n");
printf(" 请输入要查询的两个景点的编号并用','间隔):\n");
scanf("%d,%d",&i,&j);
}
else
{
floyed(); /*用floyed算法求两个景点的最短路径*/
display(i,j); /* 打印两个景点的路径及最短距离 */
}
return 1;
}/*shortestdistance*/
