一、需求分析
(1)设计校园平面图,其中所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息:以边表示路径,存放路径长度等相关信息;
(2)为来访客人提供图中任意景点相关信息的查询;
(3)为来访客人提供途中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。
1、由百度地图截图并通过自己标注得图如下:
![](https://img-blog.csdnimg.cn/90b9437abf6047678ae9746bcfc4974f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5qG255qE5aWH5aaZ5YaS6Zmp,size_20,color_FFFFFF,t_70,g_se,x_16)
2、通过杭电距离图得出相应点的距离:
![](https://img-blog.csdnimg.cn/b4017033a5a747648e1d6561a53d9cb3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5qG255qE5aWH5aaZ5YaS6Zmp,size_20,color_FFFFFF,t_70,g_se,x_16)
二、概要设计:
1.抽象数据类型图的定义如下:ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。
数据关系R:R={VR}
VR-{(v,w)| v,wEv,v,w)表示v和w之间存在路径}
基本操作P:
CreateGraph (&G,V, VR)
初始条件:V是图的顶点集,VR是图中边的集合。操作结果:按V和VR的定义构造图G。
DestroyGraph(&G)
初始条件:图G存在。操作结果:销毁图G。
LocateVex (G,u)
初始条件:图G仔在,u和G中顶点有相同特征。
2、主程序
int main()
{
定义变量并初始化;
While (1);
创建校园地图;
选择导航功能;
输出距离;
};
三、详细设计
1、顶点,边和图类型
#define INF 999999
#define M 20
int dist[M][M];///距离
int path[M][M];///路径
int Stack[M];///路径栈
int top;///栈顶
int counts;///记录路径数
int visited[M];///标记数组
struct vertex///景点信息结构体
{
int num;///景点编号
char name[20];///景点名称
char info[300];///景点介绍
};
struct maps
{
int n;///点数
int m;///边数
vertex v[M];
int edgs[M][M];///邻接矩阵
} g; ///景点图的结构体
图的基本操作:
void Creat_vertex() 创建景点信息结构体
void Creat_maps() 创建校园地图
void Search_info() 查找校园景点信息
void Floyd() 用弗洛伊德算法计算最短路径
void Floyd_print(int s, int e) 打印最短路径
void Dfs_allpath(int s,int e) 用DFS算法遍历所有路径
void Bestpath_Multispot() 多景点的最短路径计算
void Dis_menu() 菜单展示
void Creat_vertex()
{
g.v[0].num=1;
strcpy(g.v[0].name,"图书馆");
strcpy(g.v[0].info,"丰富的藏书资源");
g.v[1].num=2;
strcpy(g.v[1].name,"体育馆");
strcpy(g.v[1].info,"杭州亚运会击剑馆,学生长跑打卡点");
g.v[2].num=3;
strcpy(g.v[2].name,"六教");
strcpy(g.v[2].info,"第六教学楼");
g.v[3].num=4;
strcpy(g.v[3].name,"四教");
strcpy(g.v[3].info,"这是学校的第四教学楼");
g.v[4].num=5;
strcpy(g.v[4].name,"二教");
strcpy(g.v[4].info,"自动化学院,电子学院,机械学院");
g.v[5].num=6;
strcpy(g.v[5].name,"一教");
strcpy(g.v[5].info,"计算机学院");
g.v[6].num=7;
strcpy(g.v[6].name,"三教");
strcpy(g.v[6].info,"外国语学院");
g.v[7].num=8;
strcpy(g.v[7].name,"七教");
strcpy(g.v[7].info,"第七教学楼,设备新颖");
g.v[8].num=9;
strcpy(g.v[8].name,"十二教");
strcpy(g.v[8].info,"一般上公共课的地方");
g.v[9].num=10;
strcpy(g.v[9].name,"十一教");
strcpy(g.v[9].info,"圣光机学院");
g.v[10].num=11;
strcpy(g.v[10].name,"十教");
strcpy(g.v[10].info,"卓越学院,国际教育学院");
g.v[11].num=12;
strcpy(g.v[11].name,"九教");
strcpy(g.v[11].info,"经济,会计,人艺数法学院");
g.v[12].num=13;
strcpy(g.v[12].name,"学生活动中心");
strcpy(g.v[12].info,"这是举办文艺活动的场所");
}
void Creat_maps()
{
int i,j;
g.n=13;///13个景点
g.m=18;///18条双向路径
for(i=0; i |