景区旅游信息管理系统课外实践报告.doc

《景区旅游信息管理系统课外实践报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构课外实践报告项目名称：所在班级：小组成员：指导教师：起止时间：课外实践评定成绩记录指导教师意见系统完成情况：优良中差报告完成情况：优良中差答辩评定成绩团队整体成绩：成员成绩姓名学号综合成绩项目基本信息项目名称景区旅游信息管理系统项目简介在在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现

2、的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。小组成员任务分工xxx：导游线路图的创建，最短路径与最短距离，实践报告填写xxx：景区分布图的创建与输出，ppt制作xxx：拓扑排序判断导游线路图是否有回路，实践报告填写xxx：道路修建规划图的创建与输出，ppt制作一、问题描述及分析任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。　（1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略，这也比较符合游

3、客心理。　（2）为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。　（3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。　（4）在景区建设中，道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。二、功能模块及结构描述1.由上述描述归纳起来，本任务有如下功能模块：

4、　创建景区景点分布图，在程序中由CreateGraph(ALGraph&G)函数实现；输出景区景点分布图（邻接矩阵），在程序中由OutputGraph(ALGraphG)函数实现；　输出导游线路图，在程序中由CreatTourSortGraph(G,G1)函数实现；　判断导游线路图有无回路，在程序中由TopoSort(G1)函数实现；　求两个景点间的最短路径和最短距离，在程序中由MiniDistanse(G1,path,D)函数实现；　输出道路修建规划图，在程序中由MiniSpanTree(G,G.adjlist[0].name

5、)函数实现。　主程序用菜单选项由ShowMenu()函数供用户选择功能模块。2.景点的信息包括景点的名称和近邻景点之间的通路和距离。用邻接链表存储景点分布图的信息，（带权无向）图的邻接链表。三、主要流程描述主程序采用设计主菜单调用若干功能模块，同时在主程序中定义两个邻接链表类型变量G和G1，作为调用子函数的参数。建图子模块建立无向带权图，输入顶点信息和边的信息，输出邻接链表G。由于是无向边，输入一条边时构建两条边。输出图子模块：从邻接链表g转换成邻接矩阵a，并输出邻接矩阵a。图中边的权值∞用32767表示。遍历子模块：通过遍历图

6、G，只得到遍历的顶点序列。我们先将顶点序列存在数组vex中，然后再转换成导游线路存入数组vex1中，最后生成导游线路图G1（同样用邻接链表存储，供拓朴排序用）。将遍历顶点序列转换成导游线路。遍历结点序列与导游线路图转换的策略：　　设遍历结果为v1→v2→…→vi→vi+1→…→vn　　对于结点vi和vi+1，如果vi和vi+1存在边，则直接转换。　　否则，加入边vi→vi-1，如果vi-1和vi+1存在边，则加入边vi-1→vi+1。　　再否则，加入边vi-1→vi-2，如果vi-2和vi+1存在边，则加入边vi-2→vi+1。

7、　　如果vi-2和vi+1还不存在边，继续回溯，一定能找到某个整数k（因为景点分布图是连通图），使得vi-k和vi+1存在边，则加入边vi-k→vi+1。在本任务中，转换后的线路图存于数组vex1中。一、使用说明程序运行后，进入界面（如下图4）：图4初始界面V1在如上所示的界面下进行基本的操作，在程序测试中选用如下（图5）所示的图作为景区景点分布图V3V2V6V5V4V7V8图5景点分布在将以上景点分布输入程序创建景区景点分布图程序实现过程及输出景区景点分布图和导游路线图的程序运行结果如下如图6所示。图6创建输出景区景点分布图及

8、导游路线图程序功能4到功能6的测试结果如下图7所示：图7其它测试结果一、问题及解决方法问题1：在深度遍历景区景点分布图时，由于使用的是邻接表，在递归回溯时，指针P一直向后找当前结点的邻接点直到变为空，但是再次回溯时，P应该是当前结点的头结点的下一个结点开始，但是