景区旅游管理系统Word下载.docx
《景区旅游管理系统Word下载.docx》由会员分享，可在线阅读，更多相关《景区旅游管理系统Word下载.docx（17页珍藏版）》请在冰点文库上搜索。
图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”
#defineMAX_EDGE_NUM100/*定义图的最大边数*/
#defineMAX_VERTEX_NUM20
#defineMAXNUM32767
typedefcharVertex_type[10];
typedefstructnode/*边表结点*/
{
intadjvex;
/*邻接点域*/
intweight;
structnode*next;
/*指向下一个邻接点的指针域*/
}Edge_node;
typedefstruct/*顶点表结点*/
Vertex_typevertex;
/*顶点域，存放景点名称*/
Edge_node*firstedge;
/*边表头指针*/
}Vertex_node;
typedefstruct
Vertex_nodeadjlist[MAX_VERTEX_NUM];
/*邻接表*/
intn,m;
/*顶点数和边数*/
}Lgraph;
边的类型定义
在求最小生成树时，用到边的定义。
inti;
/*顶点vi的序号*/
intj;
/*顶点vi的序号*/
intweight;
}Edge_type;
1.1.4程序清单
主程序源程序
/*************************************************************/
/*函数名：
main */
/*入口参数：
无 */
/*返回值：
/*************************************************************/
voidmain（）
Lgraph*g,*g1;
intsele;
voidcreate_graph（）;
voidoutput_graph（）;
voiddfs_main（）;
voidtopo_sort_main（）;
voidmin_distance_main（）;
voidmin_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）
{
case1:
create_graph（g）;
break;
case2:
output_graph（g）;
break;
case3:
dfs_main（g,g1）;
case4:
topo_sort_main（g1）;
case5:
min_distance_main（g）;
case6:
min_tree（g）;
case0:
exit（0）;
}
getchar（）;
按回车键继续......"
}
}
建图子模块源程序参见10.3节的create_graph（）函数。
输出图子模块
/**************************************************************/
output_graph */
/*函数功能：
输出图G的邻接矩阵 */
g---邻接链表 */
无 */
/**************************************************************/
voidoutput_graph（Lgraph*g）
inti,j,n;
inta[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
Edge_node*p;
if（g->
n==0）
printf（“景点分布图未输入，无法输出！
\n”）;
return;
}
for（i=0;
i<
g->
n;
i++）
for（j=0;
j<
j++）
if（i==j）
a[i][j]=0;
else
a[i][j]=MAXNUM;
for（i=0;
g->
p=g->
adjlist[i].firstedge;
while（p!
=NULL）
j=p->
adjvex;
a[i][j]=p->
weight;
p=p->
next;
}
printf（"
景点分布图邻接矩阵为:
\n\n"
%8s"
"
"
g->
adjlist[i].vertex）;
{printf（"
printf（"
%9d"
a[i][j]）;
printf（“\n”）;
遍历子模块
dfs_main */
生成导游线路图 */
g--景点分布图 */
/*g1—导游线路图 */
voiddfs_main（Lgraph*g,Lgraph*g1）
intvisited[MAX_VERTEX_NUM];
intx,i;
intvex[MAX_VERTEX_NUM];
intj,k,i1,tag;
intvex1[MAX_VERTEX_NUM];
Edge_node*p,*q;
MAX_VERTEX_NUM;
visited[i]=0;
if（g->
printf（“景点分布图未输入，无法生成导游线图！
return;
do
请输入口景点序号：
"
scanf（"
%d"
&
x）;
if（x>
=1&
&
x<
=g->
n）
{
x--;
break;
}
printf（"
景点号输入有误，请重新输入！
\n"
}while
（1）;
j=0;
dfs（g,x,visited,vex,&
j）;
//每次调用时，j初始化为0
/*构建游览线路，存放在数组Vex1*/
i1=0;
n-1;
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之间有没有边*/
if（p==NULL）
k--;
/*若vi+k与vj之间没有边回溯*/
tag=0;
vex1[i1++]=j;
/*建立游览线路图的邻接链表G1，供拓朴排序用*/
i++）
strcpy（g1->
adjlist[i].vertex,g->
adjlist[i].vertex）;
g1->
adjlist[i].firstedge=NULL;
for（k=0;
k<
i1-1;
k++）
i=vex1[k];
j=vex1[k+1];
p=（Edge_node*）malloc（sizeof（Edge_node））;
p->
adjvex=j;
weight=1;
/*建立游览线路图时，不考虑边的权值*/
q=g1->
adjlist[i].firstedge=p;
next=q;
g1->
n=g->
m=i1-1;
/*输出游览线路*/
printf（“游览线路为\n：
printf（“%s->
”,g->
printf（“%s\n”,g->
adjlist[vex1[i1-1]].vertex）;
dfs */
以Vi为出发点对邻接表存储的图G进行DFS搜索 */
g--图G的邻接表存储 */
/*i—顶点Vi */
/*visited—标志顶点是否已被访问的数组 */
/*vex—存放遍历时所经过的顶点 */
/*j—存放位置 */
voiddfs（Lgraph*g,inti,intvisited[],intvex[].int*j）
intk;
staticj=0;
visitvertex:
V%s\n"
/*访问顶点Vi*/
vex[*j]=i;
/*遍历结点vi，存入数组Vex中*/
*j=*j+1;
visited[i]=1;
/*标记Vi已访问*/
p=g->
/*取Vi边表的头指针*/
while（p）/*依次搜索Vi的邻接点Vj，j=p->
adjva*/
{
k=p->
if（!
visited[k]）/*若Vj尚未访问，则以Vj为出发点向纵深搜索*/
dfs（g,k,visited,vex,j）;
/*找Vi的下一个邻接点*/
}
在本任务中，通过10.4节的遍历输出景区旅游导游线路，该线路从入口出发，经过所有旅游景点后到达出口。
在输出的导游线图中，有可能出现回路，即一个景点经过两次及两次以上。
为了实现导游线路图的优化，首先要判断图中有没有回路，若有，回路由哪几个景点组成。
然后尽可能消除回路。
比如说可以通过景区之间多修建道路来消除回路。
当然，如果确实存在困难，不能彻底消除回路，也最好使回路经过的景点最少。
其中，判断导游线路图有无回路，可用拓朴排序来解决，若有回路则输出回路中的景点。
要实现这一功能，可直接使用上述程序，存在回路时，输出未能拓朴排序的顶点。
main（）
Lgraph*g;
intvex[MAX_VERTEX_NUM],a[MAX_VERTEX_NUM][MAX_VERTEX_NUM],
vexno[MAX_VERTEX_NUM];
inti,j,n,k;
vex[i]=-1;
create_graph1（g）;
/*建立有向图*/
n=g->
i<
a[i][j]=0;
while（p!
vexno[i]=i;
k=topo_sort（a,vex,vexno,n）;
if（k==0）
printf（“该图有回路，回路中的景点为：
for（i=0;
tag=1;
for（j=0;
vex[j]!
=-1&
tag;
if（i==vex[j]）
tag=0;
if（tag==1）
printf（“%s”,g->
adjlist[vex[i]].vertex）;
else
printf（“该图没有回路”）;
1.1.5运行测试
升级会员 