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

校园旅游信息管理系统
1.1项目需求分析
在旅游景区，常常会碰到游客探询从一个景点到另一个景点最短路径和最短距离，这类游客不喜爱根据导游图线路来游览，而是挑选自己感爱好景点游览。为于帮助这类游客信息查询，就需要计算出全部景点之间最短路径和最短距离。算法采取迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现关键功效包含制订旅游景点导游线路策略和制订景区道路铺设策略。
任务中景点分布是一个无向带权连通图，图中边权值是景点之间距离。
1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先经过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。遍历采取深度优先策略，这也比较符合游客心理。
　 （2）为了使导游线路图能够优化，可经过拓朴排序判定图中有没有回路，若有回路，则打印输出回路中景点，供人工优化。
　 （3）在导游线路图中，还为部分不愿按线路走游客提供信息服务，比如从一个景点到另一个景点最短路径和最短距离。在本线路图中将输出任意景点间最短路径和最短距离。
　 （4）在景区建设中，道路建设是其中一个关键内容。道路建设首先要确保能连通全部景点，但又要花最小代价，能够经过求最小生成树来处理这个问题。本任务中假设修建道路代价只和它里程相关。
所以归纳起来，本任务有以下功效模块：
　　创建景区景点分布图；
　　输出景区景点分布图（邻接矩阵）
　　输出导游线路图；
　　判定导游线路图有没有回路；
　　求两个景点间最短路径和最短距离；
　　输出道路修建计划图。
　　主程序用菜单选项供用户选择功效模块。
1.2项目设计步骤
1.2.1项目总体框架
校园旅游信息管理系统

创
建
景
区
景
点
分
布
图
输
出
景
区
景
点
分
布
图
输
出
景
区
导
游
线
路
图
导
游
线
路
图
有
无
回
路
两
个
景
点
间

最
短
路
径
输
出
道
路
修
建
规
划
图

1.2.2项目数据结构
#ifndef SUCCESS //标志位成功
#define SUCCESS 1
#endif

#ifndef FAILURE //标志位失败
#define FAILURE 0
#endif

#ifndef INF //标志位无穷
#define INF 0x3f3fffff
#endif

#ifndef MAXNUM
#define MAXNUM 20
#endif

typedef bool STATUS; //定义函数状态数据类型

typedef char VERTEXTYPE[MAXNUM][11]; //定义顶点向量数据类型

typedef int ADJMATRIX[MAXNUM][MAXNUM]; //定义邻接矩阵数据类型

typedef struct GRAPH //定义图数据类型
{
VERTEXTYPE Vexs; //图顶点向量
ADJMATRIX Arcs; //图邻接矩阵
int VexNum; //图目前顶点
int ArcNum; //图目前弧
}*PGRAPH; //定义图指针数据类型

typedef struct CLOSEDGE //定义辅助数组数据类型
{
VERTEXTYPE Vexs; //图顶点向量
int Lowcost[MAXNUM]; //
}*PCLOSEDGE; //定义辅助数组指针数据类型
1.2.3项目模块设计
创建景区景点分布图
一. 邻接矩阵 (Adjacency Matrix)(二维数组表示法）
在图邻接矩阵表示中，有一个统计各个顶点信息顶点表，还有一个表示各个顶点之间关系邻接矩阵。
设图 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占用存放空间只和它顶点数相关，和边数无关；适适用于边稠密图；
步骤图：

程序：
//创建景区景点分布图
STATUS CreateGraph(PGRAPH pGraph)
{
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();
return FAILURE;
}
//初始化图弧数
printf("\t\t\t请输入图弧度数(<=20)：");
scanf("%d",&pGraph->ArcNum);
//检验
if(pGraph>ArcNum>20)
{
printf("\t\t\t警告：输入数据错误！！！\n");
printf("\t\t\t按任意键回主菜单！！！");
getch();
return FAILURE;
}

//初始化图顶点名称
printf("\t\t\t---------------------------------\n");
printf("\t\t\t初始化顶点名称......\n");
for(int i=0;iVexNum;i++)
{
printf("\t\t\t请输入第%d个顶点名称：",i+1);
scanf("%s",pGraph->Vexs[i]);
}

//初始化图弧权值为最大值
for(i=0;iVexNum;i++)
for(int j=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;i>ArcNum;i++)
{
int Stav,Endv,Weight;
printf("\t\t\t请输入第%d条弧(格式：Vi Vj Weight)：",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();
return SUCCESS;
}
输出景区景点分布图
步骤图：

程序：
//输出景区景点分布图
STATUS PrintGraph(const PGRAPH pGraph)
{
printf("\t\t\t_________________________________\n");
printf("\n\t\t\t$\t显示景区景点分布图\t$\n");
printf("\t\t\t_________________________________\n\n");

//
printf("\t景区景点名称......\n\t");
for(int i=0;i>VexNum;i++)
printf("%s\t",pGraph->Vexs[i]);

printf("\n\n\t景区景点信息......\n");
for(i=0;iVexNum;i++)
{
printf("\t___________________________________________________________\n\t");

for(int j=0;jVexNum;j++)
if(pGraph->Arcs[i][j]==INF)
printf("∞\t");

else
printf("%d\t",pGraph->Arcs[i][j]);
printf("\n");
}

printf("\t___________________________________________________________\n\t");
printf("按任意键回主菜单！！！");
getch();
return SUCCESS;
}
输出景区导游线路图
图遍历
从图中某一顶点出发访遍图中全部顶点，且使每个顶点仅被访问一次，这一过程就叫做图遍历 (Traversing Graph)。
图中可能存在回路，且图任一顶点全部可能和其它顶点相通，在访问完某个顶点以后可能会沿着一些边又回到了曾经访问过顶点。
为了避免反复访问，可设置一个标志顶点是否被访问过辅助数组 visited [ ]。
辅助数组 visited [ ] 初始状态为 0, 在图遍历过程中, 一旦某一个顶点 i 被访问, 就立即让 visited [i] 为 1, 预防它被数次访问。
两种图遍历方法:
深度优先搜索
DFS (Depth First Search)
广度优先搜索
BFS (Breadth First Search)
广度优先搜索遍历图(BFS)
对连通图，从起始点V到其它各顶点肯定存在路径。
其中，V->w1, V->w2, V->w8 路径长度为1;
V->w7, V->w3, V->w5 路径长度为2;
V->w6, V->w4 路径长度为3

从图中某个顶点V0出发，并在访问此顶点以后依次访问V0全部未被访问过邻接点，以后按这些顶点被访问前后次序依次访问它们邻接点，直至图中全部和V0有路径相通顶点全部被访问到。
若此时图中还有顶点未被访问,则另选图中一个未曾被访问顶点作起始点，反复上述过程，直至图中全部顶点全部被访问到为止。
步骤图：
程序：
//输出景区导游线路图(注：广度优先遍历)
STATUS TraverseGraph(const PGRAPH pGraph)
{
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));
//初始化访问标志数组为false
for(int i=0;iVexNum;i++)
Visit[i]=false;

//定义队列、并初始化队列
QUEUE Queue;
if(InitQueue(&Queue,pGraph->VexNum)==FAILURE)
{
printf("\t\t\t警告：创建队列失败！！！\n");
printf("\t\t\t按任意键回主菜单！！！");
getch();
return FAILURE;
}

//定义访问顶点变量，并初始值为0
int Vertex=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();
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 D

B

c
D
A

比如, 对学生选课工程图进行拓扑排序, 得到拓扑有序序列为
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("\t\t\t_________________________________\n");

printf("\n\t\t\t$\t导游线路图有没有回路\t$\n");
printf("\t\t\t_________________________________\n\n");

//定义入度数组,统计每个顶点入度，初始化为0
int Indegree[MAXNUM]={0};
//定义桟、并初始化桟
STACK Stack;
if(InitStack(&Stack,pGraph->VexNum)==FAILURE)
{
printf("\t\t\t警告：创建桟失败！！！\n");
printf("\t\t\t按任意键回主菜单！！！");
getch();
return FAILURE;
}

printf("\t\t\t计算各顶点入度.....\n");
for(int j=0;jVexNum;j++)
{
//求各个顶点入度
for(int i=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顶点个数
int Count=0,k;
while(StackLen(&Stack))
{
//出桟、并访问
PopStack(&Stack,&k);
printf("%s\t",pGraph->Vexs[k]);
Count++;
//对出栈顶点所指向顶点减一 ，而且将入度为0顶点入栈
for(int i=0;iVexNum;i++)
if(pGraph->Arcs[k][i]!=INF)
if(!(--Indegree[i]))
PushStack(&Stack,i);
}
//销毁桟
DestroyStack(&Stack);

//判定是否是拓扑排序
if(CountVexNum)
printf("\t\t\t结果：导游线路图有回路\n");
else
printf("\t\t\t结果：导游线路图无回路\n");

printf("\t\t\t按任意键回主菜单！！！");
getch();
return SUCCESS;
}
求两个景点间最短路径
最短路径定义
　　所谓最短路径问题是指：假如从图中某一顶点（源点）抵达另一顶点（终点）路径可能不止一条，怎样找到一条路径似沿此路径上各边权值总和（称为路径长度）达成最小。
迪杰斯特拉(Dijkstra)算法求单源最短路径
由Dijkstra提出一个按路径长度递增序产生各顶点最短路径算法。
（1）按路径长度递增序产生各顶点最短路径
若按长度递增次序生成从源点s到其它顶点最短路径，则目前正在生成最短路径上除终点以外，其它顶点最短路径均已生成（将源点最短路径看作是已生成源点到其本身长度为0路径）。
（2）具体做法
　　一开始第一组只包含顶点 v 1 ，第二组包含其它全部顶点， v 1 对应距离值为 0 ，第二组顶点对应距离值是这么确定：若图中有边 , 则 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 中边，则 cost[i][j] 值等于边所带权 ; 若 i , v 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 作为其前一个顶点序号。
步骤图:

程序:
//求两个景点间最短路径
STATUS MinShortPath(const PGRAPH pGraph)
{
printf("\t\t\t_________________________________\n");
printf("\n\t\t\t$\t景点之间最短路径\t$\n");
printf("\t\t\t_________________________________\n\n");

//定义路径矩阵、距离矩阵
ADJMATRIX PathMatrix,DisMatrix;
//定义辅助变量
int i,j,k;
//初始化路径矩阵、距离矩阵
for(i=0;iVexNum;i++)
for(j=0;jVexNum;j++)
{
DisMatrix[i][j]=pGraph->Arcs[i][j];
PathMatrix[i][j]=-1;
}
//求PathMatrix矩阵
for(k=0;kVexNum;k++)
for(i=0;iVexNum;i++)
for(j=0;jVexNum;j++)
if(DisMatrix[i][j]>DisMatrix[i][k]+DisMatrix[k][j])
{
DisMatrix[i][j]=DisMatrix[i][k]+DisMatrix[k][j];
PathMatrix[i][j]=k;
}

//定义起点、终点
int Stav=-1,Endv=-1;
//定义起点、终点名称
char StaNam[MAXNUM],EndNam[MAXNUM];

printf("\t\t\t输入起始点和终点名称(格式：Sta End)：");
scanf("%s%s",StaNam,EndNam);

for(i=0;iVexNum;i++)
{
if(!strcmp(pGraph->Vexs[i],StaNam))
//起始点名称下标
Stav=i;
if(!strcmp(pGraph->Vexs[i],EndNam))
//终点名称下标
Endv=i;
}
//判定起始点名称和终点名称是否存在
if(Stav==-1||Endv==-1)
return FAILURE;

//定义桟、并初始化
STACK Stack;
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();
return SUCCESS;
}
输出道路修建计划图
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来描述所得到最小生成树。
比如:
步骤图:

程序:
//输出道路修建计划图(注：最小生成树)
STATUS MininumCST(const PGRAPH pGraph)
{
printf("\t\t\t_________________________________\n");
printf("\n\t\t\t$\t输出道路修建计划图\t$\n");
printf("\t\t\t_________________________________\n\n");

//定义辅助数组变量
CLOSEDGE Closedge;
int Min=0;
//初始化辅助数组,从第一个顶点开始
for(int i=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;i++)
{
//保留辅助数组中Closedge.Lowcost权值最小值
//查找第一个权值不是0位置
for(int j=0;jVexNum;j++)
if(Closedge.Lowcost[j]!=0)
break;
Min=j;
//查找辅助数组中最小值
for(j=0;jVexNum;j++)
if(Closedge.Lowcost[j]&&Closedge.Lowcost[j]%s\n",Closedge.Vexs[Min],pGraph->Vexs[Min]);
//
Closedge.Lowcost[Min]=0;
//选择最小边
for(j=0;jVexNum;j++)
if(pGraph->Arcs[Min][j]Arcs[Min][j];
strcpy(Closedge.Vexs[j],pGraph->Vexs[Min]);
}
}

printf("\n\t\t\t按任意键回主菜单！！！");
getch();
return SUCCESS;
}
1.3项目编码实现
#include
#include
#include "Graph.h"
int Frame()
{
printf("\t\t\t_________________________________\n");
printf("\n\t\t\t$\t景区旅游信息管理系统\t$\n");
printf("\t\t\t_________________________________\n\n");

printf("\t\t\t1.创建景区景点分布图\n\n");
printf("\t\t\t2.保留景区景点分布图\n\n");
printf("\t\t\t3.读取景区景点分布图\n\n");
printf("\t\t\t4.输出景区景点分布图\n\n");
printf("\t\t\t5.输出景区导游线路图\n\n");
printf("\t\t\t6.导游线路图有没有回路\n\n");
printf("\t\t\t7.景点之间最短路径\n\n");
printf("\t\t\t8.输出道路修建计划图\n\n");
printf("\t\t\t9.退出信息管理系统\n\n");
printf("\t\t\t请选择对应功效：");
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数组.
在系统开发过程中我学到了很多新知识,最关键就是学会了一个思想.模块化思想,以前老师总是提到我们以后写代码无须写那么多,拿来用就行,我一直不懂她意思,原来是当你模块被集成以后,以后这些模块就能够无须写了能够直接引用.比如:这次我用到了桟和队列知识,我以前就写过,假如我要是重新去写又得花一定时间,这并不是一个好习惯,我以前写过集成了我拿来用不就行了吗,这么提升了编码速度提升了效率.不过代码重用考虑很多东西,要求比较高.
总来说这次系统开发我学到了很多.