♻️ 资源大小3.36MB➡️资源下载https://download.csdn.net/download/s1t16/87425289图的操作和应用之景区信息管理系统(1) 读文件创建图输入从Vex.txt文件中读取景点信息从Edge.txt文件中读取道路信息。处理根据读取的景区信息创建景区景点图。(2) 查询景点输入想要查询的景点的编号。处理根据输入的景点编号查询该景点及相邻景点的信息。输出① 景点名字② 景点介绍③ 相邻景区的名字④ 到达相邻景区的路径长度(3) 旅游景点导航输入起始景点的编号。处理使用深度优先搜索(DFS)算法查询以该景点为起点无回路游览整个景区的路线。输出所有符合要求的导航路线。(4) 搜索最短路径输入① 起始景点的编号② 终点的编号。处理使用迪杰斯特拉(Dijkstra)算法求得从起始景点到终点之间的最短路径计算路径总长度。输出① 最短路线② 路径总长度(5) 铺设电路规划处理根据景区景点图使用普里姆(Prim)算法构造最小生成树设计出一套铺设线路最短但能满足每个景点都能通电的方案。输出① 需要铺设电路的道路② 每条道路铺设电路的长度③ 铺设电路的总长度(6) 修改图保存文件插入、删除、修改顶点、边的信息注意顶点和边的关系之后保存文件重新读取文件建立图的存储结构并显示。重点注意顶点和边的关系考虑边是否重复顶点是否存在……(7)菜单及结构体定义代码#define MAX_SIZE 1000//最大可存顶点数 #define INFINITY 99999//无穷大 struct Vertex//顶点 { int tag;//标记此顶点是否存在 string name,info; }; struct ArcNode { int n; ArcNode *next; }; struct VNode//邻接表 { Vertex vex; ArcNode *next; }AdjList[MAX_SIZE]; struct Graph//图 { int arc[MAX_SIZE][MAX_SIZE];//每个顶点与其余各个顶点之间边长 int vexnum;//目前顶点总数 int edgnum;//目前此图边总数 int maxvexno; //目前此图顶点最大编号 }G; int created0;//表示未创建图 int main()//主函数 { int tag,m,n; while(1) { tag0; Menu(); cinn; switch(n) { case 1:CreatMap();break; case 2:{cout请输入景区编号endl;cinn;SearchVex(n);}break; case 3:{cout请输入景区编号endl;cinn;Navigation_DFS(n);}break; case 4:{cout请输入起止景区编号endl;cinmn;ShortestPath_DIJ(m,n);}break; case 5:WirePath_Prim();break; case 6:Edit();break; case 7:tag1;break; default:cout更多功能正在开发敬请期待……endl; } if(tag) break; } return 0; } void Menu()//主菜单 { printf(---------------景区管理系统功能菜单---------------\n); printf(1-----创建图\n); printf(2-----查询景点信息\n); printf(3-----旅游景点导航\n); printf(4-----搜索最短路径\n); printf(5-----铺设电路规划\n); printf(6-----修改图\n); printf(7-----退出主菜单\n); printf(请输入功能序号执行功能\n); }1、数据格式Vex.txt中第一行景点总数之后每一行一个景点信息包括景点编号、名称、介绍。Edge.txt中每一行一条道路信息。包括景点编号、景点编号、道路距离。2、数据结构读文件创图将文件中的数据读入内存建立图的邻接表并输出图的邻接表。实现该功能代码如下void CreatMap()//导入文件数据创建图并输出邻接表 { int m,t,i,j; //读取Vex.txt文件的景点信息 fstream f1(./Vex.txt,ios::in); f1G.vexnum; t0;//记录已读取景点信息个数 for(i0;tG.vexnum;i) { f1m; while(i!m) { AdjList[i].vex.tag0;//编号为i的景点不存在标记为0 i; } AdjList[m].vex.tag1; //景点存在标记为1 t; f1AdjList[m].vex.nameAdjList[m].vex.info;//从vex.txt文件中读取景点信息 } G.maxvexnom;//记录景点的最大编号 f1.close(); //初始化各路径距离 for(i0;iG.maxvexno;i) if(AdjList[i].vex.tag) for(j0;jG.maxvexno;j) if(AdjList[j].vex.tag) G.arc[i][j]INFINITY;//初始化各景点间距离为INFINITY //读取Edge.txt的路径信息 fstream f2(./Edge.txt,ios::in); G.edgnum0; while(f2ij) { f2G.arc[i][j]; G.arc[j][i]G.arc[i][j];//从Edge.txt文件中读取景点间距离若文件中未出现两景点间距离则保持初始的INFINITY G.edgnum; } f2.close(); created1;//表示已经创建图 //创建邻接表 CreatAdjList(); //展示邻接表 cout邻接表如下endl;//格式为V1-V2-V3 for(i0;iG.maxvexno;i) if(AdjList[i].vex.tag) { coutVi; ArcNode *anAdjList[i].next; while(an) { cout-Van-n; anan-next; } coutendl; } } void CreatAdjList()//建立邻接表 { for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) { ArcNode *a; AdjList[i].nextNULL; for(int jG.maxvexno;j0;j--) if(AdjList[j].vex.tag) if(G.arc[i][j]INFINITY) { anew ArcNode; a-nj; a-nextAdjList[i].next; AdjList[i].nexta; } } }数据格式编号名字介绍0A区风景优美气候宜人。1B区风景优美气候宜人。2C区风景优美气候宜人。3D区风景优美气候宜人。4E区风景优美气候宜人。5F区风景优美气候宜人。6G区风景优美气候宜人。景点1景点2距离(m)AC700AE1000AF600BC1000BG1000CD400DE300DG400EF600FG500文件截图运行截图3、查询景点输入想要查询的景点的编号。处理根据输入的景点编号查询该景点及相邻景点的信息。输出① 景点名字② 景点介绍③ 相邻景区的名字④ 到达相邻景区的路径长度算法根据输入编号直接用数组找到景点信息输出再用邻接表找到与其相连的景点并输出信息。实现该功能代码如下void SearchVex(int n)//查找编号为n的景点 { if(created)//图已被创建 { if(n0||nG.maxvexno||AdjList[n].vex.tag0)//编号n不在文件读入的编号范围内或其标记为0 cout该景点不存在endl; else {//输出景点编号、名称和景点信息以及相邻的各个景点编号、名称和相距距离 coutn AdjList[n].vex.name AdjList[n].vex.infoendl; cout相邻景点endl; for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) if(G.arc[i][n]INFINITY) couti AdjList[i].vex.name G.arc[i][n]endl; } } else//图未被创建 cout尚未读取文件创建图endl; }运行截图4、修改图保存文件插入、删除、修改顶点、边的信息注意顶点和边的关系之后保存文件重新读取文件建立图的存储结构并显示。核心操作首先要保证添加、删除后仍为连通图因此添加景点也要添加一条边删除顶点也要删除相连的边代码中用IsConnected函数来判断是否连通否则操作不能执行。其次在操作执行后都要将数据重新读入文件。最后要再一次读取文件创建图。实现该功能代码如下void Edit()//修改操作菜单 { int m; if(created) { while(1) { int tag0; cout-----编辑操作菜单-----endl; cout-----1添加-----endl; cout-----2删除-----endl; cout-----3修改-----endl; cout-----4退出本菜单-----; cout输入编号执行相应操作endl; cinm; switch(m) { case 1:Add();break; case 2:Delete();break; case 3:Revise();break; case 4:tag1;break; default:cout更多功能正在开发中敬请期待…… endl; } if(tag) break; } } else cout尚未读取文件创建图endl; } int count;//记录已访问顶点数 int IsConnected()//判断是否为连通图 { count0; int *Visitednew int[G.maxvexno1]; //标记是否已访问过 for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) Visited[i]0;//初始化 for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) { Connect_DFS(i,Visited); break; } if(countG.vexnum) return 1;//该图连通返回1 else return 0; //该图不连通返回0 } void Connect_DFS(int i,int *Visited)//DFS搜索 { ArcNode *anAdjList[i].next; Visited[i]1;//标记已访问过 count;//并入已访问过的点集 coutcountendl; while(an)//搜索与该顶点相连的每个顶点 { while(Visited[an-n]||AdjList[an-n].vex.tag0)//已访问过就找下一个顶点 { anan-next; if(anNULL)break; } if(an) { Connect_DFS(an-n,Visited);//对此顶点进行DFS搜索 anan-next; } } } void Add()//添加操作菜单 { int n,tag; while(1) { tag0; coutVex.txt内容读取endl; ShowVexTxt(); coutEdge.txt内容读取endl; ShowEdgeTxt(); cout--------添加选项------endl; cout-----1景点----- endl; cout-----2路径-----endl; cout-----3退出当前菜单-----endl; cout输入功能序号执行相应功能endl; cinn; switch(n) { case 1:AddVex();break; case 2:AddEdge();break; case 3:tag1;break; default:cout更多功能正在开发敬请期待……endl; } if(tag) break; } } void AddVex()//添加景点 { int no,start,end,dis,maxno; string name,info; if(G.vexnumMAX_SIZE) { cout请输入添加的景点及路径第一行景点编号 名称 信息 第二行景点编号 景点编号 距离endl; cinnonameinfo; cinstartenddis; if(no0) cout景点编号不合法添加失败endl; else { if(noG.maxvexno||AdjList[no].vex.tag0) {//初始化该景点相关信息 AdjList[no].vex.tag1; AdjList[no].vex.namename; AdjList[no].vex.infoinfo; G.vexnum; maxnoG.maxvexno; if(noG.maxvexno)//更改最大编号并将不存在的顶点标记 { for(int iG.maxvexno1;ino;i) AdjList[i].vex.tag0; G.maxvexnono; } for(int i0;iG.maxvexno;i)//初始化no与其他顶点的距离 if(AdjList[i].vex.tag) { G.arc[i][no]INFINITY; G.arc[no][i]INFINITY; } //添加道路 if(start0||startG.maxvexno||AdjList[start].vex.tag0||end0||endG.maxvexno||AdjList[end].vex.tag0) cout景点不存在添加失败endl; else if(dis0||disINFINITY) cout该路径距离超限添加失败endl; else if(G.arc[start][end]INFINITY) cout该路径已记录添加失败endl; else { G.arc[start][end]dis; G.arc[end][start]dis; G.edgnum; CreatAdjList();//重建邻接表 if(IsConnected())//添加后仍是连通图 { fstream f3(./Vex.txt,ios::out); fstream f4(./Edge.txt,ios::out); //读入Vex文件 f3G.vexnumendl; for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) f3i AdjList[i].vex.name AdjList[i].vex.infoendl; f3.close(); //读入Edge文件 for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) for(int ji;jG.maxvexno;j) if(AdjList[j].vex.tag) if(G.arc[i][j]INFINITY) f4i j G.arc[i][j]endl;; f4.close(); cout添加景点成功endl; } else//否则添加失败 {//更改为添加前的值 AdjList[no].vex.tag0; G.vexnum--; G.maxvexnomaxno; G.arc[start][end]INFINITY; G.arc[end][start]INFINITY; G.edgnum--; cout添加后为非连通图添加失败endl; } //重新创建图 CreatMap(); } } else cout该景点已存在添加失败endl; } } else cout景点存储数量已达上限无法再添加endl; } void AddEdge()//添加道路 { int start,end,dis; //添加道路 cout请输入添加的路径景点编号 景点编号 距离endl; cinstartenddis; if(start0||startG.maxvexno||AdjList[start].vex.tag0||end0||endG.maxvexno||AdjList[end].vex.tag0) cout景点不存在添加失败endl; else if(dis0||disINFINITY) cout该路径距离超限添加失败endl; else if(G.arc[start][end]INFINITY) cout该路径已记录添加失败endl; else { G.arc[start][end]dis; G.arc[end][start]dis; G.edgnum; CreatAdjList();//重建邻接表 if(IsConnected())//添加后仍是连通图 { fstream f5(./Edge.txt,ios::out); //读入Edge文件 for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) for(int ji;jG.maxvexno;j) if(AdjList[j].vex.tag) if(G.arc[i][j]INFINITY) f5i j G.arc[i][j]endl; f5.close(); cout添加路径成功endl; } Else//添加后不是连通图 {//恢复原值 G.arc[start][end]INFINITY; G.arc[end][start]INFINITY; G.edgnum--; cout添加后为非连通图添加失败endl; } CreatMap();//重新创建图 } }添加景点输入8 H区 高大宽敞5 8 200运行截图文件截图添加道路输入1 8 800运行截图文件截图5、修改操作菜单void Delete()//删除操作菜单 { int n,tag; while(1) { tag0; coutVex.txt内容读取endl; ShowVexTxt(); coutEdge.txt内容读取endl; ShowEdgeTxt(); cout--------删除选项------endl; cout-----1景点----- endl; cout-----2路径-----endl; cout-----3退出当前菜单-----endl; cout输入功能序号执行相应功能endl; cinn; switch(n) { case 1:DeleteVex();break; case 2:DeleteEdge();break; case 3:tag1;break; default:cout更多功能正在开发敬请期待……endl; } if(tag) break; } } void DeleteVex()//删除景点 { int no,maxno; cout请输入要删除的编号endl; cinno; if(no0||noG.maxvexno||AdjList[no].vex.tag0) cout景点不存在删除失败endl; else { G.vexnum--; AdjList[no].vex.tag0;//修改标记 maxnoG.maxvexno; if(noG.maxvexno)//更新最大编号 for(int iG.maxvexno-1;i0;i--) if(AdjList[i].vex.tag) { G.maxvexnoi; break; } CreatAdjList();//重建邻接表 if(IsConnected()) {//删除后连通 fstream f8(./Vex.txt,ios::out); //读入Vex文件 f8G.vexnumendl; for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) f8i AdjList[i].vex.name AdjList[i].vex.infoendl; f8.close(); fstream f9(./Edge.txt,ios::out); //更新删除顶点后的路径并读入Edge文件 G.edgnum0; for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) for(int ji;jG.maxvexno;j) if(AdjList[j].vex.tag) if(G.arc[i][j]INFINITY) { f9i j G.arc[i][j]endl; G.edgnum; } f9.close(); cout成功删除景点endl; } else {//不连通则恢复原值 G.vexnum; AdjList[no].vex.tag1;//修改标记 G.maxvexnomaxno; cout删除后为非连通图删除失败endl; } CreatMap();//重新创建图 } } void DeleteEdge()//删除道路 { int n,m,dis,start,end; //删除路径信息 cout请输入要删除的路径个数不得超过G.edgnum-G.vexnum1个endl; cinn; while(n0||nG.edgnum-G.vexnum1) { cout已超过可删除路径数限制请重新输入endl; cinn; } mn; cout请逐行输入路径连接的两景点格式景点编号 景点编号endl; while(n) { cinstartend; if(start0||startG.maxvexno||AdjList[start].vex.tag0||end0||endG.maxvexno||AdjList[end].vex.tag0) cout景点不存在请重新输入删除信息endl; else if(G.arc[start][end]INFINITY) cout该路径不存在请重新输入删除信息endl; else { disG.arc[start][end]; G.arc[start][end]INFINITY; G.arc[end][start]INFINITY; G.edgnum--; n--; CreatAdjList();//重建邻接表 if(IsConnected()) {//删除后仍连通 fstream f10(./Edge.txt,ios::out); //读入文件 for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) for(int ji;jG.maxvexno;j) if(AdjList[j].vex.tag) if(G.arc[i][j]INFINITY) f10i j G.arc[i][j]endl; f10.close(); cout成功删除路径endl; } else {//不连通则恢复原值 G.arc[start][end]dis; G.arc[end][start]dis; G.edgnum; cout删除后为非连通图删除失败endl; } } } coutm条路径删除完毕endl; CreatMap();//重新创建图 }修改景点输入14 W区 奇峰怪石运行结果文件截图修改道路输入12 3 200运行截图文件截图6、旅游景点导航输入起始景点的编号。处理使用深度优先搜索(DFS)算法查询以该景点为起点无回路游览整个景区的路线。输出所有符合要求的导航路线。实现该功能代码如下void Navigation_DFS(int n)//DFS算法从编号为n的景点开始无回路遍历全图 { if(created)//图已被创建 { if(n0||nG.maxvexno||AdjList[n].vex.tag0)//编号n不在文件读入的编号范围内或顶点标记为0 cout该景点不存在endl; else { int count1;//count记录本条路径已搜索过的顶点 int *BVisitednew int[G.maxvexno1];//横向标记 int *DVisitednew int[G.maxvexno1];//纵向标记 int *nonew int[G.vexnum];//记录路径上的顶点编号 for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) { DVisited[i]0;//复制前面纵向搜索的标记 BVisited[i]0;//横向均未搜索过 } no[0]n;//记录起点 DVisited[n]1;//标记纵向已访问过 ArcNode *anAdjList[n].next; while(an)//横向搜索与该顶点相连的每个顶点 { while(BVisited[an-n])//横向或纵向已访问过就找下一个顶点 { anan-next; if(anNULL)break; } if(an) { DFS(an-n,count,DVisited,no);//对此顶点进行DFS搜索 BVisited[an-n]1;//标记此顶点横向已访问过 anan-next; } } } } else//图未被创建 cout尚未读取文件创建图endl; } void DFS(int n,int count,int *a,int *no)//DFS搜索路径 { int *DVisitednew int[G.maxvexno1];//纵向标记 int *BVisitednew int[G.maxvexno1];//横向标记 for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) { DVisited[i]a[i];//复制前面纵向搜索的标记 BVisited[i]0;//横向均未搜索过 } no[count]n; DVisited[n]1;//纵向标记已访问过 ArcNode *anAdjList[n].next; while(an)//横向搜索与该顶点相连的每个顶点 { while(BVisited[an-n]||DVisited[an-n])//横向或纵向已访问过就找下一个顶点 { anan-next; if(anNULL)break; } if(an) { DFS(an-n,count,DVisited,no);//对此顶点进行DFS搜索 BVisited[an-n]1;//标记此顶点横向已访问过 anan-next; } } if(countG.vexnum)//如果此路径上顶点数与总顶点数相同说明该路径无回路 { for(int i0;icount-1;i)//输出路径 coutAdjList[no[i]].vex.name--; coutAdjList[count-1].vex.nameendl; } }算法对DFS进行改良对一个景点连接的所有景点都进行搜索每一个都可以搜索出一条新路用两个数组一个数组用来标记本条路上访问过的景点另一个数组标记搜索连接的景点中已搜索过的景点以此递归最终如果本条路上的景点数等于景点总数说明该路无回路。输入1运行截图文件截图DFS核心代码流程图7、搜索最短路径输入① 起始景点的编号② 终点的编号。处理使用迪杰斯特拉(Dijkstra)算法求得从起始景点到终点之间的最短路径计算路径总长度。输出① 最短路线② 路径总长度算法先用Dijkstra算法然后根据两个景点编号输出其最短路径。优点是可以找到任意两点间最短路径缺点是遍历的节点太多效率很低。实现该功能代码void ShortestPath_DIJ(int m,int n)//Dijkstra算法求编号m景区到编号n景区的最短路线 { if(created) { if(m0||mG.maxvexno||AdjList[m].vex.tag0||n0||nG.maxvexno||AdjList[n].vex.tag0) cout景点不存在endl; else { int *Prenew int[G.maxvexno1];//记录当前顶点的前一顶点 int *Disnew int[G.maxvexno1];//起点到各个顶点的当前最短距离 int *finalnew int[G.maxvexno1];// 记录是否已找到起点到各个顶点的最短路径 for(int i0;iG.maxvexno;i)//初始化 if(AdjList[i].vex.tag) { final[i]0;//表示起点到各个顶点的最短距离均未找到 Dis[i]G.arc[m][i];//初始化起点到各个顶点的最短距离与起点相连的就是连线的距离否则就是INFINITY if(Dis[i]INFINITY) Pre[i]m;//最短距离小于INFINITY表明与起点相连则其前一顶点为起点 else Pre[i]-1;//否则置为-1表示无前一顶点 } Dis[m]0;//起点到自身距离为0 final[m]1;//起点到起点已找到最短路径 for(int i0;iG.maxvexno;i) if(AdjList[i].vex.tag) { int minINFINITY;//记录离起点最近的距离 int v-1;//记录离起点最近的点 for(int j1;jG.maxvexno;j)//从未找到最短路径的顶点中找到离起点最近的顶点 if(AdjList[j].vex.tag) if(!final[j]Dis[j]min) { minDis[j]; vj; } final[v]1;//起点到该点已找到最短距离 for(int j0;jG.maxvexno;j) if(AdjList[j].vex.tag) if(!final[j](minG.arc[v][j]Dis[j]))//更新起点到各点的最短距离 { Dis[j]minG.arc[v][j]; Pre[j]v;//记录前一顶点 } } cout从AdjList[m].vex.name至AdjList[n].vex.name; if(Dis[n]INFINITY)//倒序输出路径 { cout最短路径总长度为Dis[n] 最短路径(倒序)如下endl; coutAdjList[n].vex.name; int vPre[n]; while(v!m) { cout--AdjList[v].vex.name; vPre[v]; } cout--AdjList[m].vex.nameendl; } else cout不通endl; } } else//图未被创建 cout尚未读取文件创建图endl; }输入5 1运行截图文件截图核心代码流程图8.设计总结首先对DFS、迪杰斯特拉、Prim算法都再次深入理解了一遍而且能更加熟练的运用和修改后适用于新问题同时也对算法的利弊有所体会。再一个就是学会了使用文件的读取和读写流文件数据修改后应该重新写入文件以及重新创建相应的图。这个过程中一个很重要的问题还是指针的熟练掌握和运用对于所创建的数据结构必要时要在数据的末尾指针赋空这样检索遍历时不会混乱。在刚开始程序写完运行的时候很容易出现烫烫烫就是因为传值没有传过来数据没有初始化等原因。另外通过设计这个程序让我对于程序的整体性、容错性以及尽可能让软件输入简洁明了有了更深的认识尽可能让用户输入正确的数据这样才能保证程序不会因为用户输错数据类型而崩溃其次还有用户输入的数据必须有效这就需要代码去识别如果无效必须进行处理否则也会引起崩溃。主要考察的修改操作这一块要求很强的逻辑性必须处理好修改成功与否与文件是否重新读写的关系。因为整个程序是在连通图的大前提下所以无论哪一步操作都要注意操作后图是否连通如果连通方可修改否则不能执行操作。修改后还要对应重新读写文件创建新图。总之在写程序时要全面考虑不管要考虑需求还要对程序的容错性最大限度地考虑到保证程序在用户输错数据的情况下依然能够正常运行。