景区旅游管理系统.doc

景区旅游信息管理系统
1.1.1 项目需求
在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。
任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。
　 （1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略，这也比较符合游客心理。
　 （2）为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。
　 （3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。
　 （4）在景区建设中，道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。
因此归纳起来，本任务有如下功能模块：
　　创建景区景点分布图；
　　输出景区景点分布图（邻接矩阵）
　　输出导游线路图；
　　判断导游线路图有无回路；
　　求两个景点间的最短路径和最短距离；
　　输出道路修建规划图。
　　主程序用菜单选项供用户选择功能模块。 　
1.1.2 设计流程
主程序采用设计主菜单调用若干功能模块，同时在主程序中定义两个邻接链表类型变量G和G1，作为调用子函数的参数。

建图子模块建立无向带权图，输入顶点信息和边的信息，输出邻接链表G。由于是无向边，输入一条边时构建两条边。　　

输出图子模块：从邻接链表g转换成邻接矩阵a，并输出邻接矩阵a。图中边的权值∞用32767表示。

遍历子模块：通过遍历图G，只得到遍历的顶点序列。我们先将顶点序列存在数组vex中，然后再转换成导游线路存入数组vex1中，最后生成导游线路图G1（同样用邻接链表存储，供拓朴排序用）。将遍历顶点序列转换成导游线路。

图10-43（a）（b）（c）三个无向图的深度优先搜索遍历的结果均为v1→v2→v3→v4。但它们的导游线路图却不同。图（a）的导游线路图为v1→v2→v3→v4，与遍历结果相同。
　　图（b）的导游线路图为v1→v2→v3→v2→v4，图（c）的导游线路图为v1→v2→v3→v2→v1→v4。
　　遍历结点序列与导游线路图转换的策略：
　　设遍历结果为v1→v2→…→vi→vi+1→…→vn
　　对于结点vi和vi+1，如果vi和vi+1存在边，则直接转换。
　　否则，加入边vi→vi-1，如果vi-1和vi+1存在边，则加入边vi-1→vi+1。
　　再否则，加入边vi-1→vi-2，如果vi-2和vi+1存在边，则加入边vi-2→vi+1。
　　如果vi-2和vi+1还不存在边，继续回溯，一定能找到某个整数k（因为景点分布图是连通图），使得vi-k和vi+1存在边，则加入边vi-k→vi+1。
　　在本任务中，转换后的线路图存于数组vex1中。
流程图见10-29。
拓朴排序子模块流程图，见图10-39源程序，参见10.7 节的samp10-8.c。
求最短路径子模块流程图：见10-34。源程序，参见10.6 节的samp10-6.c。
求最小生成树子模块流程图：见19-33。源程序，参见10.6 节的samp10-5.c。
1.1.3 数据结构
景点的信息包括景点的名称和近邻景点之间的通路和距离。用邻接链表存储景点分布图的信息。
（带权无向）图的邻接链表
　　/***************************************************************/
/*程序功能：建立一个旅游景区管理系统，实现旅游路线选择 　　 　*/
　　/*景区道路优化等功能　　　　　　　　　　　　　　　　　　　 */
　　/***************************************************************/
　　#include“stdio.h”
　　#include“stdlib.h”
　　#include “string.h”
　　#define MAX_EDGE_NUM100/*定义图的最大边数*/
　　#define MAX_VERTEX_NUM 20
　　#define MAXNUM 32767
　　typedef char Vertex_type[10];
　　typedef struct node/*边表结点*/
　　{
　　　　int adjvex;/*邻接点域*/
　　　　int weight;
　　　　struct node* next;/*指向下一个邻接点的指针域*/
　　}Edge_node;
　　typedef struct /*顶点表结点*/
　　{
　　　　Vertex_type vertex;/*顶点域，存放景点名称*/
　　　　Edge_node* firstedge;/*边表头指针*/
　　}Vertex_node;
　　typedef struct
　　{
　　　　Vertex_node adjlist[MAX_VERTEX_NUM];/*邻接表*/
　　　　int n,m;/*顶点数和边数*/
　　}Lgraph;
边的类型定义
在求最小生成树时，用到边的定义。
　　typedef struct
　　{
　　　　inti; /*顶点vi的序号*/
　　　　int j; /*顶点vi的序号*/
　　　　intweight;
　　} Edge_type;
1.1.4 程序清单
主程序源程序
/*************************************************************/
　　/*函 数 名：main　　　　　　　　　　　　　　　　　　　　　　 */
　　/*入口参数：无　　　　　　　　　　　　　　　　　　　　　　　 */
　　/*返 回 值：无　　　　　　　　　　　　　　　　　　　　　　　 */
　　/*************************************************************/
　　voidmain()
　　{
　　　　Lgraph *g, *g1;
　　　　int sele;
　　　　void create_graph();
　　　　void output_graph();
　　　　void dfs_main();
　　　　void topo_sort_main();

　　　　void min_distance_main();
　　　　void min_tree();
　　　　g=(Lgraph *)malloc(sizeof(Lgraph));
　　　　g->m=0;
　　　　g1=(Lgraph *)malloc(sizeof(Lgraph));
　　　　while(1)
　　　　{
　　　　　　system("cls");
　　　　　　printf(“\n\n******景区旅游管理信息系统******\n”);
　　　　　　printf(“1.输入景点分布图\n”);
　　　　　　printf(“2.输出景点分布图邻接矩阵\n);
　　　　　　printf(“3.生成导游线路图\n”);
　　　　　　printf(“4.输出导游线路图中回路\n”);
　　　　　　printf(“5.求两景点间最短路径和最短距离\n”);
　　　　　　printf(“6.输出景区道路修建规划图\n”);
　　　　　　printf(“0.退出\n”);
　　　　　　printf(“请选择功能序号:”);
　　　　　　scanf(“%d”,&sele);
　　　　　　printf("\n\n***************************************************\n\n");
　　　　　　switch(sele)
　　　　　　{
　　　　　　　　case 1: create_graph(g); break;
　　　　　　　　case 2: output_graph(g);break;
　　　　　　　　case 3: dfs_main(g,g1);break;
　　　　　　　　case 4: topo_sort_main(g1);break;
　　　　　　　　case 5: min_distance_main(g);break;
　　　　　　　　case 6: min_tree(g); break;
　　　　　　　　case 0: exit(0);
　　　　　　}
　　　　　　getchar();
　　　　　　printf("按回车键继续......");
　　　　　　getchar();
　　　　}
　　}

建图子模块源程序参见10.3 节的create_graph()函数。

输出图子模块
/**************************************************************/
　　/*函 数 名：output_graph 　　　　　　　　　　　　　　　　　　 */
　　/*函数功能：输出图G的邻接矩阵　　　　　　　　　　　　　　　　 */
　　/*入口参数：g --- 邻接链表　　　　　　　　　　　　　　　　　　*/
　　/*返 回 值：无　　　　　　　　　　　　　　　　　　　　　　　　*/
　　/**************************************************************/
　　void output_graph(Lgraph *g)
　　{
　　　　int i,j,n;
　　　　inta[MAX_VERTEX_NUM][ MAX_VERTEX_NUM];
　　　　Edge_node *p;
　　　　if(g->n==0)
　　　　{
　　　　　　printf(“景点分布图未输入，无法输出！\n”);
　　　　　　return;
　　　　}
　　　　for(i=0;in;i++)
　　　　　　for(j=0;jn;j++)
　　　　　　　　if (i==j)
　　　　　　　　　　a[i][j]=0;
　　　　　　　　else
　　　　　　　　　　a[i][j]=MAXNUM;
　　　　for (i=0;i< g->n;i++)
　　　　{
　　　　　　p=g->adjlist[i].firstedge;
　　　　　　while (p!=NULL)
　　　　　　{
　　　　　　　　j=p->adjvex;
　　　　　　　　a[i][j]=p->weight;
　　　　　　　　p=p->next;
　　　　　　}
　　　　}
　　　　printf("景点分布图邻接矩阵为:\n\n");
　　　　printf("%8s "," ");
　　　　for (i=0;in;i++)
　　　　　　printf("%8s ",g->adjlist[i].vertex);
　　　　for (i=0;in;i++)
　　　　　　{printf("%8s ",g->adjlist[i].vertex);
　　　　　　for(j=0;jn;j++)
　　　　　　　　printf("%9d",a[i][j]);
　　　　　　　　printf(“\n”);
　　　　}
　　}

遍历子模块
/**************************************************************/
　　/*函 数 名：dfs_main　　　　　　　　　　　　　　　　　　　　　*/
　　/*函数功能：生成导游线路图　　　　　　　　　　　　　　　　　　*/
　　/*入口参数：g-- 景点分布图　　　　　　　　　　　　　　　　　　*/
　　/*g1 — 导游线路图　　　　　　　　　　　　　　　　　　　　　　*/
　　/*返 回 值：无　　　　　　　　　　　　　　　　　　　　　　　　*/
　　/**************************************************************/
　　voiddfs_main(Lgraph *g,Lgraph *g1)
　　{
　　　　int visited[MAX_VERTEX_NUM];
　　　　int x,i;
　　　　int vex[MAX_VERTEX_NUM];
　　　　int j, k, i1, tag;
　　　　int vex1[MAX_VERTEX_NUM];
　　　　Edge_node *p, *q;
　　　　for (i=0;i< MAX_VERTEX_NUM;i++)
　　　　　　visited[i]=0;
　　　　　　if(g->n==0)
　　　　　　{
　　　　　　　　printf(“景点分布图未输入，无法生成导游线图！\n”);
　　　　　　　　return;
　　　　　　}
　　　　　　do
　　　　　　{
　　　　　　　　printf("请输入口景点序号：");
　　　　　　　　scanf("%d",&x);
　　　　　　　　if (x>=1&&x<=g->n)
　　　　　　　　{
　　　　　　　　　　x--;
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　　　printf("景点号输入有误，请重新输入！\n");
　　　　　　}while(1);
　　　　　　j=0;
　　　　　　dfs(g,x,visited,vex,&j);//每次调用时，j初始化为0
　　　　　　/*构建游览线路，存放在数组Vex1*/
　　　　　　i1=0;
　　　　for(i=0;i< g->n-1;i++)
　　　　{
　　　　　　j=vex[i+1];
　　　　　　tag=1;
　　　　　　k=0;
　　　　　　while (tag)
　　　　　　{
　　　　　　　　vex1[i1++] = vex[i+k];
　　　　　　　　p=g->adjlist[vex[i+k] ].firstedge;
　　　　　　　　while (p!=NULL && p->adjvex!=j)/*判断vi+k与vj之间有没有边*/
　　　　　　　　p=p->next;
　　　　　　　　if (p==NULL)
　　　　　　　　　　k--;/*若vi+k与vj之间没有边回溯*/
　　　　　　　　else
　　　　　　　　　　tag=0;
　　　　　　}
　　　　}
　　　　vex1[i1++]=j;
　　　　/*建立游览线路图的邻接链表G1，供拓朴排序用*/
　　　　for (i=0in;i++)
　　　　{
　　　　　　strcpy( g1->adjlist[i].vertex, g->adjlist[i].vertex );
　　　　　　g1->adjlist[i].firstedge=NULL;
　　　　}
　　　　for (k=0;kadjvex=j;
　　　　　　p-> weight=1; /*建立游览线路图时不考虑边的权值*/
　　　　　　q=g1->adjlist[i].firstedge;
　　　　　　g1->adjlist[i].firstedge=p;
　　　　　　p->next=q;
　　　　}
　　　　g1->n=g->n;
　　　　g1->m=i1-1;
　　　　/*输出游览线路*/
　　　　printf(“游览线路为\n：”);
　　　　for (k=0;k”,g->adjlist[i].vertex);
　　　　}
　　　　printf(“%s\ng->adjlist[vex1[i1-1] ].vertex);
　　}
　　/**************************************************************/
　　/*函 数 名：dfs 　　　　　　　　　　　　　　　　　　　　　　　*/
　　/*函数功能：以Vi为出发点对邻接表存储的图G进行DFS搜索　　　　　*/
　　/*入口参数：g-- 图G的邻接表存储　　　　　　　　　　　　　　　 */
　　/*i— 顶点Vi　　　　　　　　　　　　　　　　　　　　　　　　　*/
　　/*visited— 标志顶点是否已被访问的数组　　　　　　　　　　　　*/
　　/*vex— 存放遍历时所经过的顶点　　　　　　　　　　　　　　　　*/
　　/*j— 存放位置　　　　　　　　　　　　　　　　　　　　　　　　*/
　　/*返 回 值：无　　　　　　　　　　　　　　　　　　　　　　　　*/
　　/**************************************************************/
　　voiddfs(Lgraph *g,int i, int visited[], int vex[] .int *j)
　　{
　　　　int k;
　　　　static j=0;
　　　　Edge_node *p;
　　　　printf("visit vertex:V%s\n",g->adjlist[i].vertex);/*访问顶点Vi*/
　　　　vex[*j]=i; /*遍历结点vi，存入数组Vex中*/
　　　　*j=*j+1;
　　　　visited[i]=1;/*标记Vi已访问*/
　　　　p=g->adjlist[i].firstedge;/*取Vi边表的头指针*/
　　　　while (p) /*依次搜索Vi的邻接点Vj，j=p->adjva*/
　　　　{
　　　　　　k= p->adjvex;
　　　　　　if (!visited[k])/*若Vj尚未访问，则以Vj为出发点向纵深搜索*/
　　　　　　　　dfs(g,k, visited, vex,j);
　　　　　　　　p=p->next;/*找Vi的下一个邻接点*/
　　　　}
　　}

在本任务中，通过10.4节的遍历输出景区旅游导游线路，该线路从入口出发，经过所有旅游景点后到达出口。
　　 在输出的导游线图中，有可能出现回路，即一个景点经过两次及两次以上。为了实现导游线路图的优化，首先要判断图中有没有回路，若有，回路由哪几个景点组成。然后尽可能消除回路。比如说可以通过景区之间多修建道路来消除回路。当然，如果确实存在困难，不能彻底消除回路，也最好使回路经过的景点最少。
　　 其中，判断导游线路图有无回路，可用拓朴排序来解决，若有回路则输出回路中的景点。要实现这一功能，可直接使用上述程序，存在回路时，输出未能拓朴排序的顶点。
main()
　　{
　　　　Lgraph *g;
　　　　int vex[MAX_VERTEX_NUM], a[MAX_VERTEX_NUM][ MAX_VERTEX_NUM],
　　　　　　vexno[MAX_VERTEX_NUM];
　　　　int i,j,n,k;
　　　　Edge_node *p;
　　　　for (i=0;i< MAX_VERTEX_NUM;i++)
　　　　　　vex[i]=-1;
　　　　g=(Lgraph *)malloc(sizeof(Lgraph));
　　　　create_graph1(g);/*建立有向图*/
　　　　n=g->n;
　　　　for(i=0; iadjlist[i].firstedge;
　　　　　　while(p!=NULL)
　　　　　　{
　　　　　　　　j=p->adjvex;
　　　　　　　　a[i][j]=p->weight;
　　　　　　　　p=p->next;
　　　　　　}
　　　　}
　　　　for (i=0;iadjlist[vex[i]].vertex);
　　　　　　}
　　　　}
　　　　else
　　　　printf(“该图没有回路”);
　　}
1.1.5 运行测试