数据结构课外实践报告项目名称景区旅游信息管理系统所在班级：小组成员：指导教师：起止时间：课外实践评定成绩记录指导教师意见系统完成情况：优良中差报告完成情况：优良中差答辩评定成绩团队整体成绩：成员成绩“姓名”“学号”综合成绩项目基本信息项目名称景区旅游信息管理系统项目简介旅游业随着我国经济的增长和人民收入的提高迅速发展，而景区旅游管理问题日益紧迫。
本项目提供基本的有关的管理操作，能够智能化的管理，还能够为导游提供指引，为游客指路，小组成员任务分工：项目基本框架设计、项目工程中“4.cpp”文件“main.cpp”文件和“structure.h”文件、后期的调试工作、PPT制作。
：项目工程中的“3.cpp”文件、课外实践报告。
：项目工程中的“2.cpp”文件。
：项目工程中的“1.cpp”文件。
一、问题描述及分析在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。
为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。
算法采用迪杰斯特拉算法或弗洛伊德算法均可。
建立一个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。
任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。
（1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。
遍历采用深度优先策略，这也比较符合游客心理。
（2）为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。
（3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。
在本线路图中将输出任意景点间的最短路径和最短距离。
（4）在景区建设中，道路建设是其中一个重要内容。
道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。
本任务中假设修建道路的代价只与它的里程相关。
因此归纳起来，本任务有如下功能模块：创建景区景点分布图；输出景区景点分布图（邻接矩阵）输出导游线路图；判断导游线路图有无回路；求两个景点间的最短路径和最短距离；输出道路修建规划图。
主程序用菜单选项供用户选择功能模块。
二、功能模块及结构描述1.结构:*****************图的邻接表存储结构********************* 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********************//*******************图的邻接矩阵存储结构********* 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 struct VexNode{VertexType data;ArcBox *firstin,*firstout;//分别指向该顶点的第一条入弧和出弧}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);//*********************创建有向图的十字链表******************void createOLGraph(OLGraph&ag);//********************创建图的邻接表存储结构*****************void createALGraph(ALGraph&ag);//##################################################### ######//**********************转换成邻接矩阵***********************void transition(ALGraph&ag,MGraph&mg);//*************************输出邻接矩阵**********************void printMGraph(MGraph mg);//************确定该顶点在十字链表结构中顶点向量的位置**********int LocateOLGraphGraph(OLGraph&ag,VertexType d);//**************确定该节点在邻接表结构中顶点向量中的位置********int LocateVexALGraph(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,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);//****************输出最小生产树的各条边*************** void MiniSpanTree_PRIM( ALGraph&G,VertexType u);三、 主要流程描述四、 使用说明程序运行后，进入界面：备注:需按从1 到7的持续执行,因各模块不独立.在如上所示的界面下进行基本的操作。
五、 问题及解决方法输出最小生成树中的边判断图中有无回路 输出由深度优先遍历序列得到的导游线路图. 输出深度优先遍历序列. 创建邻接表. 输出转换后的邻接矩阵. 欢迎进入管理系统,请选择: 退出问题：⑴调试时数据录入问题解决方法:使用文件保存图的信息⑵邻接表转换成矩阵时,那些在邻接表中体现不出的边如何赋值?解决方法:创建邻接矩阵时,全部元素先初始化为0,在邻接表中能体现的边赋值为相应的长度,而其余还为0⑶深度优先遍历时,如何保存遍历路径?解决方法:用全局变量.(4)如何完成从深度优先遍历序列到导游线路的转换?解决方法:开始时按”学生课外实践题目”中提供的算法设计,发现无法解决复杂的情况,”实践题目”中的算法是让p在深度优先遍历序列中回溯,我们用双向链表存储导游线路,并且让p在为完成的导游线路中回溯即可解决,在ppt中有详细解释.(5)在拓扑排序中如何统计各顶点入度?解决方法:用图的十字链表存储结构.(6)在弗洛伊德算法中如何还原路径?解决方法:用二维数组存储路径,使用非递归算法实现还原.六、课外实践总结1、通过课外实践使我们在巩固了原有的理论知识上，又培养了灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，使我们体会到自身知识和能力在实际中的应用和发挥。