[数据结构大作业]HBU 河北大学校园导航

校园导航实验报告

1. 问题描述：

以我校为例，设计一个校园导航系统，主要为来访的客人提供信息查询。系统有两类登陆账号，一类是游客，使用该系统方便校内路线查询；一类是管理员，可以使用该系统查询校内路线，可对校园景点路线可编辑。

1. 需求分析：

设计学校的平面图，至少包括10个以上景点（场所），每两个景点间可以有不同道路，且路长也可能不同，找出在游人所在景点到其他景点的最短路径，或游人输入的任意两个景点的最短路径。

1. 要求
   （1） 以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，路径权重为路径长度。
   （2） 为游人提供任意景点相关信息查询。
   （3）为游人提供任意景点的问路查询，即任意两个景点之间的最短路径。

4.说明书：

本程序实现了两种身份：游客和管理员

其中，游客无登录密码，因为其只有查询功能，谁来查询都一样

查询内容包括：任意两点间距离和某个景点的相关信息

管理员 登录密码为：jiangzhiyu

除游客包括的功能外，还包括增删节点，增删路径，修改景点简介

5.功能实现：

邻接矩阵保存图

每个景点用一个结构体保存其名字和简介

用哈希表将景点和编号连起来

用Floyd算法实现求解多源多汇最短路

6.调试与解决问题

将所有输入都输入字符串，虽然数字需要在进一步进行转换，但是这样程序健壮性就得以保证。

最短路问题解决较为简单，大部分时间在增加程序健壮性了。

7.源代码：

#include<bits/stdc++.h>using namespace std;const int N = 110;//存图int idx=12;//当前有多少景点int g[N][N];int gc[N][N];//存景点struct scenic_spot {string name;//相关信息string introduction;}spot[N];map<string, int> mp;//初始化图中点的信息void Init_scenic() {spot[1].name = "体检中心";spot[2].name = "操场";spot[3].name = "校门北口";spot[4].name = "银杏景观";spot[5].name = "邯郸音乐厅";spot[6].name = "图书馆";spot[7].name = "餐厅";spot[8].name = "网计学院";spot[9].name = "信息学部";spot[10].name = "花园景观";spot[11].name = "校门东口";spot[12].name = "校门南口";for (int i = 1; i <= idx; i++)mp[spot[i].name] = i;spot[1].introduction = "虽然是体检中心，但我感觉都没怎么去过";spot[2].introduction = "风雨操场，新建的体育馆特别棒";spot[3].introduction = "用来连接教学区和生活区";spot[4].introduction = "秋天落叶非常美，一定要来看看";spot[5].introduction = "没去过，不知道";spot[6].introduction = "很大很豪华，学习氛围超级好，很适合学习";spot[7].introduction = "三层餐厅，尚饮食堂";spot[8].introduction = "网计学院yyds";spot[9].introduction = "没去过";spot[10].introduction = "挺好看的，就是离得有点远";spot[11].introduction = "现在也用来连接教学区和生活区了";spot[12].introduction = "正门口哦";}//初始化图void Init_Map() {memset(g, 0x3f, sizeof g);g[1][2] = 350, g[2][3] =200, g[3][4] =100, g[1][5] =200, g[2][5] =480, g[5][6] =400;g[2][6] = 280, g[3][7] =100, g[4][7] =100, g[5][8] =500, g[5][9] =500, g[9][10] =150;g[6][10] = 160, g[6][11] =300, g[10][11] =200, g[7][11] =100, g[8][12] =400;g[9][12] = 400, g[10][12] =500, g[11][12] =600;for (int i = 1; i <= idx; i++)for (int j = 1; j <= idx; j++) { if (g[i][j] != 0x3f3f3f3f)g[j][i] = g[i][j]; if (i == j)g[i][j] = 0; }}//初始化多源最短路void Init_MinMap() {for (int i = 1; i <= idx; i++)for (int j = 1; j <= idx; j++) gc[i][j] = g[i][j];for (int k = 1; k <= idx; k++)for (int i = 1; i <= idx; i++)for (int j = 1; j <= idx; j++)gc[i][j] = min(gc[i][j], gc[i][k] + gc[k][j]);}//查询任意两点间距离void check_two() {fflush(stdin);cout << "请输入您的起点：" << endl;string s1, s2;getline(cin, s1);while (mp.count(s1) == 0) {cout << "您输入的景点不存在，请重新输入：" << endl;getline(cin, s1);}cout << "请输入您的终点：" << endl;getline(cin, s2);while (mp.count(s2) == 0) {cout << "您输入的景点不存在，请重新输入：" << endl;getline(cin, s2);}if (gc[mp[s1]][mp[s2]] == 0x3f3f3f3f)cout << "此两点不互通" << endl;else cout << "最短距离为：" << gc[mp[s1]][mp[s2]] << endl;}//查询某个节点的信息void query() {cout << "请输入您感兴趣的景点：" << endl;string s;getline(cin, s);while (mp.count(s) == 0) {cout << "地图中没有这个景点！重新输入：" << endl;getline(cin, s);}int x = mp[s];bool fg = true;for (int i = 1; i <= idx; i++) {if (i == x)continue;if (g[x][i] != 0x3f3f3f3f) {if (fg) {fg = false;cout << "与该景点相邻的景点有：" << endl;cout << spot[i].name << " 相距" << g[x][i] << "米" << endl;}else {cout << spot[i].name << " 相距" << g[x][i] << "米" << endl;}}}if (spot[x].introduction.size() != 0) {cout << "简介：" << endl;cout << spot[x].introduction << endl << endl;}else cout << "无简介" << endl;}//判断是否继续bool goon() {string s;getline(cin, s);while (s.size() != 1 || s[0] - '0' != 1 && s[0] - '0' != 2) {cout << "请输入1或者2，不要捣乱！" << endl;getline(cin, s);}if (s[0] - '0' == 1)return true;return false;}//增加一个点void add_spot() {cout << "请输入您要加入的景点名称：" << endl;string s;getline(cin, s);while (s.size()==0) {cout << "输入不能为空" << endl;getline(cin, s);}while (mp.count(s) != 0) {cout << "这个景点我们已经添加过了！重新输入：" << endl;getline(cin, s);}mp[s] = ++idx;spot[idx].name = s;cout << "接下来请您输入与此景点直接相连的景点名称及路径长度(注意：名称和长度输入完各自按回车)" << endl;cout << "如果您输入完了，请输入“no”" << endl;string s1="";int dist=0;getline(cin, s1);while (s.size() == 0) {cout << "输入不能为空" << endl;getline(cin, s);}while (s1 != "no") {if (mp.count(s1) == 0) {cout << "这个景点名称错误，它并没有出现在已有地图中，请您重新输入：" << endl;getline(cin, s1);continue;}string ss;getline(cin, ss);bool st = true;while (true) {if (ss.size() == 0) { getline(cin, ss); continue; }for (int i = 0; i < ss.size(); i++)if (!isdigit(ss[i]))st = false;if (st)break;else {cout << "请输入一个整数：" << endl;st = true;getline(cin, ss);}}for (int i = 0; i <ss.size(); i++) {dist *= 10;dist += ss[i] - '0';}g[mp[s1]][idx] = g[idx][mp[s1]] = dist;cout << "新路径添加成功,请继续" << endl;getline(cin, s1);}Init_MinMap();}//删除一个点void del_spot() {fflush(stdin);cout << "请输入您要删除的景点名称：" << endl;string s;getline(cin, s);while (mp.count(s) == 0) {cout << "地图中没有这个景点！重新输入：" << endl;getline(cin, s);}int x = mp[s];for(int i=1;i<=idx;i++)for (int j = 1; j <= idx; j++) {if (i == x || j == x)g[i][j] = 0x3f3f3f3f;}Init_MinMap();mp.erase(s);}//增加一条路径void add_road() {fflush(stdin);cout << "请输入您要增加路径的起点：" << endl;string s1,s2;getline(cin, s1);while (mp.count(s1) == 0) {cout << "地图中没有这个景点！重新输入：" << endl;getline(cin, s1);}cout << "请输入您要增加路径的终点：" << endl;getline(cin, s2);while (mp.count(s2) == 0) {cout << "地图中没有这个景点！重新输入：" << endl;getline(cin, s2);}if (g[mp[s1]][mp[s2]] != 0x3f3f3f3f) {cout << "地图中已有路径，是否覆盖？" << endl;cout << "1.覆盖   2.重新选择景点" << endl;if (goon()) {cout << "请输入路径长度：" << endl;int dist;cin >> dist;g[mp[s1]][mp[s2]] = g[mp[s2]][mp[s1]] = dist;}else { system("cls");  add_road(); }}else {cout << "请输入路径长度：" << endl;int dist;cin >> dist;g[mp[s1]][mp[s2]] = g[mp[s2]][mp[s1]] = dist;}}//删除一条路径void del_road() {fflush(stdin);cout << "请输入您要删除路径的起点：" << endl;string s1, s2;getline(cin, s1);while (mp.count(s1) == 0) {cout << "地图中没有这个景点！重新输入：" << endl;getline(cin, s1);}cout << "请输入您要删除路径的终点：" << endl;getline(cin, s2);while (mp.count(s2) == 0) {cout << "地图中没有这个景点！重新输入：" << endl;getline(cin, s2);}g[mp[s1]][mp[s2]] = 0x3f3f3f3f;}//修改某个点的简介void Modify() {cout << "请问您想修改哪个节点的简介？" << endl;string s, s1;getline(cin, s);while (mp.count(s) == 0) {cout << "地图中没有这个景点！重新输入：" << endl;getline(cin, s);}cout << "请输入其新的简介：" << endl;getline(cin, s1);spot[mp[s]].introduction = s1;}//游客登录void Visitor() {cout << "亲爱的游客，欢迎来到河北大学！我们将为您提供搜索功能" << endl;cout << "请问您想查询什么呢？" << endl;cout << "1.任意两点间距离    2.某个景点的相关信息" << endl;if (goon())check_two();else query();cout << "请问您还要继续搜索吗？" << endl;cout<<"1.继续   2.退出" << endl;string s;getline(cin, s);while (s.size() != 1 || s[0] - '0' != 1 && s[0] - '0' != 2) {cout << "请输入1或者2，不要捣乱！" << endl;getline(cin, s);}if (s[0] - '0' == 1) {Visitor();}}//管理员登录void Admin() {cout << "亲爱的管理员：" << endl;cout << "请输入您所需的功能：" << endl;cout << "1.查询两景点间距离" << endl;cout << "2.增加节点" << endl;cout << "3.删除节点" << endl;cout << "4.增加道路" << endl;cout << "5.删除道路" << endl;cout << "6.修改已有节点信息" << endl;cout << "7.某个景点的相关信息" << endl;string s;getline(cin, s);while (s.size() != 1 || s[0] - '0' <= 0 && s[0] - '0' > 6) {cout << "请按要求输入，不要捣乱！" << endl;getline(cin, s);}if (s[0] - '0' == 1) {check_two();}else if (s[0] - '0' == 2) {add_spot();}else if (s[0] - '0' == 3) {del_spot();}else if (s[0] - '0' == 4) {add_road();Init_MinMap();}else if (s[0] - '0' == 5) {del_road();Init_MinMap();}else if (s[0] - '0' == 6) {Modify();}else {query();}cout << "您还要继续吗？" << endl;cout << "1.继续   2.退出" << endl;if (goon()) {system("cls");Admin();}}//登录void Enroll() {cout << "欢迎使用河北大学导航服务" << endl;cout << "现在是蒋志宇同学为您导航" << endl;cout << "请问您是游客还是管理员：" << endl << "1.游客   2.管理员"<<endl;string s;getline(cin, s);while (s.size() != 1 || s[0] - '0' != 1 && s[0] - '0' != 2) {cout << "请输入1或者2，不要捣乱！" << endl;getline(cin, s);}system("cls");if (s[0] - '0' == 1) {Visitor();}else {cout << "请输入密码：" << endl;string s;getline(cin, s);while (s != "jiangzhiyu") {cout << "密码错误，重新输入：" << endl;getline(cin, s);}system("cls");Admin();}}int main() {//初始化Init_scenic();Init_Map();Init_MinMap();//登录Enroll();return 0;}