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

数据结构课外实践报告项目名称：所在班级：小组成员：指导教师：起止时间：安阳师范学院·数据结构课外实践·课外实践评定成绩记录指导教师意见系统完成情况：优良中差报告完成情况：优良中差答辩评定成绩团队整体成绩：成员成绩姓名学号综合成绩安阳师范学院·数据结构课外实践·项目基本信息项目名称景区旅游信息管理系统项目简介在在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。小组成员任务分工xxx：导游线路图的创建，最短路径与最短距离，实践报告填写xxx：景区分布图的创建与输出，ppt制作xxx：拓扑排序判断导游线路图是否有回路，实践报告填写xxx：道路修建规划图的创建与输出，ppt制作一、问题描述及分析任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。（1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略，这也比较符合游客心理。（2）为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。（3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。（4）在景区建设中，道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。二、功能模块及结构描述1.由上述描述归纳起来，本任务有如下功能模块：创建景区景点分布图，在程序中由CreateGraph(ALGraph&G)函数实现；输出景区景点分布图（邻接矩阵），在程序中由OutputGraph(ALGraphG)函数实现；安阳师范学院·数据结构课外实践·输出导游线路图，在程序中由CreatTourSortGraph(G,G1)函数实现；判断导游线路图有无回路，在程序中由TopoSort(G1)函数实现；求两个景点间的最短路径和最短距离，在程序中由MiniDistanse(G1,path,D)函数实现；输出道路修建规划图，在程序中由MiniSpanTree(G,G.adjlist[0].name)函数实现。主程序用菜单选项由ShowMenu()函数供用户选择功能模块。2.景点的信息包括景点的名称和近邻景点之间的通路和距离。用邻接链表存储景点分布图的信息，（带权无向）图的邻接链表。三、主要流程描述主程序采用设计主菜单调用若干功能模块，同时在主程序中定义两个邻接链表类型变量G和G1，作为调用子函数的参数。建图子模块建立无向带权图，输入顶点信息和边的信息，输出邻接链表G。由于是无向边，输入一条边时构建两条边。安阳师范学院·数据结构课外实践·输出图子模块：从邻接链表g转换成邻接矩阵a，并输出邻接矩阵a。图中边的权值∞用32767表示。遍历子模块：通过遍历图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。如果vi-2和vi+1还不存在边，继续回溯，一定能找到某个整数k（因为景点分布图是连通图），使得vi-k和vi+1存在边，则加入边vi-k→vi+1。在本任务中，转换后的线路图存于数组vex1中。三、使用说明程序运行后，进入界面（如下图4）：图4初始界面在如上所示的界面下进行基本的操作，在程序测试中选用如下（图5）所示的图作为景区景点分布图V1V2V4V5V8V3V6V7安阳师范学院·数据结构课外实践·图5景点分布在将以上景点分布输入程序创建景区景点分布图程序实现过程及输出景区景点分布图和导游路线图的程序运行结果如下如图6所示。图6创建输出景区景点分布图及导游路线图程序功能4到功能6的测试结果如下图7所示：安阳师范学院·数据结构课外实践·图7其它测试结果四、问题及解决方法问题1：在深度遍历景区景点分布图时，由于使用的是邻接表，在递归回溯时，指针P一直向后找当前结点的邻接点直到变为空，但是再次回溯时，P应该是当前结点的头结点的下一个结点开始，但是P却一直为空.解决方法：在递归调用深度遍历函数后面，紧接着把头结点再次赋值给P，然后P后移，相当于依然是从第一个结点的下一个邻接点开始。问题2：不知该怎样输出导游线路图中的回路。解决方法：利用拓扑排序，将拓扑出来的景点存放在一个数组中，最后通过和所有的顶点比较，如果该顶点在该数组中就说明不在环中，如果不在就说明在环中，则输出它。五、课外实践总结通过这次课外实践，我们对本学期所学的数据结构课程有关知识进行了巩固，同时也体会到了团队合作的重要性。从最初的问题的讨论，分工到最后的具体程序实现大家遇到了不少的问题，我们在一起辩论，去图书馆查阅资料，在网上查询资料，大家在一起通力合作解决了遇到的各种问题，最后完成了此次的课外实践。安阳师范学院·数据结构课外实践·经过这次的课外实践，我们在对课本所学的知识有了更深的了解的同时，也学会了用所学的知识解决实际的问题，我们小组成员在一起共同学习，共同进步，取得了一定的实践效果。但是，在此期间也我们也发现了各自的不足。这激励着大家在以后的学习过程中更加努力，去积极的克服这些问题，提升自己的能力。六、源代码//结构的定义以及函数的声明（travels.h）#ifndefTRAVELS_H_H#defineTRAVELS_H_H#includestring#includeiostreamusingnamespacestd;#defineINFINITY32767#defineMAX_VERTEX_NUM20externdouble**a;//定义存储原图顶点矩阵的全局数组typedefstructArcNode{intadjvex;structArcNode*nextarc;doublew;}ArcNode;//定义顶点信息typedefstructVNode{stringname;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];//定义边信息typedefstruct{AdjListadjlist;intvexnum,arcnum;}ALGraph;//定义邻接表typedefstructedge{stringvex;intlowcost;安阳师范学院·数据结构课外实践·}Edge[MAX_VERTEX_NUM];//定义辅助数组voidShowMenu();//显示菜单boolIsZeroOrOne(intn);intLocateVex(ALGraphG,stringv);//寻找要查找顶点位置voidCreatGraph(ALGraph&G);//创建图的邻接表存储voidOutputGraph(ALGraphG);//输出图的邻接表intMininum(ALGraphG,Edgea);//寻找还没有纳入最小生成树中的边的最小值voidMiniSpanTree(ALGraphG,stringu);//求最小生成树voidDFS(ALGraphG,intv);//递归遍历voidDFSTraverse(ALGraphG);//图的深度遍历boolIsEdge(ALGraphG,stringv1,stringv2);//判断要查的这两个顶点之间是否有直接相连的边voidCreatTourSortGraph(ALGraphG,ALGraph&G1);//创建导游线路图intTopoSort(ALGraphG1);//拓扑排序voidFindInDegree(ALGraphG1,intindegree[]);//计算每个顶点的入度，存储在indegree数组中voidShortestPath(ALGraphG,intpath[][MAX_VERTEX_NUM],doubleD[][MAX_VERTEX_NUM]);//计算最短路径voidOutPutShortestPath(ALGraphG,intpath[][MAX_VERTEX_NUM],doubleD[][MAX_VERTEX_NUM],inti,intj);//求最短路径voidMiniDistanse(ALGraphG,intpath[][MAX_VERTEX_NUM],doubleD[][MAX_VERTEX_NUM]);//输出最短路径boolIsOperate(intn);//判断是否为操作数#endif//功能函数的实现（Test.cpp）#includetravels.hvoidShowMenu(){cout;cout=====================endl;cout;cout欢迎使用景区旅游信息管理系统endl;cout;cout**请选择菜单**endl;cout;cout=====================endl;安阳师范学院·数据结构课外实践·cout;cout0、退出系统。endl;cout;cout1、创建景区景点分布图。endl;cout;cout2、输出景区景点分布图。endl;cout;cout3、输出导游线路图。endl;cout;cout4、输出导游线路图中的回路。endl;cout;cout5、求两个景点间的最短路径和最短距离。endl;cout;cout6、输出道路修建规划图。endl;}boolIsOperate(intn){if(n==0||n==1||n==2||n==3||n==4||n==5||n==6)//如果不是操作数就返回真，否则假returntrue;returnfalse;}boolIsZeroOrOne(intn){if(n==0||n==1)returntrue;returnfalse;}intLocateVex(ALGraphG,stringv){for(inti=0;iG.vexnum;i++)if(v==G.adjlist[i].name)//判断要查找的顶点是否存在returni;//返回找到的顶点位置return0;}voidCreatGraph(ALGraph&G){cout请输入顶点数和边数：;cinG.vexnumG.arcnum;coutendl\请输入各顶点的信息\endlendl;安阳师范学院·数据结构课外实践·cout请输入各顶点的名字：;inti=0,j;for(;iG.vexnum;i++)//对图的顶点进行初始化{cinG.adjlist[i].name;G.adjlist[i].firstarc=NULL;}intw;stringv1,v2;for(intk=0;kG.arcnum;k++){cout请输入第k+1条边的两个顶点以及该边的权值：;cinv1v2w;i=LocateVex(G,v1);j=LocateVex(G,v2);ArcNode*P=newA