景区旅游信息管理系统

景区旅游信息管理系统校园旅游信息管理系统1.1项目需求分析在旅游景区,经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览.为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离.算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统,实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略.任务中景点分布是一个无向带权连通图,图中边的权值是景点之间的距离.1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景...

校园旅游信息管理系统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占用存储空间只与它的顶点数有关,与边数无关；适用于边稠密的图;流程图：程序：//创建景区景点分布图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—〉VexNum>20)｛printf("\t\t\t警告：输入数据错误！!！\n")；printf("\t\t\t按任意键回主菜单！！！"）；getch(）;returnFAILURE；}//初始化图的弧数printf(”\t\t\t请输入图的弧度数（〈=20)："）；scanf（"%d”，＆pGraph—>ArcNum）;//检查if(pGraph—〉ArcNum〉20){printf(”\t\t\t警告：输入数据错误！！！\n”）；printf（"\t\t\t按任意键回主菜单！！!”）;getch()；returnFAILURE;}//初始化图的顶点名称printf（”\t\t\t—————-—--————-—----—-—-———-————--\n")；printf(”\t\t\t初始化的顶点名称.。。..。\n”)；for（inti=0;i〈pGraph-〉VexNum;i++）｛printf("\t\t\t请输入第%d个顶点名称：”,i+1)；scanf（”％s",pGraph->Vexs[i]）；}//初始化图的弧权值为最大值for（i=0；iVexNum;i++）for(intj=0;jVexNum;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；iArcs［Endv］［Stav］=Weight;pGraph->Arcs[Stav］［Endv]=Weight；}printf（”\t\t\t创建景区景点分布图成功!！！\n")；printf（”\t\t\t按任意键回主菜单！！!"）；getch（);returnSUCCESS；｝输出景区景点分布图流程图：程序：//输出景区景点分布图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；i〈pGraph—>VexNum；i++）printf（"％s\t"，pGraph—>Vexs[i]）;printf（"\n\n\t景区景点信息..。。.。\n")；for(i=0;i〈pGraph->VexNum；i++)｛printf（”\t___________________________________________________________\n\t"）；for(intj=0;jVexNum；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有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程,直至图中所有顶点都被访问到为止。流程图：程序：//输出景区导游线路图(注：广度优先遍历）STATUSTraverseGraph(constPGRAPHpGraph){printf("\t\t\t_________________________________\n");printf（"\n\t\t\t$\t输出景区导游线路图\t＄\n”）；printf(”\t\t\t_________________________________\n\n”)；//定义访问标志数组bool*Visit=（bool*)malloc（pGraph—>VexNum＊sizeof(bool));//初始化访问标志数组为falsefor(inti=0；iVexNum;i++)Visit[i］=false;//定义队列、并初始化队列QUEUEQueue；if(InitQueue（&Queue，pGraph->VexNum)==FAILURE){printf（"\t\t\t警告:创建队列失败!！！\n")；printf（"\t\t\t按任意键回主菜单！！！”)；getch（);returnFAILURE；｝//定义访问顶点变量，并初始值为0intVertex=0；do｛if（！Visit［Vertex］）{printf（”\t\t\t%s景点。..。..\n",pGraph—>Vexs［Vertex])；//标志访问过Visit［Vertex]=true;//遍历与Vertex相连的顶点并进队for（i=0;iVexNum;i++）if（Visit［i]==false＆＆pGraph—>Arcs［Vertex］[i］！=INF）EnQueue（&Queue，i）；}//出队DeQueue(&Queue，＆Vertex）；｝while(QueueLen（＆Queue)）；//销毁队列DestroyQueue（&Queue)；printf（"\t\t\t按任意键回主菜单！!！");getch()；returnSUCCESS;}有向图的拓扑排序何谓“拓扑排序”?对有向图进行如下操作:假设G=（V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，…,vn称做一个拓扑序列（TopologicalOrder)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常,在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序（TopologicalSort）.在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列.判定网中是否存在环的方法:对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。例如:对于有向图可求得拓扑有序序列:ABCD或ACBDBcDA例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为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）。流程图：程序：//有向图的拓扑排序STATUSTopologicalSort(constPGRAPHpGraph)｛printf（”\t\t\t_________________________________\n”）；printf(”\n\t\t\t$\t导游线路图有无回路\t$\n")；printf(”\t\t\t_________________________________\n\n”)；//定义入度数组，记录每个顶点的入度，初始化为0intIndegree［MAXNUM]={0};//定义桟、并初始化桟STACKStack;if(InitStack(&Stack，pGraph—>VexNum)==FAILURE){printf("\t\t\t警告:创建桟失败！！!\n”);printf("\t\t\t按任意键回主菜单！!！"）;getch(）；returnFAILURE;}printf（”\t\t\t计算各顶点的入度..。..\n”)；for(intj=0;j〈pGraph->VexNum；j++）{//求各个顶点的入度for（inti=0;iVexNum；i++）if(pGraph->Arcs［i]［j］！=INF）Indegree［j］++；//入度为0的顶点入栈if（！Indegree[j])PushStack（&Stack,j）；｝printf(”\t\t\t进行拓扑排序....。\n"）;//Count用来指示入度为0的顶点个数intCount=0,k;while(StackLen(&Stack)）{//出桟、并访问PopStack（&Stack，&k）;printf（"%s\t"，pGraph—〉Vexs[k］）；Count++；//对出栈的顶点所指向的顶点减一，并且将入度为0的顶点入栈for(inti=0;iArcs[k］［i]!=INF）if（!（—-Indegree［i］)）PushStack(&Stack,i）；｝//销毁桟DestroyStack(＆Stack）;//判断是否是拓扑排序if（Count〈pGraph-〉VexNum）printf（"\t\t\t结果：导游线路图有回路\n");elseprintf("\t\t\t结果：导游线路图无回路\n”);printf(”\t\t\t按任意键回主菜单！！!"）；getch（）;returnSUCCESS;}求两个景点间的最短路径最短路径定义　　所谓最短路径问题是指：如果从图中某一顶点（源点)到达另一顶点（终点)的路径可能不止一条，如何找到一条路径似的沿此路径上各边的权值总和（称为路径长度）达到最小.迪杰斯特拉(Dijkstra)算法求单源最短路径由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。（1）按路径长度递增序产生各顶点最短路径若按长度递增的次序生成从源点s到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径)。（2）具体做法　　一开始第一组只包括顶点v1，第二组包括其他所有顶点，v1对应的距离值为0，第二组的顶点对应的距离值是这样确定的：若图中有边〈v1,vj>,则vj的距离为此边所带的权值，否则vj的距离值为一个很大的数（大于所有顶点间的路径长度)，然后每次从第二组的顶点中选一个其距离值为最小的vm加入到第一组中.每往第一组加入一个顶点vm，就要对第二组的各个顶点的距离值进行一次修正。若加进vm做中间顶点，使从v1到vj的最短路径比不加vm的路径为短，则要修改vj的距离值。修改后再选距离最小的顶点加入到第一组中.如此进行下去，直到图中所有顶点都包括在第一组中，或再也没有可加入到第一组中的顶点存在为止。　　假设有向图G的n个顶点为1到n,并用邻接矩阵cost表示,若〈vi，vj>是图G中的边,则cost［i］[j]的值等于边所带的权；若不是图G中的边，则cost[i］[j］等于一个很大的数；若i=j，则cost［i][j]=0。另外，设置三个数组S[n］、dist［n]、pre[n]。S用以标记那些已经找到最短路径的顶点，若S[i—1]=1，则表示已经找到源点到顶点i的最短路径,若S[i-1］=0,则表示从源点到顶点i的最短路径尚未求得。dist[i—1］用来记录源点到顶点i的最短路径。pre［i—1]表示从源点到顶点i的最短路径上该点的前趋顶点,若从源点到该顶点无路径,则用0作为其前一个顶点序号.流程图：程序://求两个景点间的最短路径STATUSMinShortPath（constPGRAPHpGraph）｛printf(”\t\t\t_________________________________\n”）;printf(”\n\t\t\t$\t景点之间的最短路径\t＄\n”）;printf(”\t\t\t_________________________________\n\n”）;//定义路径矩阵、距离矩阵ADJMATRIXPathMatrix，DisMatrix；//定义辅助变量inti,j,k；//初始化路径矩阵、距离矩阵for(i=0;iVexNum；k++）for(i=0;iVexNum；j++）if(DisMatrix[i］[j］〉DisMatrix［i]［k]+DisMatrix［k]［j]){DisMatrix［i］[j]=DisMatrix[i][k]+DisMatrix［k][j]；PathMatrix[i][j］=k;｝//定义起点、终点intStav=-1，Endv=—1;//定义起点、终点名称charStaNam［MAXNUM],EndNam［MAXNUM]；printf(”\t\t\t输入起始点和终点名称(格式:StaEnd)：”）；scanf（"％s％s”,StaNam,EndNam）;for(i=0；i〈pGraph—〉VexNum；i++）｛if(!strcmp（pGraph—〉Vexs[i],StaNam））//起始点名称下标Stav=i；if(!strcmp(pGraph-〉Vexs[i］，EndNam))//终点名称下标Endv=i;｝//判断起始点名称和终点名称是否存在if（Stav==-1｜｜Endv==—1）returnFAILURE;//定义桟、并初始化STACKStack；if（InitStack(＆Stack,pGraph—〉VexNum）==FAILURE）{printf("\t\t\t警告:创建桟失败!！！\n")；printf(”\t\t\t按任意键回主菜单！！！”)；getch（）；}//将所有路径入桟while(Endv！=—1)｛PushStack(&Stack，Endv);Endv=PathMatrix[Stav][Endv]；}//将所有路径出桟、并输出printf(”\t\t\t”)；while（1）{printf(”％s—->"，pGraph—>Vexs［Stav])；if（！StackLen（&Stack）)break;PopStack（＆Stack，＆Stav）；｝printf（"终点”）;//销毁桟DestroyStack（＆Stack）;printf("\n\t\t\t按任意键回主菜单!!！”）;getch（);returnSUCCESS；｝输出道路修建规划图prim算法在无向加权图中,n个顶点的最小生成树有n-1条边,这些边使得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来描述所得到的最小生成树。例如:流程图：程序：//输出道路修建规划图（注：最小生成树)STATUSMininumCST（constPGRAPHpGraph)｛printf(”\t\t\t_________________________________\n”）;printf(”\n\t\t\t$\t输出道路修建规划图\t$\n”);printf("\t\t\t_________________________________\n\n"）；//定义辅助数组变量CLOSEDGEClosedge；intMin=0;//初始化辅助数组,从第一个顶点开始for(inti=1;iVexNum;i++）｛Closedge.Lowcost［i］=pGraph-〉Arcs［Min]［i］；strcpy(Closedge。Vexs［i],pGraph—〉Vexs［Min]）;｝Closedge.Lowcost[Min］=0;//选这其余的pGraph->VexNum—1个点for（i=1；iVexNum;j++)if(Closedge。Lowcost[j］&&Closedge。Lowcost[j］〈Closedge。Lowcost［Min]）Min=j；//输出信息printf（"\t\t\t\t％s——--〉％s\n"，Closedge.Vexs[Min］，pGraph—>Vexs［Min］）;//Closedge.Lowcost[Min］=0;//选择最小边for(j=0;j〈pGraph->VexNum;j++)if（pGraph->Arcs[Min］[j]Arcs[Min］［j];strcpy（Closedge.Vexs［j],pGraph—〉Vexs[Min]）;}}printf（"\n\t\t\t按任意键回主菜单！！!");getch();returnSUCCESS;}1.3项目编码实现#include 心得体会通过本次景区旅游管理系统的开发，我对数据结构的图有了基本的了解.我对图这章的知识有了一个结构的框架，对于一些以前自己从未见过的算法有了一定的了解，并能够自己写出来,这是对我能力的一种提高在编码方面。在开发这个系统时,遇到了很多的难题，例如:求最短路径等比较有难度的算法时不得不上网查大量的资料,结合书本上写的慢慢的理解，这真是一个漫长的过程，可能有时一天也不能弄懂一个算法的本质.我凭着不放弃的心态，最终还是克服了重重困难,解决了自己从未解决过的难题。这也是自己的一个突破.在系统开发的过程中依然有一些本质性的问提没有解决,我现在没有过多的深究，但我相信我会在以后的学习中一一解决这些难题.例如：求顶点之间的最短路径我一直还不懂求PATH数组.在系统开发的过程中我学到了很多的新的知识,最重要的就是学会了一种思想。模块化思想,以前老师总是提到我们以后写代码不必写那么多,拿来用就行,我一直不懂他的意思，原来是当你的模块被集成之后，以后这些模块就可以不必写了可以直接引用。例如:这次我用到了桟和队列的知识，我以前就写过,如果我要是重新去写又得花一定的时间，这并不是一个好的习惯，我以前写过集成了我拿来用不就行了吗，这样提高了编码的速度提高了效率。不过代码重用的考虑很多的东西,要求比较高。总的来说这次系统开发我学到了很多。

                    本文档为【景区旅游信息管理系统】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

景区旅游信息管理系统

你可能还喜欢