景区旅游信息管理系统.doc

校园旅游信息管理系统 项目需求分析在旅游景区,经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离,这类游客不喜欢按照导游图的线路来游览, 而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询, 就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统, 实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。任务中景点分布是一个无向带权连通图,图中边的权值是景点之间的距离。 1 )景区旅游信息管理系统中制订旅游景点导游线路策略,首先通过遍历景点,给出一个入口景点, 建立一个导游线路图, 导游线路图用有向图表示。遍历采用深度优先策略, 这也比较符合游客心理。(2 )为了使导游线路图能够优化,可通过拓朴排序判断图中有无回路,若有回路,则打印输出回路中的景点,供人工优化。(3 )在导游线路图中,还为一些不愿按线路走的游客提供信息服务,比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。(4 )在景区建设中,道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点, 但又要花最小的代价, 可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。因此归纳起来,本任务有如下功能模块: 创建景区景点分布图; 输出景区景点分布图(邻接矩阵) 输出导游线路图; 判断导游线路图有无回路; 求两个景点间的最短路径和最短距离; 输出道路修建规划图。主程序用菜单选项供用户选择功能模块。 项目设计流程 项目总体框架校园旅游信息管理系统创建景区景点分布图输出景区景点分布图输出景区导游线路图导游线路图有无回路两个景点间的最短路径输出道路修建规划图 项目数据结构#ifndef ESS // 标志位成功#define ESS 1 #endif #ifndef FAILURE // 标志位失败#define FAILURE 0 #endif #ifndef INF // 标志位无穷#define INF 0x3f3fffff #endif #ifndef MAXNUM #define MAXNUM 20 #endif typedef bool STATUS; // 定义函数状态数据类型 typedef char VERTEXTYPE[MAXNUM][11]; // 定义顶点向量数据类型 typedef int ADJMATRIX[MAXNUM][MAXNUM]; // 定义邻接矩阵数据类型 typedef struct GRAPH // 定义图数据类型{ VERTEXTYPE Vexs; // 图的顶点向量 ADJMATRIX Arcs; // 图的邻接矩阵 int VexNum; // 图的当前顶点 int um; // 图的当前弧}*PGRAPH; // 定义图的指针数据类型 typedef struct CLOSEDGE // 定义辅助数组数据类型{ VERTEXTYPE Vexs; // 图的顶点向量 int Lowcost[MAXNUM]; // }*PCLOSEDGE; // 定义辅助数组指针数据类型 项目模块设计创建景区景点分布图一. 邻接矩阵(Adjacency Matrix)( 二维数组表示法) 在图的邻接矩阵表示中, 有一个记录各个顶点信息的顶点表, 还有一个表示各个顶点之间关系的邻接矩阵。设图 A= (V, E) 是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 [n][n] ,定义( 满足如下条件的 n 阶矩阵) : 无向图数组表示法特点: 1 )无向图邻接矩阵是对称矩阵,同一条边表示了两次; 2 )顶点 v 的度:在无向图中等于二维数组对应行(或列)中 1 的个数;在有向图中, 统计第i 行1 的个数可得顶点 i 的出度,统计第 j 列1 的个数可得顶点 j 的入度。 3 )判断两顶点 v 、u 是否为邻接点:只需判二维数组对应分量是否为 1 ; 4 )顶点不变,在图中增加、删除边:只需对二维数组对应分量赋值 1 或清 0 ; 5 ) 设存储顶点的一维数组大小为 n( 图的顶点数 n), G 占用存储空间: n+n 2;G 占用存储空间只与它的顶点数有关,与边数无关;适用于边稠密的图; 流程图: ?????? otherwise or if 0, )E j) (i, >, (< ,1] ][[.A Ejiji Edge 程序: // 创建景区景点分布图 STATUS CreateGraph(PGRAPH pGraph) { printf("\t\t\t_________________________________\