景区旅游信息管理系统.doc
《景区旅游信息管理系统.doc》由会员分享,可在线阅读,更多相关《景区旅游信息管理系统.doc(15页珍藏版)》请在咨信网上搜索。
1、校园旅游信息管理系统1。1项目需求分析在旅游景区,经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离,这类游客不喜欢按照导游图的线路来游览,而是挑选自己感兴趣的景点游览.为于帮助这类游客信息查询,就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统,实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。任务中景点分布是一个无向带权连通图,图中边的权值是景点之间的距离.1)景区旅游信息管理系统中制订旅游景点导游线路策略,首先通过遍历景点,给出一个入口景点,建立一个导游线路图,导游线路图用有向图表示.遍历采用深度优
2、先策略,这也比较符合游客心理.(2)为了使导游线路图能够优化,可通过拓朴排序判断图中有无回路,若有回路,则打印输出回路中的景点,供人工优化.(3)在导游线路图中,还为一些不愿按线路走的游客提供信息服务,比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。(4)在景区建设中,道路建设是其中一个重要内容.道路建设首先要保证能连通所有景点,但又要花最小的代价,可以通过求最小生成树来解决这个问题.本任务中假设修建道路的代价只与它的里程相关.因此归纳起来,本任务有如下功能模块:创建景区景点分布图;输出景区景点分布图(邻接矩阵)输出导游线路图;判断导游线路图有
3、无回路;求两个景点间的最短路径和最短距离;输出道路修建规划图。主程序用菜单选项供用户选择功能模块。1。2项目设计流程 1。2.1项目总体框架校园旅游信息管理系统创建景区景点分布图输出景区景点分布图输出景区导游线路图导游线路图有无回路两个景点间的最短路径输出道路修建规划图1.2.2项目数据结构#ifndef SUCCESS/标志位成功#define SUCCESS1endififndef FAILURE/标志位失败define FAILURE0#endif#ifndef INF /标志位无穷define INF 0x3f3fffffendififndef MAXNUM define MAXNUM
4、20endiftypedef bool STATUS;/定义函数状态数据类型typedef char VERTEXTYPEMAXNUM11;/定义顶点向量数据类型typedef int ADJMATRIXMAXNUMMAXNUM;/定义邻接矩阵数据类型typedef struct GRAPH/定义图数据类型VERTEXTYPE Vexs;/图的顶点向量ADJMATRIX Arcs;/图的邻接矩阵int VexNum;/图的当前顶点int ArcNum;/图的当前弧PGRAPH;/定义图的指针数据类型typedef struct CLOSEDGE/定义辅助数组数据类型VERTEXTYPE Vex
5、s;/图的顶点向量int LowcostMAXNUM;/*PCLOSEDGE;/定义辅助数组指针数据类型1。2.3项目模块设计创建景区景点分布图一. 邻接矩阵 (Adjacency Matrix)(二维数组表示法)在图的邻接矩阵表示中,有一个记录各个顶点信息的顶点表,还有一个表示各个顶点之间关系的邻接矩阵。设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A。edgenn,定义(满足如下条件的n阶矩阵):无向图数组表示法特点:1)无向图邻接矩阵是对称矩阵,同一条边表示了两次;2)顶点v的度:在无向图中等于二维数组对应行(或列)中1的个数;在有向图中, 统计第 i
6、 行 1 的个数可得顶点 i 的出度,统计第 j 列 1 的个数可得顶点 j 的入度。3)判断两顶点v、u是否为邻接点:只需判二维数组对应分量是否为1;4)顶点不变,在图中增加、删除边:只需对二维数组对应分量赋值1或清0;5)设存储顶点的一维数组大小为n(图的顶点数n), G占用存储空间:n+n2;G占用存储空间只与它的顶点数有关,与边数无关;适用于边稠密的图;流程图:程序:/创建景区景点分布图STATUS CreateGraph(PGRAPH pGraph)printf(”ttt_n);printf(”nttt$t创建景区景点分布图tn”);printf(”ttt_n);/初始化图的顶点数p
7、rintf(ttt初始化顶点数和弧度数.。.。.n);printf(ttt请输入图的顶点数(=20):”);scanf(d,pGraphVexNum);/检查if(pGraph-VexNum20)printf(”ttt警告:输入数据错误!n”);printf(”ttt按任意键回主菜单!!);getch();return FAILURE;/初始化图的弧数printf(”ttt请输入图的弧度数(=20):”);scanf(”%d,pGraphArcNum);/检查if(pGraph-ArcNum20)printf(”ttt警告:输入数据错误!!n);printf(”ttt按任意键回主菜单!”);g
8、etch();return FAILURE;/初始化图的顶点名称printf(ttt-n”);printf(”ttt初始化的顶点名称。.。.。n”);for(int i=0;iVexNum;i+)printf(ttt请输入第d个顶点名称:”,i+1);scanf(%s,pGraphVexsi);/初始化图的弧权值为最大值for(i=0;ipGraphVexNum;i+)for(int j=0;jpGraphVexNum;j+)pGraph-Arcsij=INF;/输入弧的信息printf(”ttt-n”);printf(”ttt初始化的弧的信息。.。.。n”);printf(ttt请输入弧的信
9、息(注:从0开始):n”);for(i=0;iArcNum;i+)int Stav,Endv,Weight;printf(”ttt请输入第%d条弧(格式:Vi Vj Weight):”,i+1);scanf(”ddd,&Stav,Endv,&Weight);pGraph-ArcsEndvStav=Weight;pGraphArcsStavEndv=Weight;printf(ttt创建景区景点分布图成功!!n);printf(”ttt按任意键回主菜单!”);getch();return SUCCESS;输出景区景点分布图流程图:程序:/输出景区景点分布图STATUS PrintGraph(co
10、nst PGRAPH pGraph)printf(ttt_n);printf(”ntttt显示景区景点分布图tn);printf(”ttt_nn”);/printf(”t景区景点名称。.。nt”);for(int i=0;iVexsi);printf(nnt景区景点信息.。.n”);for(i=0;ipGraphVexNum;i+)printf(”t_nt);for(int j=0;jpGraph-VexNum;j+)if(pGraphArcsij=INF)printf(t”);elseprintf(dt”,pGraphArcsij);printf(n);printf(t_nt”);print
11、f(”按任意键回主菜单!”);getch();return SUCCESS;输出景区导游线路图图的遍历从图中某一顶点出发访遍图中所有的顶点,且使每个顶点仅被访问一次,这一过程就叫做图的遍历 (Traversing Graph)。图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问,可设置一个标志顶点是否被访问过的辅助数组 visited .辅助数组 visited 的初始状态为 0, 在图的遍历过程中, 一旦某一个顶点 i被访问, 就立即让 visited i 为 1, 防止它被多次访问。两种图的遍历方法:深度优先
12、搜索 DFS (Depth First Search)广度优先搜索 BFS (Breadth First Search)广度优先搜索遍历图(BFS)对连通图,从起始点V到其余各顶点必定存在路径。 其中,Vw1, Vw2, Vw8的路径长度为1;V-w7, Vw3, V-w5的路径长度为2; Vw6, V-w4 的路径长度为3从图中的某个顶点V0出发,并在访问此顶点之后依次访问V0的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有
13、顶点都被访问到为止。流程图:程序:/输出景区导游线路图(注:广度优先遍历)STATUS TraverseGraph(const PGRAPH pGraph)printf(ttt_n);printf(”ntttt输出景区导游线路图tn”);printf(”ttt_nn);/定义访问标志数组bool Visit=(bool)malloc(pGraph-VexNumsizeof(bool));/初始化访问标志数组为falsefor(int i=0;ipGraphVexNum;i+)Visiti=false;/定义队列、并初始化队列QUEUE Queue;if(InitQueue(Queue,pGra
14、phVexNum)=FAILURE)printf(”ttt警告:创建队列失败!!!n”);printf(”ttt按任意键回主菜单!!”);getch();return FAILURE;/定义访问顶点变量,并初始值为0int Vertex=0;doif(!VisitVertex)printf(”ttts景点.。.。n,pGraphVexsVertex);/标志访问过VisitVertex=true;/遍历与Vertex相连的顶点并进队for(i=0;iArcsVertexi!=INF)EnQueue(&Queue,i);/出队DeQueue(&Queue,&Vertex);while(Queue
15、Len(Queue);/销毁队列DestroyQueue(Queue);printf(ttt按任意键回主菜单!!);getch();return SUCCESS;有向图的拓扑排序何谓“拓扑排序?对有向图进行如下操作:假设G=(V,E)是一个具有n个顶点的有向图,V中顶点序列vl,v2,vn称做一个拓扑序列(Topological Order),当且仅当该顶点序列满足下列条件:若在有向图G中存在从顶点vi到vj的一条路径,则在顶点序列中顶点vi必须排在顶点vj之前.通常,在AOV网中,将所有活动排列成一个拓扑序列的过程叫做拓扑排序(Topological Sort).在AOV网中不应该出现有向环
16、.因为环的存在意味着某项活动将以自己为先决条件,显然无法形成拓扑序列。判定网中是否存在环的方法:对有向图构造其顶点的拓扑有序序列,若网中所有顶点都出现在它的拓扑有序序列中,则该AOV网中一定不存在环.例如:对于有向图可求得拓扑有序序列: A B C D 或 A C B DBcDA例如, 对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6反之,对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路 B, C, D 如
17、何进行?输入AOV网络。令 n 为顶点个数。(1)在AOV网络中选一个没有直接前驱的顶点,并输出之;(2)从图中删去该顶点, 同时删去所有它发出的有向边;重复以上步骤,直到全部顶点均已输出,拓扑有序序列形成,拓扑排序完成;或图中还有未输出的顶点,但已跳出处理循环.这说明图中还剩下一些顶点,它们都有直接前驱,再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环.在实现拓扑排序的算法中,采用邻接表作为有向图的存储结构,每个顶点设置一个单链表,每个单链表有一个表头结点,在表头结点中增加一个存放顶点入度的域count,这些表头结点构成一个数组。为了避免重复检测入度为0的点,另设一栈存放所有入度为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 景区 旅游 信息管理 系统
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。