景区旅游信息管理系统课外实践报告Word格式.docx
《景区旅游信息管理系统课外实践报告Word格式.docx》由会员分享，可在线阅读，更多相关《景区旅游信息管理系统课外实践报告Word格式.docx（27页珍藏版）》请在冰点文库上搜索。
在本线路图中将输出任意景点间的最短路径和最短距离。
（4）在景区建设中，道路建设是其中一个重要内容。
道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。
本任务中假设修建道路的代价只与它的里程相关。
二、功能模块及结构描述
1.由上述描述归纳起来，本任务有如下功能模块：
创建景区景点分布图，在程序中由CreateGraph（ALGraph&
G）函数实现；
输出景区景点分布图（邻接矩阵），在程序中由OutputGraph（ALGraphG）函数实现；
输出导游线路图，在程序中由CreatTourSortGraph（G,G1）函数实现；
判断导游线路图有无回路，在程序中由TopoSort（G1）函数实现；
求两个景点间的最短路径和最短距离，在程序中由MiniDistanse（G1,path,D）函数实现；
输出道路修建规划图，在程序中由MiniSpanTree（G,G.adjlist[0].name）函数实现。
主程序用菜单选项由ShowMenu（）函数供用户选择功能模块。
2.景点的信息包括景点的名称和近邻景点之间的通路和距离。
用邻接链表存储景点分布图的信息，（带权无向）图的邻接链表。
三、主要流程描述
主程序采用设计主菜单调用若干功能模块，同时在主程序中定义两个邻接链表类型变量G和G1，作为调用子函数的参数。
建图子模块建立无向带权图，输入顶点信息和边的信息，输出邻接链表G。
由于是无向边，输入一条边时构建两条边。
输出图子模块：
从邻接链表g转换成邻接矩阵a，并输出邻接矩阵a。
图中边的权值∞用32767表示。
遍历子模块：
通过遍历图G，只得到遍历的顶点序列。
我们先将顶点序列存在数组vex中，然后再转换成导游线路存入数组vex1中，最后生成导游线路图G1（同样用邻接链表存储，供拓朴排序用）。
将遍历顶点序列转换成导游线路。
遍历结点序列与导游线路图转换的策略：
设遍历结果为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中。
三、使用说明
程序运行后，进入界面（如下图4）：
图4初始界面
在如上所示的界面下进行基本的操作，在程序测试中选用如下（图5）所示的图作为景区景点分布图
图5景点分布
在将以上景点分布输入程序创建景区景点分布图程序实现过程及输出景区景点分布图和导游路线图的程序运行结果如下如图6所示。
图6创建输出景区景点分布图及导游路线图
程序功能4到功能6的测试结果如下图7所示：
图7其它测试结果
四、问题及解决方法
问题1：
在深度遍历景区景点分布图时，由于使用的是邻接表，在递归回溯时，指针P一直向后找当前结点的邻接点直到变为空，但是再次回溯时，P应该是当前结点的头结点的下一个结点开始，但是P却一直为空.
解决方法：
在递归调用深度遍历函数后面，紧接着把头结点再次赋值给P，然后P后移，相当于依然是从第一个结点的下一个邻接点开始。
问题2：
不知该怎样输出导游线路图中的回路。
利用拓扑排序，将拓扑出来的景点存放在一个数组中，最后通过和所有的顶点比较，如果该顶点在该数组中就说明不在环中，如果不在就说明在环中，则输出它。
五、课外实践总结
通过这次课外实践，我们对本学期所学的数据结构课程有关知识进行了巩固，同时也体会到了团队合作的重要性。
从最初的问题的讨论，分工到最后的具体程序实现大家遇到了不少的问题，我们在一起辩论，去图书馆查阅资料，在网上查询资料，大家在一起通力合作解决了遇到的各种问题，最后完成了此次的课外实践。
经过这次的课外实践，我们在对课本所学的知识有了更深的了解的同时，也学会了用所学的知识解决实际的问题，我们小组成员在一起共同学习，共同进步，取得了一定的实践效果。
但是，在此期间也我们也发现了各自的不足。
这激励着大家在以后的学习过程中更加努力，去积极的克服这些问题，提升自己的能力。
六、源代码
//结构的定义以及函数的声明（travels.h）
#ifndefTRAVELS_H_H
#defineTRAVELS_H_H
#include<
string>
iostream>
usingnamespacestd;
#defineINFINITY32767
#defineMAX_VERTEX_NUM20
externdouble**a;
//定义存储原图顶点矩阵的全局数组
typedefstructArcNode
{
intadjvex;
structArcNode*nextarc;
doublew;
}ArcNode;
//定义顶点信息
typedefstructVNode
stringname;
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
//定义边信息
typedefstruct
AdjListadjlist;
intvexnum,arcnum;
}ALGraph;
//定义邻接表
typedefstructedge
stringvex;
intlowcost;
}Edge[MAX_VERTEX_NUM];
//定义辅助数组
voidShowMenu（）;
//显示菜单
boolIsZeroOrOne（intn）;
intLocateVex（ALGraphG,stringv）;
//寻找要查找顶点位置
voidCreatGraph（ALGraph&
G）;
//创建图的邻接表存储
voidOutputGraph（ALGraphG）;
//输出图的邻接表
intMininum（ALGraphG,Edgea）;
//寻找还没有纳入最小生成树中的边的最小值
voidMiniSpanTree（ALGraphG,stringu）;
//求最小生成树
voidDFS（ALGraphG,intv）;
//递归遍历
voidDFSTraverse（ALGraphG）;
//图的深度遍历
boolIsEdge（ALGraphG,stringv1,stringv2）;
//判断要查的这两个顶点之间是否有直接相连的边
voidCreatTourSortGraph（ALGraphG,ALGraph&
G1）;
//创建导游线路图
intTopoSort（ALGraphG1）;
//拓扑排序
voidFindInDegree（ALGraphG1,intindegree[]）;
//计算每个顶点的入度，存储在indegree数组中
voidShortestPath（ALGraphG,intpath[][MAX_VERTEX_NUM],doubleD[][MAX_VERTEX_NUM]）;
//计算最短路径
voidOutPutShortestPath（ALGraphG,intpath[][MAX_VERTEX_NUM],doubleD[][MAX_VERTEX_NUM],inti,intj）;
//求最短路径
voidMiniDistanse（ALGraphG,intpath[][MAX_VERTEX_NUM],doubleD[][MAX_VERTEX_NUM]）;
//输出最短路径
boolIsOperate（intn）;
//判断是否为操作数
#endif
//功能函数的实现（Test.cpp）
#include"
travels.h"
voidShowMenu（）
cout<
<
"
"
;
====================="
endl;
欢迎使用景区旅游信息管理系统"
cout<
**请选择菜单**"
0、退出系统。
1、创建景区景点分布图。
2、输出景区景点分布图。
3、输出导游线路图。
4、输出导游线路图中的回路。
5、求两个景点间的最短路径和最短距离。
6、输出道路修建规划图。
}
boolIsOperate（intn）
if（n==0||n==1||n==2||n==3||n==4||n==5||n==6）//如果不是操作数就返回真，否则假
returntrue;
returnfalse;
boolIsZeroOrOne（intn）
if（n==0||n==1）
intLocateVex（ALGraphG,stringv）
for（inti=0;
i<
G.vexnum;
i++）
if（v==G.adjlist[i].name）//判断要查找的顶点是否存在
returni;
//返回找到的顶点位置
return0;
G）
请输入顶点数和边数：
cin>
>
G.vexnum>
G.arcnum;
endl<
\"
请输入各顶点的信息\"
请输入各顶点的名字：
inti=0,j;
for（;
i++）//对图的顶点进行初始化
{
cin>
G.adjlist[i].name;
G.adjlist[i].firstarc=NULL;
}
intw;
stringv1,v2;
for（intk=0;
k<
k++）
cout<
请输入第"
k+1<
条边的两个顶点以及该边的权值：
v1>
v2>
w;
i=LocateVex（G,v1）;
j=LocateVex（G,v2）;
ArcNode*P=newArcNode;
ArcNode*Q=newArcNode;
P->
adjvex=j;
w=w;
nextarc=G.adjlist[i].firstarc;
G.adjlist[i].firstarc=P;
//插入点P
Q->
adjvex=i;
nextarc=G.adjlist[j].firstarc;
G.adjlist[j].firstarc=Q;
//插入点Q
double**a;
voidOutputGraph（ALGraphG）
inti,j;
a=newdouble*[G.vexnum];
for（i=0;
a[i]=newdouble[G.vexnum];
//对邻接矩阵数组分配空间
for（j=0;
j<
j++）
if（i==j）
a[i][j]=0;
else
a[i][j]=INFINITY;
ArcNode*P=newArcNode;
for（P=G.adjlist[i].firstarc;
P;
P=P->
nextarc）
{
j=P->
adjvex;
a[i][j]=P->
}
\t"
G.adjlist[i].name<
cout<
a[i][j]<
delete[]P;
intk=0;
boolvisited[MAX_VERTEX_NUM];
//判断顶点是否被遍历过
stringvex[MAX_VERTEX_NUM];
//存储遍历的顶点序列
ArcNode*p=newArcNode;
voidDFS（ALGraphG,intv）
visited[v]=true;
vex[k++]=G.adjlist[v].name;
for（p=G.adjlist[v].firstarc;
p;
p=p->
if（!
visited[p->
adjvex]）
DFS（G,p->
adjvex）;
p=G.adjlist[v].firstarc;
voidDFSTraverse（ALGraphG）
intv;
for（v=0;
v<
v++）
visited[v]=false;
//初始化遍历顶点为没有被访问
visited[v]）//如果没有被访问就对其进行深度优先遍历
DFS（G,v）;
boolIsEdge（ALGraphG,stringv1,stringv2）//判断两个顶点之间是否有边
inti=LocateVex（G,v1）;
intj=LocateVex（G,v2）;
if（a[i][j]<
INFINITY）//如果这两个顶点之间有边就返回为真，否则返回假
stringvex1[2*MAX_VERTEX_NUM];
//存储导游线路图的顶点遍历序列
G1）
DFSTraverse（G）;
inti,j,n=0;
boolIs;
for（i=0;
G.vexnum-1;
k=0;
Is=true;
while（Is）
vex1[n++]=vex[i+k];
if（IsEdge（G,vex[i+k],vex[i+1]））//如果他们之间有边就直接连接上这条边
Is=false;
k--;
//如果没有就回溯，直到找到和vex[i+1]有边的
vex1[n]=vex[i];
//将最后一个顶点放进vex数组中
=n;
visited[i]=false;
i++）//初始化导游图
G1.adjlist[i].name=G.adjlist[i].name;
G1.adjlist[i].firstarc=NULL;
intarcnum=0;
//记录导游线路图中的边的个数
for（k=0;
n;
k++）
{
i=LocateVex（G,vex1[k]）;
j=LocateVex（G,vex1[k+1]）;
if（visited[j]）//如果该点已经在导游线路图中，就寻找它是否与已经在导游线路图中的点形成回路
intm=k+2;
//跳过他的直接前驱
if（m<
=n）//判断是否超出存储导游线路图的数组
{
while（visited[LocateVex（G,vex1[m]）]）//直到出现新的节点为止
{
/*判断这两个点在原来的景区分布图中是否有边，如果有就连接上这条边，否者继续向后找*/
if（IsEdge（G,vex1[k],vex1[m]））
{
j=LocateVex（G,vex1[m]）;
ArcNode*P=newArcNode;
ArcNode*Q=newArcNode;
P->
w=a[i][j];
Q=G1.adjlist[i].firstarc;
G1.adjlist[i].firstarc=P;
nextarc=Q;
arcnum++;
}
if（++m>
=n）//如果在查找的过程中到了数组末尾就强行退出
break;
}
}
else//如果没有在导游线路图中就连接上它
visited[i]=visited[j]=true;
ArcNode*P=newArcNode;
ArcNode*Q=newArcNode;
P->
Q=G1.adjlist[i].firstarc;
G1.adjlist[i].firstarc=P;
arcnum++;
G1.vexnum=G.vexnum;
//赋值导游线路图中顶点的个数
G1.arcnum=arcnum;
//赋值导游线路图中边的个数
导游路线为：
vex1[i];
//输出导游线路图
intTopoSort（ALGraphG1）
string*a=newstring[G1.vexnum];
//将不在回路中的顶点暂存在字符数组a中
int*indegree=newint[G1.vexnum];
//为顶点入度数组开辟空间
inttop=0,base=0;
int*S=newint[G1.vexnum];
//为顶点栈开辟空间
inti=0;
G1.vexnum;
i++）//初始化顶点入读数组
indegree[i]=0;
FindInDegree（G1,indegree）;
//调用求入度函数求出各个顶点的入度
indegree[i]）//将入度减为0的顶点入栈
S[top++]=i;
intcount=0;
//记录已经进入拓扑序列的顶点的个数
intk;
ArcNode*p=newArcNode;
while（top!
=base）//当栈不空是继续循环
k=S[--top];
a[count++]=G1.adjlist[k].name;
for（p=G1.adjlist[k].firstarc;
if（!
（--indegree[p->
adjvex]））//如果入度减为0，则入栈
S[top++]=p->
if（count<
G1.vexnum）
图中有回路,回路为：
for（i=0;
for（k=0;
count;
if（G1.adjlist[i].name==a[k]）//如果顶点与数组a中的顶点相同就跳出循环，说明不在循环中
break;
if（k>
=count）
cout<
G1.adjlist[i].name;
returnfalse;
else
图中没有回路"
delete[]a;
delete[]indegree;
delete[]S;
voidFindInDegree（ALGraphG1,intindegree[]）//求各
升级会员 