景区旅游信息管理系统.docx

《景区旅游信息管理系统.docx》由会员分享，可在线阅读，更多相关《景区旅游信息管理系统.docx（29页珍藏版）》请在三一办公上搜索。

1、景区旅游信息管理系统数据结构课外实践报告 项 目 名 称 景区旅游信息管理系统 所 在 班 级： 小 组 成 员： 指 导 教 师： 起 止 时 间： 安阳师范学院 数据结构课外实践 课外实践评定成绩记录 系统完成情况：优 良 中 差 指导教师意见 报告完成情况：优 良 中 差 团队整体成绩： “姓名” “学号” 成答辩评定成绩 员成绩 综 合 成 绩 - 2 - 安阳师范学院 数据结构课外实践 项目基本信息 项目名称 景区旅游信息管理系统 旅游业随着我国经济的增长和人民收入的提高迅速发展，而景区旅游管理问题日益紧迫。本项目提项目简介 供基本的有关的管理操作，能够智能化的管理，还能够为导游提供

2、指引，为游客指路， 小组成员 ：项目基本框架设计、项目工程中“4.cpp”文件“main.cpp”文件和“structure.h”文件 、后期的调试工作、PPT制作。 任务分工 ：项目工程中的“3.cpp”文件、课外实践报告。 ：项目工程中的“2.cpp”文件。 ：项目工程中的“1.cpp”文件。 一、 问题描述及分析 在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理

3、系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。 任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。 景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略，这也比较符合游客心理。 为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。 在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。 在景区建设中，道路建设

4、是其中一个重要内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。 - 3 - 安阳师范学院 数据结构课外实践 因此归纳起来，本任务有如下功能模块： 创建景区景点分布图； 输出景区景点分布图 输出导游线路图； 判断导游线路图有无回路； 求两个景点间的最短路径和最短距离； 输出道路修建规划图。 主程序用菜单选项供用户选择功能模块。 二、 功能模块及结构描述 1.结构: *图的邻接表存储结构* typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置; int weight;

5、/弧长度 struct ArcNode*nextarc; /指向下一条弧的指针; ArcNode; typedef struct VNode VertexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode,*AdjList; typedef struct AdjList vertices; int vexnum,arcnum; /图的当前顶点数和弧数; ALGraph; /*end* /*图的邻接矩阵存储结构* typedef char VertexType; typedef struct VertexType*vexs; /顶

6、点向量; int*arcs; /邻接矩阵/存储对应的长度 int vexnum,arcnum; /图的当前顶点数和弧数; MGraph; /*end* - 4 - 安阳师范学院 数据结构课外实践 /*十字链表存储结构* typedef struct ArcBox int tailvex,headvex; /该弧的尾和头顶点的位置 int weight; /该弧的长度; struct ArcBox *hlink,*tlink; /分别为弧头相同和弧尾相同的弧的链域 ArcBox; typedef struct VexNode VertexType data; ArcBox *firstin,*f

7、irstout;/分别指向该顶点的第一条入弧和出弧 VexNode; typedef struct VexNode *xlist; /表头向量 int vexnum,arcnum; /当前顶点数和边数; OLGraph;/ /*end* /*求导游线路所用的结构(双向链表)* struct guideNode int adj; guideNode*next;/指向节点后继 guideNode*prior;/指向节点前驱 ; 2.功能模块: /*求导游线路图* void guideGraph(ALGraph&G,OLGraph&OG,guideNode*&H); /*创建有向图的十字链表* vo

8、id createOLGraph(OLGraph&ag); /*创建图的邻接表存储结构* void createALGraph(ALGraph&ag); /# - 5 - 安阳师范学院 数据结构课外实践 /*转换成邻接矩阵* void transition(ALGraph&ag,MGraph&mg); /*输出邻接矩阵* void printMGraph(MGraph mg); /*确定该顶点在十字链表结构中顶点向量的位置* int LocateOLGraphGraph(OLGraph&ag,VertexType d); /*确定该节点在邻接表结构中顶点向量中的位置* int LocateVe

9、xALGraph(ALGraph&ag,VertexType d); /*确定该节点在邻接矩阵结构中顶点向量中的位置* int LocateVexMGraph(MGraph&mg,VertexType d); /# /*深度优先遍历* void DFSTraverse(const ALGraph&G); /*从第v个顶点出发递归地深度优先遍历图G* void DFS(const ALGraph&G,int v); /*拓扑排序* int TopologicalSort(const OLGraph&G); /*Floyd算法* void ShortestPath_FLOYD(ALGraph&G,

10、int *&path,int *&d); /*还原最短路径(非递归算法)* void explainPath(int*path,int i,int j,int *S,int &top);/从i到j的路径 /*输出路径及长度* void printPath(ALGraph&G,int *path,int *d); /*最小生成树(普利姆算法)* /辅助结构 typedef struct VertexType adjvex; int lowcost; Closedeg,*CLOSEDEG; /*求出下一条最短的边* int minimum(CLOSEDEG closedeg); - 6 - 安阳师

11、范学院 数据结构课外实践 /*输出最小生产树的各条边* void MiniSpanTree_PRIM( ALGraph&G,VertexType u); 三、 主要流程描述 欢迎进入管理系 统,请选择: 创建邻输出深度判断图中输出由深输出转换 接表. 有无回路 优先遍历度优先遍后的邻接 序列. 历序列得 到的导游矩阵. 线路图. 四、 使用说明 程序运行后，进入界面： 备注:需按从1 到7的持续执行,因各模块不独立. 输出最小生成树中的边 退出 在如上所示的界面下进行基本的操作。 五、 问题及解决方法 - 7 - 安阳师范学院 数据结构课外实践 问题：调试时数据录入问题 解决方法:使用文件保存

12、图的信息 邻接表转换成矩阵时,那些在邻接表中体现不出的边如何赋值? 解决方法:创建邻接矩阵时,全部元素先初始化为0,在邻接表中能体现的 边赋值为相应的长度,而其余还为0 深度优先遍历时,如何保存遍历路径? 解决方法:用全局变量. (4)如何完成从深度优先遍历序列到导游线路的转换? 解决方法:开始时按”学生课外实践题目”中提供的算法设计,发现无法解决复杂的情况,”实践题目”中的算法是让p在深度优先遍历序列中回溯,我们用双向链表存储导游线路,并且让p在为完成的导游线路中回溯即可解决,在ppt中有详细解释. (5)在拓扑排序中如何统计各顶点入度? 解决方法:用图的十字链表存储结构. (6)在弗洛伊德

13、算法中如何还原路径? 解决方法:用二维数组存储路径,使用非递归算法实现还原. 六、课外实践总结 1、通过课外实践使我们在巩固了原有的理论知识上，又培养了灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，使我们体会到自身知识和能力在实际中的应用和发挥。其次，它激发了我们创新意识，开发创造的能力和培养沟通能力。 2、这次课外实践设计让我们受益匪浅。我们不仅学到了很多知识和技能，更重要的是我们学会了如何运用所学知识去解决实际问题。在完成实践报告的过程中，遇到一些困难，但经过共同努力，仔细研读教材和相关资料，最终解决.既学到知识，我们也体会到了团队合作的重要性，锻炼了团队协作的意识，以及不

14、怕困难，不惧失败的精神。 3、通过这次课外实践，我们深刻的认识到了自己在学习方面的不足之处，但我们也认识到，要学好一门学科，没有刻苦钻研的精神是不行的，只有在不断的尝试中，经历失败，从失败中总结经验，然后再不断的尝试，才能获得成功。 七、源代码 “structure.h”文件： #ifndef structre_h_h #define structre_h_h #include #include using namespace std; typedef char VertexType; #define MAX 10000 - 8 - 安阳师范学院 数据结构课外实践 / /*图的邻接表存储结构*

15、 typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置; int weight;/弧长度 struct ArcNode*nextarc; /指向下一条弧的指针; ArcNode; typedef struct VNode VertexType data; ArcNode *firstarc; /顶点信息 /指向第一条依附该顶点的弧的指针 VNode,*AdjList; typedef struct AdjList vertices; int vexnum,arcnum; /图的当前顶点数和弧数; ALGraph; /*end* /# / /*图的邻接矩阵

16、存储结构* typedef char VertexType; typedef struct VertexType*vexs; /顶点向量; int*arcs; /邻接矩阵/存储对应的长度 int vexnum,arcnum; /图的当前顶点数和弧数; MGraph; /*end* /# / /*十字链表存储结构* typedef struct ArcBox int tailvex,headvex; /该弧的尾和头顶点的位置 int weight; /该弧的长度; struct ArcBox *hlink,*tlink; /分别为弧头相同和弧尾相同的弧的链域 ArcBox; typedef st

17、ruct VexNode - 9 - 安阳师范学院 数据结构课外实践 VertexType data; ArcBox *firstin,*firstout;/分别指向该顶点的第一条入弧和出弧 VexNode; typedef struct VexNode *xlist; /表头向量 int vexnum,arcnum; /当前顶点数和边数; OLGraph;/ /*end* /# / /*求导游线路所用的结构(双向链表)* struct guideNode int adj; guideNode*next;/指向节点后继 guideNode*prior;/指向节点前驱 ; /*end* /# /

18、*求导游线路图* void guideGraph(ALGraph&G,OLGraph&OG,guideNode*&H); / /*创建有向图的十字链表* void createOLGraph(OLGraph&ag); /*创建图的邻接表存储结构* void createALGraph(ALGraph&ag); /# /*转换成邻接矩阵* void transition(ALGraph&ag,MGraph&mg); /*输出邻接矩阵* void printMGraph(MGraph mg); / /*确定该顶点在十字链表结构中顶点向量的位置* int LocateOLGraphGraph(OLG

19、raph&ag,VertexType d); /*确定该节点在邻接表结构中顶点向量中的位置* int LocateVexALGraph(ALGraph&ag,VertexType d); /*确定该节点在邻接矩阵结构中顶点向量中的位置* int LocateVexMGraph(MGraph&mg,VertexType d); /# - 10 - 安阳师范学院 数据结构课外实践 /*深度优先遍历* void DFSTraverse(const ALGraph&G); /*从第v个顶点出发递归地深度优先遍历图G* void DFS(const ALGraph&G,int v); /*拓扑排序* i

20、nt TopologicalSort(const OLGraph&G); /*Floyd算法* void ShortestPath_FLOYD(ALGraph&G,int *&path,int *&d); /*还原最短路径(非递归算法)* void explainPath(int*path,int i,int j,int *S,int &top);/从i到j的路径 /*输出路径及长度* void printPath(ALGraph&G,int *path,int *d); /*最小生成树(普利姆算法)* /辅助结构 typedef struct VertexType adjvex; int l

21、owcost; Closedeg,*CLOSEDEG; /*求出下一条最短的边* int minimum(CLOSEDEG closedeg); /*输出最小生产树的各条边* void MiniSpanTree_PRIM( ALGraph&G,VertexType u); #endif “ 1.cpp”文件 #includestructure.h /*创建图的邻接表存储结构* void createALGraph(ALGraph&ag) ifstream fin(test.txt,ios:in); if(fin=NULL) cout文件无法打开!vnumanum;/输入顶点数,边数,和是否有信

22、息的判断信息 ag.vexnum=vnum;/ ag.arcnum=anum;/ ag.vertices=new VNodevnum;/开辟空间,存储顶点信息 for(i=0;iag.verticesi.data;/输入顶点信息 VertexType d1,d2; ArcNode *p; int weight; for(i=0;id1d2weight; m=LocateVexALGraph(ag,d1);/确定d1在顶点向量中的位置 n=LocateVexALGraph(ag,d2);/确定d2在顶点向量中的位置 p=new ArcNode;/开辟空间,存储边的信息 p-adjvex=m;/

23、p-weight=weight; /把该边链入邻接表 p-nextarc=ag.verticesn.firstarc; ag.verticesn.firstarc=p; p=new ArcNode; p-adjvex=n; p-weight=weight; /把对应的边链入邻接表 p-nextarc=ag.verticesm.firstarc; ag.verticesm.firstarc=p; cout邻接表:endl; for(i=0;iag.vexnum;i+) coutag.verticesi.datanextarc) coutadjvex.data ;/输出到屏幕以备查看 couten

24、dl; “2.cpp”文件 #includestructure.h /*转换成邻接矩阵* void transition(ALGraph&ag,MGraph&mg) mg.vexnum=ag.vexnum;/顶点数 - 12 - 安阳师范学院 数据结构课外实践 mg.arcnum=ag.arcnum;/边数 mg.vexs=new VertexTypemg.vexnum;/开辟空间,存储顶点信息 for(int i=0;img.vexnum;i+) mg.vexsi=ag.verticesi.data;/复制节点信息 /*开辟空间,存储邻接矩阵* mg.arcs=new int*mg.vexn

25、um; for(i=0;img.vexnum;i+) mg.arcsi=new intmg.vexnum; /*end* ArcNode*p; int j; /*邻接表转化为邻接矩阵* for(i=0;img.vexnum;i+) for(j=0;jnextarc) mg.arcsip-adjvex=p-weight; /*end* /*输出邻接矩阵* void printMGraph(MGraph mg) int i,j; cout*endl; cout邻接矩阵为:endl; for(i=0;img.vexnum;i+) for(j=0;jmg.vexnum;j+) coutmg.arcsi

26、jt; coutendl; - 13 - 安阳师范学院 数据结构课外实践 “3.cpp”文件 #includestructure.h bool *visited;/访问标记数组; int *InDegree;/顶点入度数组; int *guide;/存储深度优先遍历路径 int i=0; /*深度优先遍历* void DFSTraverse(const ALGraph&G) guide=new intG.vexnum; int i; int sum=0; visited=new boolG.vexnum; for(i=0;iG.vexnum;i+) visitedi=false; for(i=

27、0;iG.vexnum;i+) if(!visitedi) sum+;/统计连通分量 DFS(G,i); coutendl连通分量数为:sumendl; deletevisited; /*从第v个顶点出发递归地深度优先遍历图G* void DFS(const ALGraph&G,int v) visitedv=true; coutG.verticesv.datanextarc)/对剩下的图深度优先遍历 if(!visitedp-adjvex) - 14 - 安阳师范学院 数据结构课外实践 DFS(G,p-adjvex); /*求导游线路图* /H为双向循环链表,存储导游线路 void guid

28、eGraph(ALGraph&G,OLGraph&OG,guideNode*&H) H=new guideNode;/建头结点 H-next=H-prior=H;/双向循环链表 /创建十字链表 OG.vexnum=G.vexnum; OG.arcnum=G.arcnum; OG.xlist=new VexNodeG.vexnum; for(int j=0;jadj=guidei+;/初始化,表示第一个顶点已在导游线路中且是第一个顶点 p_o-next=H-next; p_o-prior=H; H-next-prior=p_o; H-next=p_o; guideNode*p_o1; guide

29、Node*p_end=p_o; while(iadj.firstarc; while(p_a)/查找是否有边 if(p_a-adjvex=guidei) break; p_a=p_a-nextarc; - 15 - 安阳师范学院 数据结构课外实践 if(p_a)/若有边 p_o1=new guideNode; p_o1-adj=guidei; i+;/i指向下一个位置 /插入到表尾 p_o1-next=p_end-next; p_o1-prior=p_end; p_end-next-prior=p_o1; p_end-next=p_o1; p_end=p_end-next;/p_end始终指向

30、最后一个元素 p_o=p_end;/p_o指向最后一个元素 else p_o=p_o-prior;/p_o退一个位置 p_o1=new guideNode; p_o1-adj=p_o-adj;/把p_o所指结点插入 p_o1-next=p_end-next; p_o1-prior=p_end; p_end-next-prior=p_o1; p_end-next=p_o1; p_end=p_end-next;/p_end始终指向最后一个元素 p_o=H-next; p_o1=p_o-next;/p_o1指向第一个节点 ArcBox*p_arc; while(p_o1!=H)/创建十字链表结构,以便拓扑排序 p_arc=new ArcBox;/弧结点 p_arc-tailvex=p_o-adj;/弧尾位置 p_arc-headvex=p_o1-adj; p_arc-tlink=OG.xlistp_o-adj.firstout;/顶点结点的弧尾链域地址赋值给相对应的弧的tlink链域 p_arc-hlink=OG.xlistp_o1-adj.firstin; OG.xlistp_o-adj.firstout=p_arc; OG.xlistp_o1-adj.firstin=p_arc; p_o=p_o1; p_o1=p_o1