版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/shiliang97/article/details/103339031
校园导航问题
GitHub源码地址:https://github.com/HANXU2018/data-structure-HBUGuide
以我校为例,设计一个校园导航系统,主要为来访的客人提供信息查询。系统有两类登陆账号,一类是游客,使用该系统方便校内路线查询;一类是管理员,可以使用该系统查询校内路线,可对校园景点路线可编辑。
设计学校的平面图,至少包括10个以上景点(场所),每两个景点间可以有不同道路,且路长也可能不同,找出在游人所在景点到其他景点的最短路径,或游人输入的任意两个景点的最短路径。 要求: (1) 以图中顶点表示校园内各景点,存放景点名称、代号、简介等信息;以边表示路径,路径权重为路径长度。 (2) 为游人提供任意景点相关信息查询。 (3)为游人提供任意景点的问路查询,即任意两个景点之间的最短路径。
text
实现提示: 一般情况下,校园道路是双向通行的,可设计校园平面图是一个无向图。顶点和边均含有相关信息。 选做内容: (1)提供图的编辑功能:增删景点;增删道路;修改已有信息等。 (2)校园导游图的仿真界面。
text
text
1. 抽象数据类型定义:
(1)景点 顶点名称 代号 顶点信息简介
Typedef struct{
Int num;
Char name[100];
Char features[200];
} VertexType;
(2)图的存储结构:
Typedef int EdgeType;
Typedef struct{
VertexType vexs[MaxVertexNum];
EdgeType edges[MaxVertexNum][MaxVertexNum];
Int n, e;
} MGraph;
2 主要功能模块
(1)创建图的邻接矩阵存储结构 create() (2) 浏览图中任一景点介绍 (3) 修改景点信息 (4) 增加景点信息 (5) 删除景点信息 (6) 增加道路 (7) 删除道路 (8) 查找某一景点到其他景点的最短路径 (9) 查找任一两个景点之间的最短路径。
//景点介绍
void introduct (void){
return;
}
//查找游客所在景点与其他景点的距离
void Dijkstra(void){
return;
}
//查找游客指定的两个景点间的最短路径长度
void Floyd(void){
return;
}
//修改景点信息
void modifyInfo(void){
return;
}
//添加景点
void addInfo(void){
return;
}
//删除景点
void delInfo(void){
return;
}
//添加道路
void addPath(void){
return;
}
//删除道路
void delPath(void){
return;
}
//生成图
void create(void){
return;
}
3 主模块流程
管理员登陆,可实现(1)-(9)功能操作 游客登陆,在(1)基础实现基础之上,可实现 (2)(8)(9)功能操作
printf("请输入您的密码:");
char password[PASSWORDLENGTH];
scanf("%s",password);
getchar();//一定要吃回车,不然影响下一次输入
if(strcmp(password, PASSWORD)==False) {
printf("密码正确,即将进入系统\n");
Administrator();//转入超级管理员界面
}else{
system("cls");
printf("----------密码错误---------\n");
printf("系统将在1S后回到主面板");
Sleep(1000);
system("cls");
}
break;
default:
printf("即将在1s后退出系统,感谢您的使用。");
Sleep(1000);
return 0;
Typedef struct{
Int num;
Char name[100];
Char features[200];
} VertexType;
(2)图的存储结构:
Typedef int EdgeType;
Typedef struct{
VertexType vexs[MaxVertexNum];
EdgeType edges[MaxVertexNum][MaxVertexNum];
Int n, e;
} MGraph;
时间复杂度 n* n 空间复杂度 存储信息 n * n
登录界面
游客界面
管理员登录
管理员系统
景点描述
最短路径查询
删除功能