精选_毕业设计_图的操作和应用之景区信息管理系统_完整源码

# 图的操作和应用之景区信息管理系统 # 一、功能要求 ## 1.1 读文件创建图 - **输入**：从Vex.txt文件中读取景点信息，从Edge.txt文件中读取道路信息 - **处理**：根据读取的景区信息创建景区景点图 ## 1.2 查询景点 - **输入**：想要查询的景点的编号 - **处理**：根据输入的景点编号，查询该景点及相邻景点的信息 - **输出**： - 景点名字 - 景点介绍 - 相邻景区的名字 - 到达相邻景区的路径长度 ## 1.3 旅游景点导航 - **输入**：起始景点的编号 - **处理**：使用深度优先搜索(DFS)算法，查询以该景点为起点，无回路游览整个景区的路线 - **输出**：所有符合要求的导航路线 ## 1.4 搜索最短路径 - **输入**： - 起始景点的编号 - 终点的编号 - **处理**：使用迪杰斯特拉(Dijkstra)算法，求得从起始景点到终点之间的最短路径，计算路径总长度 - **输出**： - 最短路线 - 路径总长度 ## 1.5 铺设电路规划 - **处理**：根据景区景点图使用普里姆(Prim)算法构造最小生成树，设计出一套铺设线路最短，但能满足每个景点都能通电的方案 - **输出**： - 需要铺设电路的道路 -每条道路铺设电路的长度 - 铺设电路的总长度 ## 1.6 修改图保存文件 插入、删除、修改顶点、边的信息，注意顶点和边的关系，之后保存文件，重新读取文件建立图的存储结构并显示。 重点注意顶点和边的关系，考虑边是否重复？顶点是否存在？…… # 二、数据结构介绍 ```c++ # 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 created=0;//表示未创建图 int main()//主函数 { int tag,m,n; while(1) { tag=0; Menu(); cin>>n; switch(n) { case 1:CreatMap();break; case 2:{cout<<"请输入景区编号："<<endl;cin>>n;SearchVex(n);}break; case 3:{cout<<"请输入景区编号："<<endl;cin>>n;Navigation_DFS(n);}break; case 4:{cout<<"请输入起止景区编号："<<endl;cin>>m>>n;ShortestPath_DIJ(m,n);}break; case 5:WirePath_Prim();break; case 6:Edit();break; case 7:tag=1;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"); } ``` # 三、功能实现 ## 3.1 数据格式 - Vex.txt中第一行景点总数，之后每一行一个景点信息，包括景点编号、名称、介绍 - Edge.txt中每一行一条道路信息。包括景点编号、景点编号、道路距离 ## 3.2 读文件创图 将文件中的数据读入内存，建立图的邻接表并输出图的邻接表。 ### 3.2.1 实现代码 ```c++ void CreatMap()//导入文件数据创建图，并输出邻接表 { int m,t,i,j; //读取Vex.txt文件的景点信息 fstream f1("./Vex.txt",ios::in); f1>>G.vexnum; t=0;//记录已读取景点信息个数 for(i=0;t<G.vexnum;i++) { f1>>m; while(i!=m) { AdjList[i].vex.tag=0;//编号为i的景点不存在，标记为0 i++; } AdjList[m].vex.tag=1; //景点存在，标记为1 t++; f1>>AdjList[m].vex.name>>AdjList[m].vex.info;//从vex.txt文件中读取景点信息 } G.maxvexno=m;//记录景点的最大编号 f1.close(); //初始化各路径距离 for(i=0;i<=G.maxvexno;i++) if(AdjList[i].vex.tag) for(j=0;j<=G.maxvexno;j++) if(AdjList[j].vex.tag) G.arc[i][j]=INFINITY;//初始化各景点间距离为INFINITY //读取Edge.txt的路径信息 fstream f2("./Edge.txt",ios::in); G.edgnum=0; while(f2>>i>>j) { f2>>G.arc[i][j]; G.arc[j][i]=G.arc[i][j];//从Edge.txt文件中读取景点间距离，若文件中未出现两景点间距离则保持初始的INFINITY G.edgnum++; } f2.close(); created=1;//表示已经创建图 //创建邻接表 CreatAdjList(); //展示邻接表 cout<<"邻接表如下："<<endl;//格式为V1->V2->V3 for(i=0;i<=G.maxvexno;i++) if(AdjList[i].vex.tag) { cout<<'V'<<i; ArcNode *an=AdjList[i].next; while(an) { cout<<"->V"<<an->n; an=an->next; } cout<<endl; } } void CreatAdjList()//建立邻接表 { for(int i=0;i<=G.maxvexno;i++) if(AdjList[i].vex.tag) { ArcNode *a; AdjList[i].next=NULL; for(int j=G.maxvexno;j>=0;j--) if(AdjList[j].vex.tag) if(G.arc[i][j]<INFINITY) { a=new ArcNode; a->n=j; a->next=AdjList[i].next; AdjList[i].next=a; } } } ``` ### 3.2.2 数据格式 | 编号 | 名字 | 介绍 | | ---- | ---- | ---------- | | 0 | A区 | 风景优美，气候宜人。 | | 1 | B区 | 风景优美，气候宜人。 | | 2 | C区 | 风景优美，气候宜人。 | | 3 | D区 | 风景优美，气候宜人。 | | 4 | E区 | 风景优美，气候宜人。 | | 5 | F区 | 风景优美，气候宜人。 | | 6 | G区 | 风景优美，气候宜人。 | | 景点1 | 景点2 | 距离(m) | | ---- | ---- | ----- | | A | C | 700 | | A | E | 1000 | | A | F | 600 | | B | C | 1000 | | B | G | 1000 | | C | D | 400 | | D | E | 300 | | D | G | 400 | | E | F | 600 | | F | G | 500 | ### 3.2.3 截图    ## 3.3 查询景点 - **输入**：想要查询的景点的编号 **处理**：根据输入的景点编号，查询该景点及相邻景点的信息 - **输出**： - 景点名字 - 景点介绍 - 相邻景区的名字 - 到达相邻景区的路径长度 - **算法**：根据输入编号直接用数组找到景点信息输出，再用邻接表找到与其相连的景点并输出信息 ### 3.3.1 实现代码 ```c++ void SearchVex(int n)//查找编号为n的景点 { if(created)//图已被创建 { if(n<0||n>G.maxvexno||AdjList[n].vex.tag==0)//编号n不在文件读入的编号范围内或其标记为0 cout<<"该景点不存在！"<<endl; else {//输出景点编号、名称和景点信息，以及相邻的各个景点编号、名称和相距距离 cout<<n<" "<<AdjList[n].vex.name<<" "<<AdjList[n].vex.info<<endl; cout<<"相邻景点："<<endl; for(int i=0;i<=G.maxvexno;i++) if(AdjList[i].vex.tag) if(G.arc[i][n]<INFINITY) cout<<i<<" "<<AdjList[i].vex.name<<" "<<G.arc[i][n]<<endl; } } else//图未被创建 cout<<"尚未读取文件创建图！"<<endl; } ``` ### 3.3.2 截图  ## 3.4 修改图保存文件 插入、删除、修改顶点、边的信息，注意顶点和边的关系，之后保存文件，重新读取文件建立图的存储结构并显示。 核心操作：首先要保证添加、删除后仍为连通图（因此添加景点也要添加一条边，删除顶点也要删除�