景区旅游信息管理系统

校园旅游信息管理系统1.1项目需求分析在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略，这也比较符合游客心理。（2）为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。（3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。（4）在景区建设中，道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。因此归纳起来，本任务有如下功能模块：创建景区景点分布图；输出景区景点分布图（邻接矩阵）输出导游线路图；判断导游线路图有无回路；求两个景点间的最短路径和最短距离；输出道路修建规划图。主程序用菜单选项供用户选择功能模块。1.2项目设计流程1.2.1项目总体框架校园旅游信息管理系统创建景区景点分布图输出景区景点分布图输出景区导游线路图导游线路图有无回路两个景点间的最短路径输出道路修建规划图1.2.2项目数据结构#ifndefSUCCESS//标志位成功#defineSUCCESS1#endif#ifndefFAILURE//标志位失败#defineFAILURE0#endif#ifndefINF//标志位无穷#defineINF0x3f3fffff#endif#ifndefMAXNUM#defineMAXNUM20#endiftypedefboolSTATUS;//定义函数状态数据类型typedefcharVERTEXTYPE[MAXNUM][11];//定义顶点向量数据类型typedefintADJMATRIX[MAXNUM][MAXNUM];//定义邻接矩阵数据类型typedefstructGRAPH//定义图数据类型{VERTEXTYPEVexs;//图的顶点向量ADJMATRIXArcs;//图的邻接矩阵intVexNum;//图的当前顶点intArcNum;//图的当前弧}*PGRAPH;//定义图的指针数据类型typedefstructCLOSEDGE//定义辅助数组数据类型{VERTEXTYPEVexs;//图的顶点向量intLowcost[MAXNUM];//}*PCLOSEDGE;//定义辅助数组指针数据类型1.2.3项目模块设计创建景区景点分布图一.邻接矩阵(AdjacencyMatrix)(二维数组表示法）在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[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+n2；G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；流程图：初始化图的顶点数scanf(%d,&pGraph-VexNum);if(pGraph-VexNum20)初始化图的弧数scanf(%d,&pGraph-ArcNum);if(pGraph-ArcNum20)初始化图的顶点名称初始化图的弧权值为最大值输入弧的信息终止otherwiseorif0,)Ej)(i,,(,1]][[.AEjijiEdge程序：//创建景区景点分布图STATUSCreateGraph(PGRAPHpGraph){printf(\t\t\t_________________________________\n);printf(\n\t\t\t$\t创建景区景点分布图\t$\n);printf(\t\t\t_________________________________\n);//初始化图的顶点数printf(\t\t\t初始化顶点数和弧度数......\n);printf(\t\t\t请输入图的顶点数(=20)：);scanf(%d,&pGraph-VexNum);//检查if(pGraph-VexNum20){printf(\t\t\t警告：输入数据错误！！！\n);printf(\t\t\t按任意键回主菜单！！！);getch();returnFAILURE;}//初始化图的弧数printf(\t\t\t请输入图的弧度数(=20)：);scanf(%d,&pGraph-ArcNum);//检查if(pGraph-ArcNum20){printf(\t\t\t警告：输入数据错误！！！\n);printf(\t\t\t按任意键回主菜单！！！);getch();returnFAILURE;}//初始化图的顶点名称printf(\t\t\t---------------------------------\n);printf(\t\t\t初始化的顶点名称......\n);for(inti=0;ipGraph-VexNum;i++){printf(\t\t\t请输入第%d个顶点名称：,i+1);scanf(%s,pGraph-Vexs[i]);}//初始化图的弧权值为最大值for(i=0;ipGraph-VexNum;i++)for(intj=0;jpGraph-VexNum;j++)pGraph-Arcs[i][j]=INF;//输入弧的信息printf(\t\t\t---------------------------------\n);printf(\t\t\t初始化的弧的信息......\n);printf(\t\t\t请输入弧的信息(注：从0开始)：\n);for(i=0;ipGraph-ArcNum;i++){intStav,Endv,Weight;printf(\t\t\t请输入第%d条弧(格式：ViVjWeight)：,i+1);scanf(%d%d%d,&Stav,&Endv,&Weight);pGraph-Arcs[Endv][Stav]=Weight;pGraph-Arcs[Stav][Endv]=Weight;}printf(\t\t\t创建景区景点分布图成功！！！\n);printf(\t\t\t按任意键回主菜单！！！);getch();returnSUCCESS;}输出景区景点分布图流程图：景区景点名称i=0ipGraph-VexNumprintf(%s\t,pGraph-Vexs[i]);i++景区景点信息i=0ipGraph-VexNumj=0jpGraph-VexNumif(pGraph-Arcs[i][j]==INF)printf(∞\t);printf(%d\t,pGraph-Arcs[i][j]);j++i++终止程序：//输出景区景点分布图STATUSPrintGraph(constPGRAPHpGraph){printf(\t\t\t_________________________________\n);printf(\n\t\t\t$\t显示景区景点分布图\t$\n);printf(\t\t\t_________________________________\n\n);//printf(\t景区景点名称......\n\t);for(inti=0;ipGraph-VexNum;i++)printf(%s\t,pGraph-Vexs[i]);printf(\n\n\t景区景点信息......\n);for(i=0;ipGraph-VexNum;i++){printf(\t___________________________________________________________\n\t);for(intj=0;jpGraph-VexNum;j++)if(pGraph-Arcs[i][j]==INF)printf(∞\t);elseprintf(%d\t,pGraph-Arcs[i][j]);printf(\n);}printf(\t___________________________________________________________\n\t);printf(按任意键回主菜单！！！);getch();returnSUCCESS;}输出景区导游线路图图的遍历从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历(TraversingGraph)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]。辅助数组visited[]的初始状态为0,在图的遍历过程中,一旦某一个顶点i被访问,就立即让visited[i]为1,防止它被多次访问。两种图的遍历方法:深度优先搜索DFS(DepthFirstSearch)广度优先搜索BFS(BreadthFirstSearch)广度优先搜索遍历图(BFS)对连通图，从起始点V到其余各顶点必定存在路径。其中，V-w1,V-w2,V-w8的路径长度为1;V-w7,V-w3,V-w5的路径长度为2;V-w6,V-w4的路径长度为3从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。流程图：定义访问标志数组初始化访问标志数组为false定义队列、并初始化队列if(InitQueue(&Queue,pGraph-VexNum)==FAILURE)否if(!Visit[Vertex])printf(\t\t\t%s景点......\n,pGraph-Vexs[Vertex]);标志访问过Visit[Vertex]=true;出队DeQueue(&Queue,&Vertex);i=0ipGraph-VexNumif(Visit[i]==false&&pGraph-Arcs[Vertex][i]!=INF)是EnQueue(&Queue,i);是i++否while(QueueLen(&Queue));终止程序：//输出景区导游线路图(注：广度优先遍历)STATUSTraverseGraph(constPGRAPHpGraph){printf(\t\t\t_________________________________\n);printf(\n\t\t\t$\t输出景区导游线路图\t$\n);printf(\t\t\t_________________________________\n