校园导航问题（河大版）
版权声明：本文为博主原创文章，遵循 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 << "\n\t\t 欢迎进入河北大学校园导航系统\n\n";
cout << "\t\t『1』 -------------------------- 以管理员身份登录\n\n";
cout << "\t\t『2』 -------------------------- 以游客身份进入\n\n";
cout << "\t\t『0』 -------------------------- 退出\n\n";
cout << "\t\t请输入您选择的序号：";
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] = '\0';
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 << "\n\t\t 欢迎进入河北大学校园导航系统\n\n";
cout << "\t\t 您的身份是管理员\n\n";
cout << "\t\t『1』 -------------------------- 添加校园地点\n\n";
cout << "\t\t『2』 -------------------------- 添加校园路径\n\n";
cout << "\t\t『3』 -------------------------- 查询校园所有地点信息\n\n";
cout << "\t\t『4』 -------------------------- 查询校园任一地点信息\n\n";
cout << "\t\t『5』 -------------------------- 查询某一地点到其他地点的最短路径\n\n";
cout << "\t\t『6』 -------------------------- 查询俩点间的最短路径\n\n";
cout << "\t\t『7』 -------------------------- 删除校园地点\n\n";
cout << "\t\t『8』 -------------------------- 删除校园路径\n\n";
cout << "\t\t『9』 -------------------------- 修改校园地点信息\n\n";
cout << "\t\t『0』 -------------------------- 退出\n\n";
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 << "\n\t\t 欢迎进入河北大学校园导航系统\n\n";
cout << "\t\t 您的身份是游客\n\n";
cout << "\t\t『1』 -------------------------- 查询校园所有地点信息\n\n";
cout << "\t\t『2』 -------------------------- 查询校园任一地点信息\n\n";
cout << "\t\t『3』 -------------------------- 查询某一地点到其他地点的最短路径\n\n";
cout << "\t\t『4』 -------------------------- 查询俩点间的最短路径\n\n";
cout << "\t\t『0』 -------------------------- 退出\n\n";
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();
}