程序设计实训：校园导游模拟程序的设计
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<j)
{
printf("%d",b);
while(path[i][j]!=0)//当i,j之间有最短路径时
{/* 把i到j的路径上所有经过的景点按逆序打印出来*/
printf("<–%d",path[i][j]);
if(i<j)
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)
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*/
void DFS(int k,int v1,int t,int cost[MAXSIZE][MAXSIZE])
{//k为当前景点编号,v1为终点编号,t为当前已经找到的以k为终点的路径上景点的个数
int i;
if(k==v1)//当前景点即为终点
{
for(int j=1;j<t;j++)
printf("%d–>",T[j]);
printf("%d\n",T[t]);
return ;
}
for(i=1;i<=n;i++)
if(!Visit[i]&&cost[k][i]<INT_MAX)//i为k的邻接点
{
Visit[i]=true;
T[t+1]=i; //i为路径上的第t+1个景点
DFS(i,v1,t+1,cost); //递归调用
Visit[i]=false;//释放
}
}
Status Allpath(int cost[MAXSIZE][MAXSIZE],int v0,int v1) //两点间的所有路径
{
int i;
if(v0==v1)
{
printf("输入有错,两点为同一点！\n");
return ERROR;
}
for(i=1;i<=n;i++)
Visit[i]=false;//初始化
Visit[v0]=true;
T[1]=v0;
DFS(v0,v1,1,cost);
return OK;
}
Status ShowAll(Graph p[MAXSIZE]) //显示所有信息
{
int i;
for(i=1;i<=n;i++)
{
printf("%-4d ",p[i].num);
printf("%-20s ",p[i].name);
printf("%-80s\n",p[i].info);
}
return OK;
}
Status IntroduceView(Graph p[MAXSIZE]) //查询景点信息
{
int t;
printf("请输入要查询景点的编号：");
scanf("%d",&t);
while(t<0||t>=n)
{
printf("您输入的景点不存在，请重新输入：");
scanf("%d",&t);
}
printf("%d ",p[t].num);
printf("%s ",p[t].name);
printf("%s\n",p[t].info);
return OK;
}
Status InsertView(Graph p[MAXSIZE],int cost[MAXSIZE][MAXSIZE])
{//n为导游图中已含景点个数 插入景点
int j,t;
p[n+1].num=n+1;
printf("请输入新增景点的名称：");
scanf("%s",&p[n+1].name);
printf("请输入新增景点的信息：");
scanf("%s",&p[n+1].info);
printf("输入与%d存在路径的景点编号及路径长度（以'0'结束）\n",n+1);
scanf("%d",&j);
while(j!=0)
{
scanf("%d",&t);
cost[n+1][j]=t;
cost[j][n+1]=t;
scanf("%d",&j);
}
n++;
return OK;
}
Status DeleteView(Graph p[MAXSIZE],int cost[MAXSIZE][MAXSIZE])//删除景点,n为现有景点的个数
{
int t,i,j;
printf("请输入要删除的景点编号：(1~%d)",n);
scanf("%d",&t);
if(t<0||t>n)
{
printf("该景点已经不存在！");
return OK;
}
for(i=t+1;i<=n;i++) //将删除的景点后面的景点向前移
{
p[i-1].num=i-1;
strcpy(p[i-1].name,p[i].name);
strcpy(p[i-1].info,p[i].info);
}
for(i=t+1;i<=n;i++)//改变删除的景点后面的景点与其余景点之间的道路长度
{
for(j=1;j<=n;j++)
cost[i-1][j]=cost[i][j];
}
for(i=1;i<=n;i++)
{
for(j=t+1;j<=n;j++)
cost[i][j-1]=cost[i][j];
}
n–;
return OK;
}
Status UpdateUiew(Graph p[MAXSIZE]) //更新景点信息
{
int t;
printf("请输入要更新景点的编号:");
scanf("%d",&t);
if(t<1||t>n)
{
printf("该景点不存在，无法更新！\n");
return OK;
}
printf("%d ",p[t].num);
printf("%s ",p[t].name);
printf("%s\n",p[t].info);
printf("请输入更新后景点的名称：");
scanf("%s",&p[t].name);
printf("请输入更新后景点的信息：");
scanf("%s",&p[t].info);
return OK;
}
Status UpdatePath(int cost[MAXSIZE][MAXSIZE]) //更新道路
{
int t,v1,v2;
printf("请输入要更新道路两端景点的编号并用','间隔：");
scanf("%d,%d",&v1,&v2);
while(v1==v2)
{
printf("两顶点为同一个顶点，请重新输入：");
scanf("%d%d",&v1,&v2);
}
printf("请输入道路更新后的长度：");
scanf("%d",&t);
cost[v1][v2]=t;
cost[v2][v1]=t;
return OK;
}
void main()
{/*主函数*/
Graph p[MAXSIZE]={{0,"",""},
{1,"北门", "330公交车附近"},
{2,"红楼","儿童研究中心，有5L"},
{3,"精业楼","行知学院教学大楼,有9L"},
{4,"初阳湖","人造湖很漂亮"},
{5,"杏园食堂","东西一般好吃"},
{6,"艺术大楼","艺术生的圣地"},
{7,"大学生活动中心","大学生陶冶情操的地方"},
{8,"图文信息中心","豪华图书馆在学校大门附近"},
{9,"体育馆","学校体育馆，运动健儿的圣地"},
{10,"学校正大门","一楼为快餐 二楼为自助餐 三楼是乒乓球馆."},
};
char k;
int v0,v1;
n=10;
ViewInfo(cost);
printf("—————-欢迎使用浙江师范导游系统!———————————–\n");
printf("1.景点信息查询…………请按 i (introduce)键\n");
printf("2.景点间最短路径查询…请按 s (shortestdistance)键\n");
printf("3.查看浏览路线…请按 w (wholedistance)键\n");
printf("4.增加景点信息…………请按 a (add)键\n");
printf("5.删除景点信息…………请按 d (delete)键\n");
printf("6.更新景点及道路信息…请按 u (update)键\n");
printf("7.显示所有景点信息……请按 p (print)键\n");
printf("8.退出系统………………请按 e (exit)键\n");
printf("学校景点列表:\n");
printf("》》");
printf("|1:北门|2:红楼|3:精业楼|4:初阳湖 |");
printf("|5:杏园食堂|6:艺术大楼 |7:大学生活动中心|8:图文信息中心|");
printf("|9: 体育馆|10:学校正大门|");
printf("》》");
while(1)
{
printf("\n请选择服务:");
scanf("\n%c",&k);
switch(k)
{
case 'i':
printf("进入景点信息查询:");
IntroduceView(p);
break;
case 's':
printf("进入最短路径查询:");
shortestdistance();
break;
case 'w':
printf("进入所有路径查询:");
printf("请输入要查询的两个景点的编号并用','间隔");
scanf("%d,%d",&v0,&v1);
Allpath(cost,v0,v1);
break;
case 'a':
printf("增加景点信息:");
InsertView(p,cost);
break;
case 'd':
printf("删除景点信息");
DeleteView(p,cost);
break;
case 'u':
printf("更新景点信息:");
UpdateUiew(p);
UpdatePath(cost);
break;
case 'p':
printf("显示所有景点信息:\n");
ShowAll(p);
break;
case 'e':
printf("退出系统!");
exit(0);
default:
printf("输入信息错误！\n请输入正确的字母来选择服务.\n");
break;
}
}
}/*main*/
测试图片
