校园导航系统
项目文件
- config.h 定义了数据的宏
- SchoolGraph.h
- SchoolGraph.cpp 校园导航的图类
- school-map.cpp 程序主类
config.h
x
/* CONFIG_H */SchoolGraph.h
xxxxxxxxxx/******************************************************************************* File: SchoolGraph.h** Author: Chenrenhao* Created: 11/24/21* Description:* 图类的声明：* 1.使用一维数组储存定点元素，使用领接矩阵储存边,领接矩阵中的值表示距离（权重）;* 2.图类具有的属性：* （1）储存定点的数组;* （2）储存边的领接矩阵;* (3) 顶点数和边数;* (4) 最短路径矩阵以及路线矩阵；* 3.图具有的方法：* （1) 构造函数：构造具有n个定点的图;* (2) 输出各个顶点的信息* （3）输出各个边的信息* （2）输出任意两个顶点间的距离,这里的距离都定义为整数;* (3) 修改任意亮点间的距离;* （4）获取任意两点之间的最短距离(非领接定点之间距离不允许修改);*****************************************************************************///图的顶点最多有20个//定义一个无穷大表示两个定点之间没有连接
class SchoolGraph{public: //构造函数：构造具有n个定点的图,并向图提供定点和边的信息以供初始化 SchoolGraph(int n,std::string vertex[],int **arc); SchoolGraph(); //输出各个顶点的信息 void showVertexs(); //输出各边的信息 void showArc(); //输出任意两个顶点的距离,参数为顶点在vertex数组的下标 int distance(int begin, int end); //修改亮点间的距离,前两个参数为顶点在vertex数组中的下标，最后一个参数为修改后的距离 bool modifyDistance(int begin,int end,int dis); //获取两点之间最短距离 int minDistance(int begin,int end);
//存放定点的数组 std::string vertex[MAX_COUNT]; //输出路线 void fromTo(int begin,int end);private: //最短路线矩阵 int path[MAX_COUNT][MAX_COUNT]; //最短路径矩阵 int minArc[MAX_COUNT][MAX_COUNT]; //存放边的矩阵 int arc[MAX_COUNT][MAX_COUNT]; //顶点数和边数 int vertexNum = 0; int arcNum;};/* SCHOOLGRAPH_H */SchoolGraph.cpp
xxxxxxxxxx/******************************************************************************* File: SchoolGraph.cpp** Author: Chenrenhao* Created: 11/24/21* Description: 图类的定义*****************************************************************************///构造函数默认认为参数均正确，在其他地方会对参数的合理性进行判断SchoolGraph::SchoolGraph(){}SchoolGraph::SchoolGraph(int n,std::string vertex[],int **arc){ //顶点数初始化 this->vertexNum = n; //顶点信息初始化 for(int i = 0;i < n;i++) { this->vertex[i] = vertex[i]; for(int j = 0;j < n;j++) { this->arc[i][j] = *((int*)arc + i*n + j); } } //遍历算出arcNum int arcNum = 0; for(int i = 0;i < this->vertexNum;i++) { for(int j = 0;j< this->vertexNum;j++) { if(this->arc[i][j] != 0 && this->arc[i][i] != INF) arcNum++; } } this->arcNum = arcNum;}/******************************************************************************* Function: showVertexs* Description: 输出各个定点的信息*****************************************************************************/void SchoolGraph::showVertexs(){ for(int i = 0;i < this->vertexNum;i++) { std::cout<<this->vertex[i]<<std::endl; }}/******************************************************************************* Function: showArc* Description: 输出各个边的信息*****************************************************************************/void SchoolGraph::showArc(){ for(int i = 0;i < this->vertexNum - 1;i++) { for(int j = i + 1; j < this->vertexNum;j++) { if(this->arc[i][j] != INF) std::cout<<this->vertex[i]<<" 到 "<<vertex[j]<<" 的距离是："<<this->arc[i][j]<<std::endl; } }}/******************************************************************************* Function: minDistance* Description: 求两点之间最短路径*****************************************************************************/int SchoolGraph::minDistance(int begin, int end){ //floyd算法求最短路径 //初始化两个矩阵 for(int i = 0;i < this->vertexNum;i++) { for(int j = 0;j< this->vertexNum;j++) { this->minArc[i][j] = this->arc[i][j]; this->path[i][j] = j; } } for(int k = 0;k < this->vertexNum;k++) { for(int i = 0;i < this->vertexNum;i++) { for(int j = 0;j < this->vertexNum;j++) { if(i != j && (this->minArc[i][j] > (this->minArc[i][k] + this->minArc[k][j]))) { this->minArc[i][j] = this->minArc[i][k] + this->minArc[k][j]; this->path[i][j] = k; } } } } return this->minArc[begin][end];
}/******************************************************************************* Function: SchoolGraph::fromTo(int begin ,int end)* Return:* Error:*****************************************************************************/void SchoolGraph::fromTo(int begin ,int end){ if(this->path[begin][end] == end) { return; } fromTo(begin,this->path[begin][end]); std::cout<<"-->"<<this->vertex[this->path[begin][end]]; fromTo(this->path[begin][end],end);}/******************************************************************************* Function: distance* Description: 求两个定点之间的距离，返回所求结果，并没有进行输出*****************************************************************************/
int SchoolGraph::distance(int begin,int end){ //如果两点之间不存在连接则计算最短路径 if(this->arc[begin][end] == INF) { //如果不存在最短路径则返回INF if(minDistance(begin,end) == INF) return INF; return minDistance(begin,end); }else{//如果两点之间存在连接则直接返回arc矩阵中的记录值 return this->arc[begin][end]; }}/******************************************************************************* Function: modifyDistance* Description: 修改两点距离*****************************************************************************/bool SchoolGraph::modifyDistance(int begin,int end,int dis){ try { this->arc[begin][end] = dis; this->arc[end][begin] = dis; }catch(int){ return false; } return true;}school-map.cpp
xxxxxxxxxxusing namespace std;SchoolGraph graph;void map(){cout<<"+————————————————————————————————————————————————————————————————————————————————+\n";cout<<"| +——+ 10X——————————————————X8—————————————————————X7 +——+ |\n";cout<<"| |研| | +———+————+ | |材| |\n";cout<<"| +——————————+ |究| | |餐饮场所| | |料| |\n";cout<<"| |校外体育场| |生| | +———+————+ | |楼| |\n";cout<<"| +——————————+ |公| | | | +——+ |\n";cout<<"| |寓| | | | |\n";cout<<"| +——+ | | +——+ | |\n";cout<<"| | | |宿| | |\n";cout<<"| | | |舍| | |\n";cout<<"| | +————————+ | |楼| | |\n";cout<<"| +————————+ | |AB篮球场| | +——+ | +——+ |\n";cout<<"| |教学D楼 | | +————————+ | | |冶| |\n";cout<<"| +————————+ 11X————————————————————X9 ———————————————————6X |金| |\n";cout<<"| 12X——————————————————+ |——————————| | |楼| |\n";cout<<"| | | |振华图书馆| | +——+ |\n";cout<<"| | | |——————————| | |\n";cout<<"| | | | +——+ |\n";cout<<"| +——+ | +——+ | | |鸟| |\n";cout<<"| |艺| | |机|14X +——————————————————+ 5X |笼| |\n";cout<<"| |设| X13———————————|械|——+ | 宿 舍 楼 | | |篮| |\n";cout<<"| |楼| | |楼| | +——————————————————+ | |球| |\n";cout<<"| +——+ | +——+ | | |场| |\n";cout<<"| | | | +——+ |\n";cout<<"| | | +——————————+ | +——+ |\n";cout<<"+————————+ +——+ | | 南 北 教 | | |体| |\n";cout<<"|小吃广场| |电| | +——————————+ | |育| |\n";cout<<"+————————+ |气| X16 —————————————————— 2X———————————————————3X|馆| |\n";cout<<"| | |楼| | | +——+ |\n";cout<<"| 15X +——+ | +——————————+ | |\n";cout<<"| +——————+ +——————————————| 学校正门 |—————————————————X4 |\n";cout<<"| |逸夫楼| +——————————+ +————————+\n";cout<<"| +——————+ 1X | 阶教 |\n";cout<<"+———————————————————————————————————————————————————————————————————————+————————+\n";cout<<endl;}/*map*///绘制菜单void drawMenu(){ cout<<"[------欢迎进入校园导航系统!------------]" <<endl; cout<<"[---------------------------------------]" <<endl; cout<<"[---------------------------------------]" <<endl; cout<<"[---------1.显示地图--------------------]" <<endl; cout<<"[---------2.输出顶点信息----------------]" <<endl; cout<<"[---------3.输出边的信息----------------]" <<endl; cout<<"[---------4.修改两点距离----------------]" <<endl; cout<<"[---------5.求最短路径------------------]" <<endl; cout<<"[---------0.退出程序--------------------]" <<endl; cout<<"[---------------------------------------]" <<endl; cout<<"[---------------------------------------]" <<endl; cout<<"请输入你的操作：";}void initilize(){ string vertex[16] = _VERTEX_; int arc[16][16] = _ARC_; SchoolGraph gr(16,vertex,(int**)arc); graph = gr;}void run(){ bool run = true; while(run) { int ch; drawMenu(); cin>>ch; switch(ch) { case 1: { system("clear"); map(); break; } case 2: { system("clear"); cout<<"顶点信息如下："<<endl; graph.showVertexs(); break; } case 3: { system("clear"); cout<<"边的信如下："<<endl; graph.showArc(); break; } case 4: { system("clear"); map(); cout<<"输入你要修改的两个地点的序号和修改后的距离"<<endl; int begin,end,dis; cin>>begin; cin>>end; cin>>dis; graph.modifyDistance(begin-1,end-1,dis); cout<<"已修改信息！"<<endl; break; } case 5: { system("clear"); map(); cout<<"请输入两地代号："<<endl; int begin,end; cin>>begin; cin>>end; if(begin <= 0||begin > 16 || end <= 0 ||end > 16) { cout<<"输入错误！"<<endl; break; } int min = graph.minDistance(begin-1,end-1); cout<<graph.vertex[begin-1]<<"到"<<graph.vertex[end-1]<<"的最短距离为："<<min<<endl; cout<<graph.vertex[begin-1]; graph.fromTo(begin-1,end-1); cout<<"-->"<<graph.vertex[end-1]<<endl; break; } case 0: { run = false; break; } default: { cout<<"输入错误！"<<endl; drawMenu(); break; } } }}//在文件中读取地图信息int main(){ /* map(); */ initilize(); run(); return 0;}运行截图
