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

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