景区旅游管理系统.pdf

《景区旅游管理系统.pdf》由会员分享，可在线阅读，更多相关《景区旅游管理系统.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 景区旅游管理系统 景区旅游信息管理系统 1.1.1 项目需求 在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。（1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图

2、用有向图表示。遍历采用深度优先策略，这也比较符合游客心理。（2）为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。（3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。（4）在景区建设中，道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。因此归纳起来，本任务有如下功能模块：创建景区景点分布图；输出景区景点分布图（邻接矩阵）输出

3、导游线路图；判断导游线路图有无回路；求两个景点间的最短路径和最短距离；输出道路修建规划图。主程序用菜单选项供用户选择功能模块。1.1.2 设计流程 主程序采用设计主菜单调用若干功能模块，同时在主程序中定义两个邻接链表类型变量 G 和G1，作为调用子函数的参数。建图子模块建立无向带权图，输入顶点信息和边的信息，输出邻接链表 G。由于是无向边，输入一条边时构建两条边。输出图子模块：从邻接链表 g 转换成邻接矩阵a，并输出邻接矩阵 a。图中边的权值用 32767表示。遍历子模块：通过遍历图 G，只得到遍历的顶点序列。我们先将顶点序列存在数组 vex 中，然后再转换成导游线路存入数组 vex1 中，最

4、后生成导游线路图 G1（同样用邻接链表存储，供拓朴排序用）。将遍历顶点序列转换成导游线路。图 10-43（a）（b）（c）三个无向图的深度优先搜索遍历的结果均为 v1v2v3v4。但它们的导游线路图却不同。图（a）的导游线路图为v1v2v3v4，与遍历结果相同。图（b）的 导 游 线 路 图 为v1v2v3v2v4，图（c）的导游线路图为v1v2v3v2v1v4。遍历结点序列与导游线路图转换的策略：设遍历结果为v1v2vivi+1vn 对于结点 vi 和 vi+1，如果 vi 和 vi+1存在边，则直接转换。否则，加入边 vivi-1，如果 vi-1 和 vi+1存在边，则加入边 vi-1vi

5、+1。再否则，加入边 vi-1vi-2，如果 vi-2 和 vi+1存在边，则加入边 vi-2vi+1。如果 vi-2 和 vi+1 还不存在边，继续回溯，一定能找到某个整数 k（因为景点分布图是连通图），使得 vi-k 和 vi+1 存在边，则加入边vi-kvi+1。在本任务中，转换后的线路图存于数组 vex1中。流程图见 10-29。拓朴排序子模块流程图，见图 10-39 源程序，参见 10.7 节的 samp10-8.c。求最短路径子模块流程图：见 10-34。源程序，参见 10.6 节的 samp10-6.c。求最小生成树子模块流程图：见 19-33。源程序，参见 10.6 节的 sa

6、mp10-5.c。1.1.3 数据结构 景点的信息包括景点的名称和近邻景点之间的通路和距离。用邻接链表存储景点分布图的信息。（带权无向）图的邻接链表 /*/*程序功能：建立一个旅游景区管理系统，实现旅游路线选择 */*景区道路优化等功能 */*/#include“stdio.h”#include“stdlib.h”#include“string.h”#define MAX_EDGE_NUM100/*定义图的最大边数*/#define MAX_VERTEX_NUM 20#define MAXNUM 32767 typedef char Vertex_type10;typedef struct n

7、ode/*边表结点*/int adjvex;/*邻接点域*/int weight;struct node*next;/*指向下一个邻接点的指针域*/Edge_node;typedef struct/*顶点表结点*/Vertex_type vertex;/*顶点域，存放景点名称*/Edge_node*firstedge;/*边表头指针*/Vertex_node;typedef struct Vertex_node adjlistMAX_VERTEX_NUM;/*邻接表*/int n,m;/*顶点数和边数*/Lgraph;边的类型定义 在求最小生成树时，用到边的定义。typedef struct

8、inti;/*顶点 vi 的序号*/int j;/*顶点 vi 的序号*/intweight;Edge_type;1.1.4 程序清单 主程序源程序/*/*函 数 名：main */*入口参数：无 */*返 回 值：无 */*/voidmain()Lgraph*g,*g1;int sele;void create_graph();void output_graph();void dfs_main();void topo_sort_main();void min_distance_main();void min_tree();g=(Lgraph*)malloc(sizeof(Lgraph);g-

9、m=0;g1=(Lgraph*)malloc(sizeof(Lgraph);while(1)system(cls);printf(“nn*景区旅游管理信息系统*n”);printf(“1.输入景点分布图n”);printf(“2.输出景点分布图邻接矩阵n”);printf(“3.生成导游线路图n”);printf(“4.输出导游线路图中回路n”);printf(“5.求两景点间最短路径和最短距离n”);printf(“6.输出景区道路修建规划图n”);printf(“0.退出n”);printf(“请选择功能序号:”);scanf(“%d”,&sele);printf(nn*nn);switc

10、h(sele)case 1:create_graph(g);break;case 2:output_graph(g);break;case 3:dfs_main(g,g1);break;case 4:topo_sort_main(g1);break;case 5:min_distance_main(g);break;case 6:min_tree(g);break;case 0:exit(0);getchar();printf(按回车键继续.);getchar();建图子模块源程序参见 10.3 节的 create_graph()函数。输出图子模块/*/*函 数 名：output_graph

11、*/*函数功能：输 出图 G 的邻接矩 阵 */*入 口 参 数：g-邻 接 链 表 */*返 回 值：无 */*/void output_graph(Lgraph*g)int i,j,n;intaMAX_VERTEX_NUM MAX_VERTEX_NUM;Edge_node*p;if(g-n=0)printf(“景点分布图未输入，无法输出！n”);return;for(i=0;in;i+)for(j=0;jn;j+)if(i=j)aij=0;else aij=MAXNUM;for(i=0;in;i+)p=g-adjlisti.firstedge;while(p!=NULL)j=p-adjve

12、x;aij=p-weight;p=p-next;printf(景点分布图邻接矩阵为:nn);printf(%8s,);for(i=0;in;i+)printf(%8s,g-adjlisti.vertex);for(i=0;in;i+)printf(%8s,g-adjlisti.vertex);for(j=0;jn;j+)printf(%9d,aij);printf(“n”);遍历子模块/*/*函 数 名：dfs_main */*函 数 功 能：生 成 导 游 线 路 图 */*入 口 参 数：g-景 点 分 布 图 */*g1 导游线路图 */*返 回 值：无 */*/voiddfs_main

13、(Lgraph*g,Lgraph*g1)int visitedMAX_VERTEX_NUM;int x,i;int vexMAX_VERTEX_NUM;int j,k,i1,tag;int vex1MAX_VERTEX_NUM;Edge_node*p,*q;for(i=0;in=0)printf(“景点分布图未输入，无法生成导游线图！n”);return;do printf(请输入口景点序号：);scanf(%d,&x);if(x=1&xn)x-;break;else printf(景点号输入有误，请重新输入！n);while(1);j=0;dfs(g,x,visited,vex,&j);/每

14、次调用时，j 初始化为 0 /*构建游览线路，存放在数组Vex1*/i1=0;for(i=0;in-1;i+)j=vexi+1;tag=1;k=0;while(tag)vex1i1+=vexi+k;p=g-adjlistvexi+k.firstedge;while(p!=NULL&p-adjvex!=j)/*判断 vi+k 与 vj 之间有没有边*/p=p-next;if(p=NULL)k-;/*若vi+k与vj之间没有边回溯*/else tag=0;vex1i1+=j;/*建立游览线路图的邻接链表 G1，供拓朴排序用*/for(i=0;in;i+)strcpy(g1-adjlisti.ver

15、tex,g-adjlisti.vertex);g1-adjlisti.firstedge=NULL;for(k=0;kadjvex=j;p-weight=1;/*建立游览线路图时，不考虑边的权值*/q=g1-adjlisti.firstedge;g1-adjlisti.firstedge=p;p-next=q;g1-n=g-n;g1-m=i1-1;/*输出游览线路*/printf(“游览线路为n：”);for(k=0;k”,g-adjlisti.vertex);printf(“%sn”,g-adjlistvex1i1-1.vertex);/*/*函 数 名：dfs */*函数功能：以 Vi 为

16、出发点对邻接表存储的图 G 进行 DFS 搜索 */*入口参数：g-图 G 的邻接表存储 */*i 顶点Vi */*visited 标志顶点是否已被访问的数组 */*vex 存 放 遍 历 时 所 经 过 的 顶 点 */*j 存放位置 */*返 回 值：无 */*/voiddfs(Lgraph*g,int i,int visited,int vex.int*j)int k;static j=0;Edge_node*p;printf(visit vertex:V%sn,g-adjlisti.vertex);/*访问顶点Vi*/vex*j=i;/*遍历结点 vi，存入数组 Vex中*/*j=*j

17、+1;visitedi=1;/*标记 Vi 已访问*/p=g-adjlisti.firstedge;/*取 Vi 边表的头指针*/while(p)/*依次搜索 Vi 的邻接点 Vj，j=p-adjva*/k=p-adjvex;if(!visitedk)/*若 Vj 尚未访问，则以 Vj 为出发点向纵深搜索*/dfs(g,k,visited,vex,j);p=p-next;/*找 Vi 的下一个邻接点*/在本任务中，通过 10.4 节的遍历输出景区旅游导游线路，该线路从入口出发，经过所有旅游景点后到达出口。在输出的导游线图中，有可能出现回路，即一个景点经过两次及两次以上。为了实现导游线路图的优化

18、，首先要判断图中有没有回路，若有，回路由哪几个景点组成。然后尽可能消除回路。比如说可以通过景区之间多修建道路来消除回路。当然，如果确实存在困难，不能彻底消除回路，也最好使回路经过的景点最少。其中，判断导游线路图有无回路，可用拓朴排序来解决，若有回路则输出回路中的景点。要实现这一功能，可直接使用上述程序，存在回路时，输出未能拓朴排序的顶点。main()Lgraph*g;int vexMAX_VERTEX_NUM,aMAX_VERTEX_NUM MAX_VERTEX_NUM,vexnoMAX_VERTEX_NUM;int i,j,n,k;Edge_node*p;for(i=0;in;for(i=0;in;i+)for(j=0;jn;j+)aij=0;for(i=0;iadjlisti.firstedge;while(p!=NULL)j=p-adjvex;aij=p-weight;p=p-next;for(i=0;in;i+)vexnoi=i;k=topo_sort(a,vex,vexno,n);if(k=0)printf(“该图有回路，回路中的景点为：n”);for(i=0;iadjlistvexi.vertex);else printf(“该图没有回路”);1.1.5 运行测试