景区旅游信息管理系统 数据结构 课外实践报告 小组人员 时彬强 12级物联网工程 潘理想 12级物联网工程 凡正宇 12级物联网工程 万 路 12级物联网工程 问题简述 v首先通过系统管理者输入景区的信息，以确定是一 个什么样的景区分布情况，供游客利用管理系统清 楚地了解到本景区的基本情况（如：景点的名称， 景点间的距离）。 v制订旅游景点导游线路策略，首先通过遍历景点， 给出一个入口景点，建立一个导游线路图，导游线 路图用有向图表示。遍历采用深度优先策略，这也 比较符合游客心理。 v为了使导游线路图能够优化，可通过拓朴排序判断 图中有无回路，若有回路，则打印输出回路中的景 点，供人工优化。 v在导游线路图中，还为一些不愿按线路走的游客提供 信息服务，比如从一个景点到另一个景点的最短路径 和最短距离。在本线路图中将输出任意景点间的最短 路径和最短距离。 v在景区建设中，道路建设是其中一个重要内容。道路 建设首先要保证能连通所有景点，但又要花最小的代 价，通过求最小生成树来解决这个问题。本任务中假 设修建道路的代价只与它的里程相关。 任务功能模块如下： 1）创建景区景点分布图 2）输出景区景点分布图（邻接矩阵） 3）输出导游线路图 4）判断导游线路图有无回路 5）求两个景点间的最短路径和最短距离 6）输出道路修建规划图 小组人员任务分工 v时彬强：导游线路图的创建，最短路径与最短距离 v潘理想：景区分布图的创建与输出 v凡正宇：拓扑排序判断导游线路图是否有回路 v万 路：道路修建规划图的创建与输出 解决问题的具体函数 1）创建景区景点分布图 /寻找要查找顶点位置 int LocateVex(ALGraph G,string v); /创建图的邻接表存储 void CreatGraph(ALGraph 2）输出景区景点分布图（邻接矩阵） /输出图的邻接矩阵 void OutputGraph(ALGraph G); 3）输出导游线路图 void DFS(ALGraph G,int v); /递归遍历 void DFSTraverse(ALGraph G); /图的深度遍历 void CreatTourSortGraph(ALGraph G,ALGraph /创建导游线路图 4）判断导游线路图有无回路 /计算每个顶点的入度，存储在indegree数组中 void FindInDegree(ALGraph G1,int indegree); /拓扑排序 int TopoSort(ALGraph G1); 5）求两个景点间的最短路径和最短距离 /计算最短路径 void ShortestPath(ALGraph G,int path MAX_VERTEX_NUM,double D MAX_VERTEX_NUM); /输出最短路径 void MiniDistanse(ALGraph G,int pathMAX_VERTEX_NUM,double D MAX_VERTEX_NUM); /输出走的路线 void OutPutShortestPath(ALGraph G,int pathMAX_VERTEX_NUM, int i,int j）; 6）输出道路修建规划图 /寻找还没有纳入最小生成树中的边的最小值 int Mininum(ALGraph G,Edge a); /求最小生成树 void MiniSpanTree(ALGraph G,string u); 景区图 v1 v7 v6 v3 v5 v8 v4 v2 v1 v4 v2 v5 v8 v1 v4 v2 v7 v6 v3 v5 v8 v1 v4 v2 v7 v6 v3 v5 v8 v1 v4 v2 导游图 v1 v7 v6 v3 v5 v8 v4 v2 Thats all thank you !