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

校园旅游信息管理系统1。1项目需求分析在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览.为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。任务中景点分布是一个无向带权连通图,图中边的权值是景点之间的距离.1)景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点,建立一个导游线路图，导游线路图用有向图表示.遍历采用深度优先策略,这也比较符合游客心理.(2)为了使导游线路图能够优化,可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点,供人工优化.（3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。（4）在景区建设中,道路建设是其中一个重要内容.道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题.本任务中假设修建道路的代价只与它的里程相关.因此归纳起来，本任务有如下功能模块:创建景区景点分布图；输出景区景点分布图（邻接矩阵）输出导游线路图;判断导游线路图有无回路；求两个景点间的最短路径和最短距离；输出道路修建规划图。主程序用菜单选项供用户选择功能模块。1。2项目设计流程 1。2.1项目总体框架校园旅游信息管理系统创建景区景点分布图输出景区景点分布图输出景区导游线路图导游线路图有无回路两个景点间的最短路径输出道路修建规划图1.2.2项目数据结构#ifndef SUCCESS/标志位成功#define SUCCESS1endififndef FAILURE/标志位失败define FAILURE0#endif#ifndef INF /标志位无穷define INF 0x3f3fffffendififndef MAXNUM define MAXNUM20endiftypedef bool STATUS；/定义函数状态数据类型typedef char VERTEXTYPEMAXNUM11；/定义顶点向量数据类型typedef int ADJMATRIXMAXNUMMAXNUM；/定义邻接矩阵数据类型typedef struct GRAPH/定义图数据类型VERTEXTYPE Vexs；/图的顶点向量ADJMATRIX Arcs；/图的邻接矩阵int VexNum；/图的当前顶点int ArcNum；/图的当前弧PGRAPH；/定义图的指针数据类型typedef struct CLOSEDGE/定义辅助数组数据类型VERTEXTYPE Vexs;/图的顶点向量int LowcostMAXNUM；/*PCLOSEDGE；/定义辅助数组指针数据类型1。2.3项目模块设计创建景区景点分布图一. 邻接矩阵 （Adjacency Matrix）（二维数组表示法)在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表,还有一个表示各个顶点之间关系的邻接矩阵。设图 A = (V， E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A。edgenn,定义(满足如下条件的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占用存储空间只与它的顶点数有关,与边数无关；适用于边稠密的图；流程图：程序:/创建景区景点分布图STATUS CreateGraph(PGRAPH pGraph）printf（”ttt_n）;printf（”nttt$t创建景区景点分布图tn”)；printf（”ttt_n)；/初始化图的顶点数printf(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按任意键回主菜单！”）；getch（）;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请输入弧的信息（注：从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（const 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”）；printf（”按任意键回主菜单！”）；getch()；return SUCCESS；输出景区导游线路图图的遍历从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历 （Traversing Graph）。图中可能存在回路，且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问,可设置一个标志顶点是否被访问过的辅助数组 visited .辅助数组 visited 的初始状态为 0, 在图的遍历过程中, 一旦某一个顶点 i被访问， 就立即让 visited i 为 1, 防止它被多次访问。两种图的遍历方法:深度优先搜索 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有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程,直至图中所有顶点都被访问到为止。流程图:程序：/输出景区导游线路图(注:广度优先遍历)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，pGraphVexNum)=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（QueueLen（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网中不应该出现有向环.因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。判定网中是否存在环的方法:对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中,则该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 如何进行？输入AOV网络。令 n 为顶点个数。（1)在AOV网络中选一个没有直接前驱的顶点，并输出之；（2）从图中删去该顶点， 同时删去所有它发出的有向边；重复以上步骤，直到全部顶点均已输出，拓扑有序序列形成,拓扑排序完成;或图中还有未输出的顶点，但已跳出处理循环.这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环.在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点,在表头结点中增加一个存放顶点入度的域count,这些表头结点构成一个数组。为了避免重复检测入度为0的点,另设一栈存放所有入度为0的点.对于有n个顶点和e条边的有向图而言，for循环中建立入度为0的顶点栈时间为O(n）；若在拓扑排序过程中不出现有向环,则每个顶点出栈、入栈和入度减1的操作在while循环语句中均执行e次,因此拓扑排序总的时间花费为O (n+e).流程图：程序：/有向图的拓扑排序STATUS TopologicalSort(const PGRAPH pGraph）printf(”ttt_n）;printf（ntttt导游线路图有无回路tn”）;printf（”ttt_nn”）；/定义入度数组，记录每个顶点的入度，初始化为0int IndegreeMAXNUM=0;/定义桟、并初始化桟STACK Stack；if(InitStack（Stack，pGraph-VexNum）=FAILURE)printf(”ttt警告：创建桟失败!！n”）；printf(”ttt按任意键回主菜单!！）；getch（);return FAILURE；printf（ttt计算各顶点的入度。n”）;for(int j=0；jpGraph-VexNum;j+）/求各个顶点的入度for（int i=0;ipGraphVexNum;i+）if（pGraph-Arcsij！=INF）Indegreej+;/入度为0的顶点入栈 if(！Indegreej）PushStack（Stack,j);printf（ttt进行拓扑排序.。.。n”）；/Count用来指示入度为0的顶点个数int Count=0，k；while（StackLen(&Stack）/出桟、并访问PopStack(Stack，k）;printf（%st”，pGraph-Vexsk）；Count+;/对出栈的顶点所指向的顶点减一 ，并且将入度为0的顶点入栈for（int i=0;ipGraphVexNum；i+）if（pGraphArcski!=INF）if（！(-Indegreei）)PushStack(Stack，i）；/销毁桟DestroyStack（Stack）;/判断是否是拓扑排序if（CountVexNum)printf(”ttt结果:导游线路图有回路n”)；elseprintf（”ttt结果：导游线路图无回路n”）;printf(”ttt按任意键回主菜单！!！”);getch(）；return SUCCESS；求两个景点间的最短路径最短路径定义所谓最短路径问题是指：如果从图中某一顶点（源点）到达另一顶点(终点)的路径可能不止一条，如何找到一条路径似的沿此路径上各边的权值总和（称为路径长度）达到最小.迪杰斯特拉（Dijkstra）算法求单源最短路径由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法.(1)按路径长度递增序产生各顶点最短路径若按长度递增的次序生成从源点s到其它顶点的最短路径,则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成(将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。（2）具体做法一开始第一组只包括顶点 v 1 ，第二组包括其他所有顶点， v 1 对应的距离值为 0 ，第二组的顶点对应的距离值是这样确定的：若图中有边 v 1 ， v j ， 则 v j 的距离为此边所带的权值,否则 v j 的距离值为一个很大的数 ( 大于所有顶点间的路径长度 ) ，然后每次从第二组的顶点中选一个其距离值为最小的 v m 加入到第一组中.每往第一组加入一个顶点 v m ,就要对第二组的各个顶点的距离值进行一次修正。若加进 v m 做中间顶点，使从 v 1 到 v j 的最短路径比不加 v m 的路径为短，则要修改 v j 的距离值。修改后再选距离最小的顶点加入到第一组中。如此进行下去，直到图中所有顶点都包括在第一组中，或再也没有可加入到第一组中的顶点存在为止。假设有向图 G 的 n 个顶点为 1 到 n, 并用邻接矩阵 cost 表示 , 若 v i ， v j 是图 G 中的边，则 costij 的值等于边所带的权 ； 若 v i ， v j 不是图 G 中的边,则 costij 等于一个很大的数；若 i=j， 则 costij=0 。另外 , 设置三个数组 Sn 、 distn 、 pren . S 用以标记那些已经找到最短路径的顶点，若 Si1=1， 则表示已经找到源点到顶点 i 的最短路径 , 若 Si-1=0， 则表示从源点到顶点 i 的最短路径尚未求得。 disti1 用来记录源点到顶点 i 的最短路径。 prei1 表示从源点到顶点 i 的最短路径上该点的前趋顶点,若从源点到该顶点无路径,则用 0 作为其前一个顶点序号。流程图:程序:/求两个景点间的最短路径STATUS MinShortPath（const PGRAPH pGraph)printf（”ttt_n”）;printf（”ntttt景点之间的最短路径t$n)；printf（ttt_nn”）；/定义路径矩阵、距离矩阵ADJMATRIX PathMatrix,DisMatrix;/定义辅助变量int i,j，k;/初始化路径矩阵、距离矩阵for（i=0;ipGraphVexNum;i+）for（j=0；jArcsij；PathMatrixij=-1;/求PathMatrix矩阵for(k=0；kpGraph-VexNum;k+）for（i=0；ipGraph-VexNum；i+）for（j=0；jpGraphVexNum;j+)if（DisMatrixijDisMatrixik+DisMatrixkj)DisMatrixij=DisMatrixik+DisMatrixkj；PathMatrixij=k；/定义起点、终点int Stav=1，Endv=1;/定义起点、终点名称char StaNamMAXNUM，EndNamMAXNUM;printf（”ttt输入起始点和终点名称（格式:Sta End）：);scanf（”%ss，StaNam，EndNam)；for（i=0；iVexsStav）；if（!StackLen（Stack）break；PopStack（Stack，Stav)；printf（”终点”）;/销毁桟DestroyStack（Stack）；printf(”nttt按任意键回主菜单！”）；getch（）;return SUCCESS；输出道路修建规划图prim算法在无向加权图中，n个顶点的最小生成树有n1条边，这些边使得n个顶点之间可达,且总的代价最小.prim算法是一种贪心算法,将全部的顶点划分为2个集合,每次总在2个集合之间中找最小的一条边，局部最优最终达到全局最优,这正是贪心的思想.具体的描述参见相关书籍:描述从单一顶点开始,普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点.1。输入：一个加权连通图，其中顶点集合为V，边集合为E； 2。初始化：Vnew = x,其中x为集合V中的任一节点（起始点），Enew = ; 3。重复下列操作，直到Vnew = V: 1。在集合E中选取权值最小的边（u， v），其中u为集合Vnew中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； 2。将v加入集合Vnew中，将（u， v）加入集合Enew中； 4.输出：使用集合Vnew和Enew来描述所得到的最小生成树.例如：流程图：程序：/输出道路修建规划图（注:最小生成树）STATUS MininumCST（const PGRAPH pGraph）printf（ttt_n）；printf（ntttt输出道路修建规划图tn”);printf(”ttt_nn”）；/定义辅助数组变量CLOSEDGE Closedge;int Min=0；/初始化辅助数组，从第一个顶点开始for（int i=1;ipGraphVexNum；i+)Closedge.Lowcosti=pGraphArcsMini；strcpy（Closedge。Vexsi，pGraphVexsMin）；Closedge.LowcostMin=0；/选这其余的pGraph-VexNum1个点for（i=1；iVexNum;j+)if（Closedge.Lowcostj！=0)break;Min=j;/查找辅助数组中最小值for（j=0;jpGraph-VexNum；j+）if（Closedge。LowcostjClosedge。LowcostjClosedge.LowcostMin)Min=j;/输出信息printf（”tttts-%sn”，Closedge。VexsMin，pGraphVexsMin);/Closedge。LowcostMin=0；/选择最小边for（j=0;jpGraphVexNum;j+）if(pGraphArcsMinjClosedge.Lowcostj)Closedge.Lowcostj=pGraphArcsMinj；strcpy(Closedge。Vexsj，pGraphVexsMin）;printf(nttt按任意键回主菜单!”）；getch(）；return SUCCESS；1。3项目编码实现include stdio。hinclude stdlib。hinclude Graph.h”int Frame（）printf（”ttt_n”）；printf(”ntttt景区旅游信息管理系统tn”)；printf(”ttt_nn”）；printf(ttt1。创建景区景点分布图nn)；printf(ttt2。保存景区景点分布图nn”）；printf（”ttt3。读取景区景点分布图nn”）；printf（”ttt4。输出景区景点分布图nn”);printf（”ttt5。输出景区导游线路图nn”)；printf（”ttt6。导游线路图有无回路nn）；printf（”ttt7。景点之间的最短路径nn”）；printf（”ttt8.输出道路修建规划图nn”）;printf（ttt9。退出信息管理系统nn”）;printf（”ttt请选择相应功能：”)；return 0；int Menu(）GRAPH Graph；int Select；while（1）system（”cls）；Frame（)；scanf（”%d，Select）;system(”cls”）;switch（Select)case 1:CreateGraph(&Graph）；break;case 2：SaveGraph(&Graph);break;case 3：ReadGraph(Graph）；break;case 4：PrintGraph（Graph）；break；case 5:TraverseGraph（Graph）；break;case 6：TopologicalSort（&Graph）；break；case 7：MinShortPath（Graph)；break；case 8:MininumCST（&Graph);break;case 9：return 0;default：break;int main（）Menu（）;return 0;主界面：创建景区景点分布图：输出景区景点分布图：输出景区导游线路图：有向图的拓扑排序:求两个景点间的最短路径:输出道路修建规划图：1。3项目心得体会通过本次景区旅游管理系统的开发,我对数据结构的图有了基本的了解。我对图这章的知识有了一个结构的框架，对于一些以前自己从未见过的算法有了一定的了解，并能够自己写出来，这是对我能力的一种提高在编码方面。在开发这个系统时，遇到了很多的难题，例如：求最短路径等比较有难度的算法时不得不上网查大量的资料,结合书本上写的慢慢的理解,这真是一个漫长的过程，可能有时一天也不能弄懂一个算法的本质。我凭着不放弃的心态,最终还是克服了重重困难,解决了自己从未解决过的难题.这也是自己的一个突破。在系统开发的过程中依然有一些本质性的问提没有解决,我现在没有过多的深究，但我相信我会在以后的学习中一一解决这些难题。例如：求顶点之间的最短路径我一直还不懂求PATH数组。在系统开发的过程中我学到了很多的新的知识，最重要的就是学会了一种思想。模块化思想,以前老师总是提到我们以后写代码不必写那么多，拿来用就行，我一直不懂他的意思，原来是当你的模块被集成之后，以后这些模块就可以不必写了可以直接引用。例如:这次我用到了桟和队列的知识，我以前就写过，如果我要是重新去写又得花一定的时间,这并不是一个好的习惯,我以前写过集成了我拿来用不就行了吗,这样提高了编码的速度提高了效率。不过代码重用的考虑很多的东西，要求比较高。总的来说这次系统开发我学到了很多。