景区旅游信息标准管理系统.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;iArcNum;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;iVexNum;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;
whileStackLen(&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);

//判断与否是拓扑排序
ifCountVexNum)
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] 值等于边所带权 ；若 不是图 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;jVexNumj++)
{
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]st[j]=pGraph->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数组.
在系统开发过程中我学到了诸多新知识,最重要就是学会了一种思想.模块化思想,此前教师总是提到咱们后来写代码不必写那么多,拿来用就行,我始终不懂她意思,本来是当你模块被集成之后,后来这些模块就可以不必写了可以直接引用.例如:这次我用到了桟和队列知识,我此前就写过,如果我要是重新去写又得花一定期间,这并不是一种好习惯,我此前写过集成了我拿来用不就行了吗,这样提高了编码速度提高了效率.但是代码重用考虑诸多东西,规定比较高.
总来说这次系统开发我学到了诸多.