校园导航问题（河大版）
- 2019 年 11 月 8 日
- 筆記
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/85266144
【问题描述】
以我校为例，设计一个校园导航系统，主要为来访的客人提供信息查询。系统有两类登陆账号，一类是游客，使用该系统方便校内路线查询；一类是管理员，可以使用该系统查询校内路线，可对校园景点路线可编辑。
【需求分析】
设计学校的平面图，至少包括10个以上景点（场所），每两个景点间可以有不同道路，且路长也可能不同，找出在游人所在景点到其他景点的最短路径，或游人输入的任意两个景点的最短路径。
要求：
（1） 以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，路径权重为路径长度。
（2） 为游人提供任意景点相关信息查询。
（3）为游人提供任意景点的问路查询，即任意两个景点之间的最短路径。
实现提示：
一般情况下，校园道路是双向通行的，可设计校园平面图是一个无向图。顶点和边均含有相关信息。
选做内容：
（1）提供图的编辑功能：增删景点；增删道路；修改已有信息等。
（2）校园导游图的仿真界面。
【概要设计】
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）创建图的邻接矩阵存储结构 void create( Graph *G );
（2） 浏览图中任一景点介绍 VertexType GetVex(Graph *G, int v);
（3） 修改景点信息 void PutVertex(Grahp *G, int v);
（4） 增加景点信息 void InsertVertex(Graph*G, VertexType v);
（5） 删除景点信息 void DeleteVertex(Graph *G, VertexType v);
（6） 增加道路 void InsertArc(Graph *G,int v, int w);
（7） 删除道路 void DeleteArc(Graph*G ,int v,int w);
（8） 查找某一景点到其他景点的最短路径 void ShortestPath(Graph *G, int P[ ], int D[ ]);
（9） 查找任一两个景点之间的最短路径。Void ToDestination(Graph *G, int v, int w);
3. 主模块流程
管理员登陆，可实现（1）-（9）功能操作
游客登陆，在（1）基础实现基础之上，可实现 （2）（8）（9）功能操作
一些瞎扯淡的话：
额，数据结构老师给定的抽象数据类型定义和主要功能模块让我感jio有点难受啊。我用C++写的，然后所有的自定义函数都没按照老师的来，名字不一样参数也不一样，不过并不影响功能实现，最后是800多行 27311个字节。上周给老师检查的时候，老师运行程序之后先看到了1314ms的羊驼界面（我忍笑…这个羊驼界面真实地表达了我对这个大作业的真情实感，羊驼只对大作业哦，老师还是挺好的！）。
老师说“这个还挺有趣的哈，不过神兽也救不了你。”然后老师问我“账号密码是啥？”我：“打开那个记事本，里面存了管理员的账号密码，只有我们俩个晓得哦，不要把密码告诉别人哦（一脸Just kidding的表情）。”老师：“诶？为啥我复制粘贴不对？”旁边同学说：“老师您少复制了个小数点。”我正插着腰站在旁边看呢（别问我为啥叉腰！）
老师进入功能菜单界面之后，我说：“老师您别一顿乱敲暴力输入呀，不然又会出现刚刚那个羊驼界面，然后退出程序。只要不暴力输入怎么操作都行！”老师对着键盘疯狂哒哒哒地敲，说：“行，找到一个bug，请我一顿饭啊（老师当然是开玩笑的啦~）”。我：“要得！”（我当时就是这样插着腰站在老师旁边。）
接着老师疯狂吐槽我的查询功能太垃圾了（just kidding），因为我的程序是在用户输入地点名的基础上来实现的，“校门南口”必须完整输入“校门南口”这四个字才能查询到，输入“校门”二字没用，我没有用KMP算法来对字符串子串进行模式匹配，更别说“校门口”这种模糊查询啦。只见老师疯狂敲击键盘进行操作，大概5 6分钟之后，那个价值一顿饭的bug被老师发现了（lol?）！我的天，震惊！老师真的太秀了！下文会还原一波老师找出那个价值连饭的bug时的操作（那个bug已经被我修复了）。
部分代码：
预处理：
#include <bits/stdc++.h> #include <conio.h> #include <windows.h> using namespace std; #define MAX 51 #define INF 9999
顶点结构体如下。
//顶点结构体 typedef struct { int num; //地点序号 string name; //地点名称 string info; //简单得不能再简单的地点简介 }VertexNode;
邻接矩阵结构体，存路径。
//邻接矩阵结构体,存路径 typedef struct { int Edge[MAX][MAX]; //边集 int vn; //顶点数目 int en; //边数目 VertexNode Vex[MAX] = //顶点集 { {1,"体检中心","河北大学体检中心"},{2,"邯郸音乐厅","河北大学邯郸音乐厅"}, {3,"网计学院","河北大学网络空间安全与计算机学院"},{4,"信息学部","河北大学信息学部"}, {5,"操场","河北大学体育场"},{6,"图书馆","河北大学图书馆"}, {7,"花园景观","花园景观"},{8,"校门南口","正对着图书馆的那个校门"}, {9,"校门北口","挨着北街的那个校门"},{10,"校门东口","挨着食堂的那个校门"}, {11,"餐厅","河北大学的食堂,有三层"},{12,"银杏景观","里面很多银杏树,秋天的时候挺好看的"} }; }AdjMatrix;
全局变量的设置。
//全局变量 bool isAdmin; //判断用户身份是不是管理员 bool isFirst = true; //只在第一次创建邻接矩阵的时候为true int weight[MAX][MAX]; AdjMatrix S; //一定要全局变量,不然添加和删除操作会无法实现 AdjMatrix *G; //用一个AdjMatrix 指针指向创建好的邻接矩阵S的地址
写在主函数前的函数声明，只有Create()是引用传参，其他的函数都是指针作形参。
//登录时的主菜单界面 void Login_Menu(); //管理员登录时用的函数 void Admin_Login(); //不可描述的自定义函数 void Alpaca(); //管理员的主菜单界面 void Admin_Menu(); //游客的主菜单界面 void Tour_Menu(); //根据当前状态来返回菜单的函数 void Back_Menu(); //根据地点名称确认地点序号 int Locate(AdjMatrix *G,string name); //采用邻接矩阵创建无向网 void Create(AdjMatrix &G); //添加校园地点 void Insert_Vex(AdjMatrix *G); //添加校园路径 void Insert_Edge(AdjMatrix *G); //查询所有地点信息 void Inquiry_All_Vex(AdjMatrix *G); //查询某一地点信息 void Get_Vex(AdjMatrix *G); //查询某一地点到其他所有地点的最短路径 void Inquiry_Short_Edge(AdjMatrix *G); //查询任意俩点间的最短路径 void Inquiry_A2B_Short_Edge(AdjMatrix *G); //删除校园地点 void Delete_Vex(AdjMatrix *G); //删除校园路径 void Delete_Edge(AdjMatrix *G); //修改校园地点信息 void Modify(AdjMatrix *G);
简洁的主函数。
int main() { Login_Menu(); return 0; }
不可描述的羊驼函数：
//不可描述的函数 void Alpaca() { string str0 = "┌─┐"; string str1 = "┌──┘"; string str2 = "┴───────┘"; string str3 = "┴──┐"; string str4 = "│"; string str5 = "──"; string str6 = "─┬┘"; string str7 = "└┬─"; string str8 = "─┴─"; string str9 = "└───┐"; string str10 = "┌───┘"; string str11 = "└──────────────┐"; string str12 = "├─┐"; string str13 = "┌─┘ "; string str14 = "└─┐"; string str15 = "┐"; string str16 = "┌───────┬──┐"; string str17 = "┌──┘"; string str18 = "┤"; string str19 = "└──┴──┘"; cout << setw(31) << str0 << setw(13) << str0 << endl; cout <<setw(30)<< str1 <<setw(19)<<str2<<setw(9)<<str3<< endl; cout << setw(24) << str4 <<setw(19)<<str4<< endl; cout << setw(24) << str4 << setw(11) <<str5<<setw(10)<< str4 << endl; cout << setw(24) << str4 << setw(19) << str4 << endl; cout << setw(24) << str4 << setw(9) << str6 << setw(11) << str7 << setw(5) << str4 << endl; cout << setw(24) << str4 << setw(19) << str4 << endl; cout << setw(24) << str4 << setw(19) << str4 << endl; cout << setw(24) << str4 << setw(13) << str8 <<setw(9)<<str4<< endl; cout << setw(24) << str4 << setw(19) << str4 << endl; cout << setw(32) << str9 << setw(19)<< str10 << endl; cout << setw(28) << str4 << setw(11) << str4 << endl; cout << setw(28) << str4 << setw(11) << str4 << endl; cout << setw(28) << str4 << setw(11) << str4 << endl; cout << setw(28) << str4 << setw(11) << str4 << endl; cout << setw(28) << str4 << setw(41) << str11 << endl; cout << setw(28) << str4 << setw(26) << str4 << endl; cout << setw(28) << str4 << setw(30) << str12 << endl; cout << setw(28) << str4 << setw(32) << str13 << endl; cout << setw(28) << str4 << setw(26) << str4 << endl; cout << setw(32) << str14 <<setw(4)<<str15<<setw(26)<<str16<<setw(10)<<str17<< endl; cout << setw(30) << str4 <<setw(4)<<str18<<setw(4)<<str18<<setw(9)<<str4<<setw(4)<<str18 <<setw(4)<<str18<< endl; cout << setw(42) << str19 <<setw(21)<<str19<< endl; cout << " " << endl; cout << setw(43) << "神兽保佑"<<endl; cout << " " << endl; cout << setw(43) << "永无bug!" << endl; Sleep(1314); //等待1314ms system("cls"); //清屏 }
登录时的主菜单界面，不管用户选择哪种登录方式，都应该先调用Create函数创建邻接矩阵。
//登录时的主菜单界面 void Login_Menu() { cout << setw(52) << "正在进入河北大学导航系统......" << endl; Alpaca(); //登录前的开场动画 cout << "ntt 欢迎进入河北大学校园导航系统nn"; cout << "tt『1』 -------------------------- 以管理员身份登录nn"; cout << "tt『2』 -------------------------- 以游客身份进入nn"; cout << "tt『0』 -------------------------- 退出nn"; cout << "tt请输入您选择的序号："; int n; while(cin >> n && n != 0) { //创建邻接矩阵 if(isFirst) { Create(S); //Create函数的形参是一个引用 G = &S; isFirst = false; } switch(n) { case 1: Admin_Login(); isAdmin = true; break; //管理员 case 2: Tour_Menu(); isAdmin = false; break; //游客 default: cout << "请输入0~2以内的数字:"; break; //输入0直接退出,我个人觉得没必要再写case0了 } } cout << "正在退出河北大学校园导航系统......" << endl; Alpaca(); exit(0); }
管理员登录时用到的函数，账号和密码是用一个map来存放的，如果需要添加管理员信息操作起来也方便。密码是用getch来输入的，输入密码的同时打印*号。需要注意的是验证密码是否输入正确时，是将map中的value值——一个string型的字符串与用户输入的char*型字符串进行比较，此时应该先用c_str()函数来把string型强制转换成char*型，再用strcmp进行比较。
//管理员登录时用到的函数 void Admin_Login() { map<string,string> m; //map的key值是管理员的账号、value值是管理员的密码 //添加管理员的账号密码信息 m["Student"] = "TYD123456."; m["Teacher"] = "SQX654321."; int count = 3; //账号和密码输入错误的次数不能超过3次 while(count--) { string id; cout << "请输入您的账号：" << endl; cin >> id; int i = 0; char pw[50],ch; cout << "请输入您的密码：" << endl; while((ch = getch()) != 'r') // r是回车符,回到行首 { if(ch == 'b') // b是退格符 { if(i > 0) { printf("b b"); --i; } } else { pw[i++] = ch; printf("*"); } } pw[i] = ' '; cout << endl; bool flag = false; //判断密码是否为真 for(auto it : m) //for-each循环遍历map { //string型可以直接==比较,string型和char*型比较需要将string用c_str()转换后再用strcmp比较 if((it.first == id) && strcmp(it.second.c_str(), pw) == 0) { flag = true; } } if(flag) { isAdmin = true; //是管理员 cout << id << ",恭喜您登录成功。" << endl; Admin_Menu(); } else { isAdmin = false; //不是管理员 if(count == 0) { break; } cout << "您输入的账号或密码错误,请您重新输入。" << endl; } } cout << "连续三次输入错误,您将以游客身份进入校园导航系统,"; system("pause"); Tour_Menu(); }
管理员的功能菜单界面。
//管理员的功能菜单界面 void Admin_Menu() { cout << "ntt 欢迎进入河北大学校园导航系统nn"; cout << "tt 您的身份是管理员nn"; cout << "tt『1』 -------------------------- 添加校园地点nn"; cout << "tt『2』 -------------------------- 添加校园路径nn"; cout << "tt『3』 -------------------------- 查询校园所有地点信息nn"; cout << "tt『4』 -------------------------- 查询校园任一地点信息nn"; cout << "tt『5』 -------------------------- 查询某一地点到其他地点的最短路径nn"; cout << "tt『6』 -------------------------- 查询俩点间的最短路径nn"; cout << "tt『7』 -------------------------- 删除校园地点nn"; cout << "tt『8』 -------------------------- 删除校园路径nn"; cout << "tt『9』 -------------------------- 修改校园地点信息nn"; cout << "tt『0』 -------------------------- 退出nn"; cout << "请输入您选择的序号："; int n; while(cin >> n && n != 0) { switch(n) { case 1: Insert_Vex(G); break; //添加校园地点 case 2: Insert_Edge(G); break; //添加校园路径 case 3: Inquiry_All_Vex(G); break; //查询校园所有地点信息 case 4: Get_Vex(G); break; //查询校园任一地点信息 case 5: Inquiry_Short_Edge(G); break; //查询某一地点到其他地点的最短路径 case 6: Inquiry_A2B_Short_Edge(G); break; //查询俩点间的最短路径 case 7: Delete_Vex(G); break; //删除校园地点 case 8: Delete_Edge(G); break; //删除校园路径 case 9: Modify(G); break; //修改校园地点信息 default: cout << "请输入0~9以内的数字:"; break; //输入0直接退出,我个人觉得没必要再写case0了 } } cout << "正在退出河北大学校园导航系统......" << endl; Alpaca(); }
游客的功能菜单界面。
//游客的功能菜单界面 void Tour_Menu() { cout << "ntt 欢迎进入河北大学校园导航系统nn"; cout << "tt 您的身份是游客nn"; cout << "tt『1』 -------------------------- 查询校园所有地点信息nn"; cout << "tt『2』 -------------------------- 查询校园任一地点信息nn"; cout << "tt『3』 -------------------------- 查询某一地点到其他地点的最短路径nn"; cout << "tt『4』 -------------------------- 查询俩点间的最短路径nn"; cout << "tt『0』 -------------------------- 退出nn"; cout << "请输入您选择的序号："; int n; while(cin >> n && n != 0) { switch(n) { case 1: Inquiry_All_Vex(G); break; //查询校园所有地点信息 case 2: Get_Vex(G); break; //查询校园任一地点信息 case 3: Inquiry_Short_Edge(G); break; //查询某一地点到其他地点的最短路径 case 4: Inquiry_A2B_Short_Edge(G); break; //查询俩点间的最短路径 default: cout << "请输入0~4以内的数字:"; break; //输入0直接退出,我个人觉得没必要再写case0了 } } cout << "正在退出河北大学校园导航系统......" << endl; Alpaca(); }
返回菜单函数。
//根据当前登录状态来返回菜单的函数 void Back_Menu() { if(isAdmin) { Admin_Menu(); } else { Tour_Menu(); } }
采用邻接矩阵来创建无向网时（我是从0开始的而不是1），建立边的关系时需要注意一点：校园路径都是双向的。
//采用邻接矩阵创建无向网 void Create(AdjMatrix &G) { G.vn = 12; //顶点数 G.en = 20; //边数 int i,j,k; //初始化边的信息 for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { G.Edge[i][j] = INF; } } weight[0][1] = 200; //体检中心和邯郸音乐厅间的距离为200 weight[0][4] = 350; //体检中心和操场间的距离为350 weight[1][2] = 500; //邯郸音乐厅和网计学院间的距离为500 weight[1][3] = 500; //邯郸音乐厅和信息学部间的距离为500 weight[1][4] = 480; //邯郸音乐厅和操场间的距离为480 weight[1][5] = 400; //邯郸音乐厅和图书馆间的距离为400 weight[2][7] = 400; //网计学院和校门南口间的距离为400 weight[3][6] = 100; //信息学部和花园景观间的距离为100 weight[3][7] = 400; //信息学部和校门南口间的距离为400 weight[4][5] = 280; //操场和图书馆间的距离为280 weight[4][8] = 200; //操场和校园北口间的距离为200 weight[5][6] = 100; //图书馆和花园景观间的距离为100 weight[5][9] = 300; //图书馆和校门东口间的距离为300 weight[6][7] = 500; //花园景观和校门南口间的距离为500 weight[6][9] = 200; //花园景观和校门东口间的距离为200 weight[7][9] = 600; //校门南口和校门空口间的距离为600 weight[8][10] = 100; //校门北口和餐厅间的距离为100 weight[8][11] = 100; //校门北口和银杏景观间的距离为100 weight[9][10] = 100; //校门东口和餐厅间的距离为100 weight[10][11] = 100; //餐厅和银杏景观间的距离为100 //建立边的关系 int temp; for (i = 0; i < G.vn; i++) { for (j = 0; j < G.vn; j++) { if(weight[i][j]!=0 || weight[j][i]!=0) { if(weight[i][j] != 0) { temp = weight[i][j]; } else { temp = weight[j][i]; } G.Edge[i][j] = temp; G.Edge[j][i] = temp; } } } //查看这个无向图 /* for(i=0;i<G.vn;i++) { for(j=0;j<G.vn;j++) { printf("%d ",G.Edge[i][j]); } cout << endl; } */ }
根据地点名称确认地点编号的Locate函数。
//根据地点名称确认地点编号 int Locate(AdjMatrix *G,string name) { for (int i = 0; i < G->vn; i++) { //若图中含有该地点,则返回其编号 if(G->Vex[i].name == name) { return i+1; } } return -1; //若图中不存在该地地点,则返回-1 }
利用Dijkstra算法查询某一地点到其他所有地点的的最短路径。知道写这个之后，任俩点的最短路径也就简单了。
//查询某一地点到其他所有地点的的最短路径――――Dijkstra算法 已经ok void Inquiry_Short_Edge(AdjMatrix *G) { int start = -2; string name; while(start == -2) { cout << "请输入查询地点名称:"; cin >> name; start = Locate(G,name)-1; } int i,j,k; int D[MAX][MAX]; //D[]表示最短距离 int P[MAX][MAX]; //P[]记录路径 //初始化 for(i = 0; i < G->vn; i++) { for(j = 0; j < G->vn;j++) { D[i][j] = G->Edge[i][j]; P[i][j] = j; } } //Dijkstra算法 for(int k = 0; k < G->vn; k++) { for(int i = 0; i < G->vn; i++) { for(int j = 0; j < G->vn; j++) { if(D[i][j] > D[i][k] + D[k][j]) { D[i][j] = D[i][k] + D[k][j]; P[i][j] = P[i][k]; } } } } //输出 for(j = 0; j < G->vn; j++) { if(j != start && G->Vex[j].num != -1) { printf("从%s到%s的距离是：%d,",G->Vex[start].name.c_str(),G->Vex[j].name.c_str(),D[start][j]); k = P[start][j]; cout << "路径为：" << G->Vex[start].name; while(k != j) { cout << "->" << G->Vex[k].name; k = P[k][j]; } cout << "->" << G->Vex[j].name << endl; } } cout << "即将返回菜单,"; system("pause"); Back_Menu(); }
