【数据结构与算法实验】景区信息管理系统

xiaoxiao2022-07-06 184

任务背景有一个景区，景区里面有若干个景点，景点之间满足以下条件：

某些景点之间铺设了道路(相邻)这些道路都是可以双向行驶的(无向图)从任意一个景点出发都可以游览整个景区(遍历连通图)

景区图如下：景点数据景区的数据包含景点信息和景点之间的道路信息。分别由两个文本文件存储。 Vex.txt文件用来存储景点信息；Edge.txt文件用来存储道路信息。实现代码如下： Main.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include"Graph.h" #include"Tourism.h" using namespace std; Graph m_Graph; int main() { int nSelection = -1; do { cout << "===== 景区信息管理系统 =====" << endl; cout << "1.创建景区景点图" << endl; cout << "2.查询景点信息" << endl; cout << "3.旅游景点导航" << endl; cout << "4.搜索最短路径" << endl; cout << "5.铺设电路规划" << endl; cout << "0.退出" << endl; cout << "请输入操作编号(0～5):"; //该循环用来解决输入字符(串)后会进入死循环的问题 while (scanf("%d", &nSelection) != 1) { //scanf函数有n个输入正确便会返回n cout << "输入有误，请输入0～5的数字:"; while (getchar() != '\n') {}; //内层while循环换成下面的语句也可以解决问题，但VS2017的编译器不支持fflush(stdin)函数 //fflush(stdin); } switch (nSelection) { case 1: CreateGraph(); break; //创建景区景点图 case 2: GetSPotInfo(); break; //查询景点信息 case 3: TravelPath(); break; //旅游景点导航 case 4: FindShortPath(); break; //搜索最短路径 case 5: DesigePath(); break; //铺设电路规划 case 0: cout << "程序已退出\n"; system("pause"); exit(0); break;//退出 default: cout << "输入有误，请输入0～5的数字:"; break; } } while (nSelection != 0); return 0; }

Graph.h

#ifndef GRAPH_H #define GRAPH_H //定义顶点 struct Vex { int num; //景点编号 char name[20]; //景点名称 char desc[1024]; //景点介绍 }; //定义边 struct Edge { int vex1; //边的第一个顶点 int vex2; //边的第二个顶点 int weight; //权值 }; //定义图 struct Graph { int m_aAdjMatrix[20][20]; //邻接矩阵 Vex m_aVexs[20]; //顶点信息数组 int m_nVexNum; //当前图的顶点个数 }; //定义路径 typedef struct Path { int vexs[20]; //保存一条路径 Path *next; //下一条路径 }*PathList; //初始化图 void Init(); //插入顶点信息 bool InsertVex(Vex sVex); //插入边信息 bool InsertEdge(Edge sEdge); //获取当前顶点数 int GetVexmun(); //查询指定顶点信息 Vex GetVex(int v); //查询与指定顶点相连的边 int FindEdge(int nVex, Edge aEdge[]); //使用深度优先搜索算法遍历图 void DFS(int nVex, bool bVisted[], int &nIndex, PathList &pList); /* 输入参数：int nVex，顶点编号。输入参数：bVisted[]，bool 类型的数组，用来记录某个顶点是否被遍历过。输入参数：int &nIndex，记录遍历的深度。输出参数：PathList &pList，遍历得到的结果。功能：使用深度优先搜索算法遍历图 */ //通过调用 DFS()函数，得到深度优先搜索遍历结果 void DFSTraverse(int nVex, PathList &pList); /* 输入参数：int nVex，顶点编号。输出参数：PathList &pList，遍历得到的结果。功能：通过调用 DFS()函数，得到深度优先搜索遍历结果。 */ //通过Dijkstra算法求得nVexStart到nVexEnd的最短路径 int FindShortPath(int nVexStart, int nVexEnd, Edge aPath[]); /* 输入：起始景点的编号 v1 和目的景点的编号 v2。输出：最短路径。功能：通过 Dijkstra 算法求得 v1 到 v2 的最短路径 */ //通过 Prim 算法构建最小生成树 void FindMinTree(Edge aPath[]); /* 输入：Edge aPath[] 输出：最小生成树。功能：通过 Prim 算法构建最小生成树 */ #endif

Graph.cpp

#include<iostream> #include"Graph.h" using namespace std; //m_Graph图结构已经在主函数中定义，在此处调用 extern Graph m_Graph; //初始化图结构 void Init() { for (int i = 0; i < 20; i++) { for (int j = 0; j < 20; j++) { m_Graph.m_aAdjMatrix[i][j] = 0; //权值信息初始化为0 } m_Graph.m_nVexNum = 0; //景点数目初始化为0 } } //插入顶点信息 bool InsertVex(Vex sVex) { if (m_Graph.m_nVexNum == 20) //顶点已满 return false; m_Graph.m_aVexs[m_Graph.m_nVexNum++] = sVex; //插入顶点信息 return true; } //插入边信息 bool InsertEdge(Edge sEdge) { if (sEdge.vex1 < 0 || sEdge.vex1 >= 20 || sEdge.vex2 < 0 || sEdge.vex2 >= 20) //下标越界 return false; // 插入边的信息 m_Graph.m_aAdjMatrix[sEdge.vex1][sEdge.vex2] = sEdge.weight; m_Graph.m_aAdjMatrix[sEdge.vex2][sEdge.vex1] = sEdge.weight; return true; } //获取当前顶点数 int GetVexmun() { return m_Graph.m_nVexNum; } //查询指定顶点信息 Vex GetVex(int v) { return m_Graph.m_aVexs[v]; } //查询与指定顶点相连的边 int FindEdge(int nVex, Edge aEdge[]) { int k = 0; //便利整个图的邻接矩阵 for (int i = 0; i < 20; i++) { if (m_Graph.m_aAdjMatrix[nVex][i] != 0 && nVex != i) { //得到边的信息 aEdge[k].vex1 = nVex; aEdge[k].vex2 = i; aEdge[k].weight = m_Graph.m_aAdjMatrix[nVex][i]; k++; } } return k; // 返回边的条数 } //使用深度优先搜索算法遍历图 (一条路径) void DFS(int nVex, bool isVisited[], int & nIndex, PathList & pList) { isVisited[nVex] = true; //改为已访问 pList->vexs[nIndex++] = nVex; //访问顶点nVex int num = 0;//被访问过的节点数 for (int i = 0; i < m_Graph.m_nVexNum; i++) if (isVisited[i])//如果当前i节点被访问过，则num+1 num++; if (num == m_Graph.m_nVexNum) //如果所有的节点都被访问过 { //保存一条路径 pList->next = new Path; for (int i = 0; i < m_Graph.m_nVexNum; i++) pList->next->vexs[i] = pList->vexs[i]; pList = pList->next; pList->next = NULL; } else { for (int w = 0; w < m_Graph.m_nVexNum; w++) // 搜素 v 的所有邻接点 { if (m_Graph.m_aAdjMatrix[nVex][w] > 0 && !isVisited[w])//如果w是nVex的的邻接点并未被访问 { DFS(w, isVisited, nIndex, pList); //递归调用DFS isVisited[w] = false; //改为未访问 nIndex--; //索引值减1 } } } } //通过调用 DFS()函数，得到深度优先搜索遍历结果 void DFSTraverse(int nVex, PathList & pList) { int nIndex = 0; bool bVisited[20] = { false }; DFS(nVex, bVisited, nIndex, pList); } //寻找最短路径 int FindShortPath(int nVexStart, int nVexEnd, Edge aPath[]) { int nShortPath[20][20]; //最短路径，行表示终点，列表示从起点到终点的最短路径的每一步 int nShortDistance[20]; //保存从起点到任一顶点的最短距离 bool aVisited[20]; //判断某点是否已在最短路径中 int v; //每一次找到的可以加入集合的顶点 //初始化 for (v = 0; v < m_Graph.m_nVexNum; v++) { aVisited[v] = false; if (m_Graph.m_aAdjMatrix[nVexStart][v] != 0) { //如果顶点v和nVexStart相连，则最短距离设置为两顶点间的距离 nShortDistance[v] = m_Graph.m_aAdjMatrix[nVexStart][v]; } else { //如果不相连，则最短距离设置为最大值 nShortDistance[v] = 0x7FFFFFFF; } nShortPath[v][0] = nVexStart; //起始点为nVexStart //初始化最短路径 for (int w = 1; w < m_Graph.m_nVexNum; w++) { nShortPath[v][w] = -1; } } //初始化，将nVexStart顶点加入到集合中 aVisited[nVexStart] = true; int min; //暂存路径的最小值 for (int i = 1; i < m_Graph.m_nVexNum; i++) { min = 0x7FFFFFFF; bool bAdd = false; //判断是否还有顶点可以加入集合 for (int w = 0; w < m_Graph.m_nVexNum; w++) { if (!aVisited[w] && nShortDistance[w] < min) { v = w; //w顶点距离nVexStart顶点最近 min = nShortDistance[w]; //w到nVexStart的最短距离为min bAdd = true; } } //如果没有顶点可以加入到集合，则跳出循环 if (!bAdd) break; aVisited[v] = true; //将w顶点加入到集合 nShortPath[v][i] = v; //每次找到最短路径后，就相当于从源点出发到了终点，所以nShortPath[v][i]=v for (int w = 0; w < m_Graph.m_nVexNum; w++) { // 将w作为中间点计算nVexStart到所有顶点的最短距离 if (!aVisited[w] && (min + m_Graph.m_aAdjMatrix[v][w] < nShortDistance[w]) && (m_Graph.m_aAdjMatrix[v][w] > 0))//如果有新的最短距离 { //更新最短路径及距离 nShortDistance[w] = min + m_Graph.m_aAdjMatrix[v][w]; for (int i = 0; i < m_Graph.m_nVexNum; i++) { //如果通过w达到顶点i的距离比较短，则将w的最短路径复制给i nShortPath[w][i] = nShortPath[v][i]; } } } } int nIndex = 0; int nVex1 = nVexStart; //将最短路径保存到边的结构体数组中 for (int i = 1; i < m_Graph.m_nVexNum; i++) { if (nShortPath[nVexEnd][i] != -1) { aPath[nIndex].vex1 = nVex1; aPath[nIndex].vex2 = nShortPath[nVexEnd][i]; aPath[nIndex].weight = m_Graph.m_aAdjMatrix[nVex1][aPath[nIndex].vex2]; nVex1 = nShortPath[nVexEnd][i]; nIndex++; } } return nIndex; } //通过Prim算法构建最小生成树 void FindMinTree(Edge aPath[]) { bool aVisited[20] = { false }; //判断某顶点是否在最小生成树中 aVisited[0] = true; //从0号顶点开始，加入到集合中 int min; int nVex1, nVex2; for (int k = 0; k < m_Graph.m_nVexNum - 1; k++) { min = 0x7FFFFFFF; for (int i = 0; i < m_Graph.m_nVexNum; i++) { //从集合中取一个顶点 if (aVisited[i]) { for (int j = 0; j < m_Graph.m_nVexNum; j++) { //从不在集合中的顶点中取出一个顶点 if (!aVisited[j]) { if ((m_Graph.m_aAdjMatrix[i][j] < min) && (m_Graph.m_aAdjMatrix[i][j] != 0)) { nVex1 = i; nVex2 = j; //找出最短边 min = m_Graph.m_aAdjMatrix[i][j]; } } } } } //保存最短边的两个顶点 aPath[k].vex1 = nVex1; aPath[k].vex2 = nVex2; aPath[k].weight = m_Graph.m_aAdjMatrix[nVex1][nVex2]; //将两个顶点加入集合 aVisited[nVex1] = true; aVisited[nVex2] = true; } }

Tourism.h

#ifndef TOURISM_H #define TOURISM_H //读取文件，创建景区景点图 void CreateGraph(); //查询指定景点信息 void GetSPotInfo(); //通过调用 DFSTraverse()函数，实现旅游景点导航功能，将查询到的景点导航路线显示在界面上。 void TravelPath(); //通过调用函数查询两个景点间的最短路径和距离 void FindShortPath(); //查询铺设电路规划图 void DesigePath(); /* 输入：viod 输出：铺设的线路。功能：通过调用Graph.cpp文件中的FindMinTree()方法查询铺设电路规划图。 */ #endif

Tourism.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include <fstream> #include <string.h> #include<stdlib.h> #include"Graph.h" #include"Tourism.h" using namespace std; //m_Graph在主函数中已经定义，在此处调用 extern Graph m_Graph; //读取文件，创建景区景点图 void CreateGraph() { cout << "\n=====创建景点景区图=====" << endl; Init(); //初始化图 ifstream VexFile("Vex.txt"); if (!VexFile) { cout << "Vex.txt文件打开失败，请检查！" << endl; return; } //暂存从Vex.txt读取的一行数据 char num[2]; char name[20]; char desc[1024]; Vex sVex; //逐行读取Vex.txt文件中的数据 VexFile.getline(num, 2); //将第一行的数据读出丢掉 cout << "景区数目：" << atoi(num) << endl; cout << "----- 顶点 -----" << endl; while (VexFile.getline(num, 2)) { sVex.num = atoi(num); VexFile.getline(name, 20); strcpy(sVex.name, name); VexFile.getline(desc, 1024); strcpy(sVex.desc, desc); //将景点信息输出 cout << sVex.num << "―" << sVex.name << endl; //设置图的顶点 if (!InsertVex(sVex)) { cout << "新增景点失败！" << endl; continue; } } VexFile.close(); ifstream EdgeFile("Edge.txt"); if (!EdgeFile) { cout << "Edge.txt文件打开失败，请检查！" << endl; return; } Edge edge; cout << "----- 边 -----" << endl; while (EdgeFile) { EdgeFile >> edge.vex1 >> edge.vex2 >> edge.weight; cout << "<" << edge.vex1 << "," << edge.vex2 << "> " << edge.weight << endl; //设置图的边 if (!InsertEdge(edge)) { cout << "新增路径信息失败！" << endl; continue; } } EdgeFile.close(); cout << endl; return; } //查询指定景点信息 void GetSPotInfo() { cout << "\n=====查询景点信息=====" << endl; int nVexNum = m_Graph.m_nVexNum; if (nVexNum == 0) { cout << "请先创建图！" << endl; return ; } //将景点信息列出来 for (int i = 0; i < m_Graph.m_nVexNum; i++) { Vex sVex = GetVex(i); cout << i << "—" << sVex.name << endl; } //提示用户根据编号查询 cout << "\n请输入想要查询的景点编号："; int num; cin >> num; if (num < 0 || num >= m_Graph.m_nVexNum) cout << "输入错误！" << endl; else { Vex sVex = GetVex(num); cout << sVex.name << "\n" << sVex.desc << endl; cout << "-----周边景区-----" << endl; Edge aEdge[20]; int EdgeNum = FindEdge(num, aEdge); //周边景点的数目 for (int i = 0; i < EdgeNum; i++) { Vex v1 = GetVex(aEdge[i].vex1); Vex v2 = GetVex(aEdge[i].vex2); cout << v1.name << "->" << v2.name << " " << aEdge[i].weight << "m" << endl; } } cout << endl; return ; } //通过调用 DFSTraverse()函数，实现旅游景点导航功能，将查询到的景点导航路线显示在界面上。 void TravelPath() { cout << "\n=====旅游景点导航=====" << endl; int nVexNum = m_Graph.m_nVexNum; if (nVexNum == 0) { cout << "请先创建图！" << endl; return; } for (int i = 0; i < m_Graph.m_nVexNum; i++) { Vex sVex = GetVex(i); cout << i << "-" << sVex.name << endl; } //输入景点编号 cout << "请输入想要起始点编号："; int startnum; cin >> startnum; if (startnum < 0 || startnum >= m_Graph.m_nVexNum) { cout << "输入的编号有误！" << endl; return; } //遍历景区景点图 PathList pList = new Path; PathList pHead = pList; DFSTraverse(startnum, pList); //输出遍历结果 cout << "导游路线为：" << endl; int i = 1; pList = pHead; while (pList->next != NULL) { Vex vex = GetVex(pList->vexs[0]); cout << "路线" << i++ << "：" << vex.name; for (int j = 1; j < m_Graph.m_nVexNum; j++) { vex = GetVex(pList->vexs[j]); cout << " -> " << vex.name; } cout << endl; pList = pList->next; } cout << endl; delete pList; pList = NULL; pHead = NULL; } //通过调用函数查询两个景点间的最短路径和距离 void FindShortPath() { cout << "\n=====搜索最短路径=====" << endl; int nVexNum = m_Graph.m_nVexNum; if (nVexNum == 0) { cout << "请先创建图！" << endl; return; } for (int i = 0; i < m_Graph.m_nVexNum; i++) { Vex sVex = GetVex(i); cout << i << "-" << sVex.name << endl; } //输入两个景点的编号 int start_place, end_place; cout << "请输入起点的编号："; cin >> start_place; cout << "请输入终点的编号："; cin >> end_place; if (start_place < 0 || start_place >= m_Graph.m_nVexNum || end_place < 0 || end_place >= m_Graph.m_nVexNum) { cout << "输入错误！" << endl; return; } Edge aPath[20]; //边信息数组，依次保存最短的路径 for (int i = 0; i < 20; i++) { //初始化边信息数组 aPath->vex1 = -1; aPath->vex2 = -1; aPath->weight = -1; } //搜索最短路径 int index = FindShortPath(start_place, end_place, aPath); int length = 0; //最短路径总长度 Vex sVex = GetVex(aPath[0].vex1); //得到最短路径和最短距离 cout << "最短路径为：" << sVex.name; for (int i = 0; i < index; i++) { sVex = GetVex(aPath[i].vex2); cout << "->" << sVex.name; length += aPath[i].weight; } cout << endl; cout << "最短距离为：" << length << endl << endl; } //查询铺设电路规划图 void DesigePath() { cout << "\n=====铺设电路规划=====" << endl; Edge aPath[20]; FindMinTree(aPath); //构建最小树 int nVexNum = m_Graph.m_nVexNum; if (nVexNum == 0) { cout << "请先创建图！" << endl; return; } //输出铺设线路图 int nAllLength = 0; cout << "在以下两个景点之间铺设电路：" << endl; for (int i = 0; i < m_Graph.m_nVexNum - 1; i++) { Vex nVex1 = GetVex(aPath[i].vex1); Vex nVex2 = GetVex(aPath[i].vex2); cout << nVex1.name << "-" << nVex2.name << " " << aPath[i].weight << "m" << endl; nAllLength += aPath[i].weight; } cout << "铺设电路的总长度是：" << nAllLength << "m" << endl << endl; }

最新回复(0)