数据结构课程设计报告----景区旅游信息管理系统.doc-资料库

weixin_44170305-12267083-16359648024131511036.doc.pdf-第1页.png

第1页 / 共45页

weixin_44170305-12267083-16359648024131511036.doc.pdf-第2页.png

第2页 / 共45页

weixin_44170305-12267083-16359648024131511036.doc.pdf-第3页.png

第3页 / 共45页

weixin_44170305-12267083-16359648024131511036.doc.pdf-第4页.png

第4页 / 共45页

weixin_44170305-12267083-16359648024131511036.doc.pdf-第5页.png

第5页 / 共45页

weixin_44170305-12267083-16359648024131511036.doc.pdf-第6页.png

第6页 / 共45页

weixin_44170305-12267083-16359648024131511036.doc.pdf-第7页.png

第7页 / 共45页

weixin_44170305-12267083-16359648024131511036.doc.pdf-第8页.png

第8页 / 共45页

数据结构课程设计报告题目景区旅游信息管理系统院系计算机与控制工程学院专业计算机科学与技术班级姓名学号指导教师 2019 年 12 月 18 日

目录 1 项目描述................................................................................................................................ 1 2 数据及其逻辑结构分析 ........................................................................................................ 1 3 数据的存储结构设计 ............................................................................................................ 4 4 项目主要算法 ........................................................................................................................ 5 5 项目的程序实现 .................................................................................................................... 7 6 项目实现结果 ........................................................................................................................ 9 7 课程设计总结 ...................................................................................................................... 14 附录：源程序 .......................................................................................................................... 14

1 项目描述在旅游景区，经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离，这类游客不喜欢按照导游图的线路来游览，而是挑选自己感兴趣的景点游览。为于帮助这类游客信息查询，就需要计算出所有景点之间最短路径和最短距离。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统，实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。任务中景点分布是一个无向带权连通图，图中边的权值是景点之间的距离。（1）景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。遍历采用深度优先策略，这也比较符合游客心理。（2）为了使导游线路图能够优化，可通过拓朴排序判断图中有无回路，若有回路，则打印输出回路中的景点，供人工优化。（3）在导游线路图中，还为一些不愿按线路走的游客提供信息服务，比如从一个景点到另一个景点的最短路径和最短距离。在本线路图中将输出任意景点间的最短路径和最短距离。（4）在景区建设中，道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点，但又要花最小的代价，可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。本工程旨在完成上述所说的各种功能。 2 数据及其逻辑结构分析 ATD Complex{ 数据对象： D1={ PlaceName[MAX]，number}//一个 Node 由一个字符数组 PlaceName 和一个整数 number 组成 D2={mp[MAX][MAX] ，nn，ee}//一个 MatGraph 由一个整数二维数组 mp 和两个整数 nn，ee 组成 D3={key，infor，*lchild，*rchild}//一个 BSTNode 由一个整数 key 和一个 Node 数据类型 infor 和两个指针域 lchild，rchild 组成 1

D4={adjvex，weight，*nextarc}//一个 ArcNode 由两个整数 adjvex，weigh 和一个指针域 nextarc 组成} D5={*fitstarc ， ct} 一个 VNode 由一个 ArcNode 指针域和一个整数 ct 组成 D6={adjlist[MAX]，n，e}一个 AdjGraph 由一个 VNode 类型一维数组 adjlist 和两个整数 n，e 组成数据关系： R1={ ( ，number ) | PlaceName[i]是 Node 中景点的名字，number 是 Node 中景点的编号} R2={ ( ，nn，ee) | mp[i][j]是 MatGraph 中存储各景点信息的二维数组，nn 是顶点个数，ee 是边数} R3={ (key，infor，*lchild，*rchild) | key 是 BSTNode 中的关键字，infor 是 BSTNode 中的景点信息，lchild 是 BSTNode 中左指针域，rchild 是 BSTNode 中右指针域} R4={ (adjvex，weight，*nextarc) | adjvex 是 ArcNode 中结点编号，weight 是 ArcNode 中结点权重，nextare 是 ArcNode 中下一个结点域} R5={ (*fitstarc，ct) |firstare 是 VNode 中的头节点，ct 是 VNode 中的入度} R6={ (，n，e) | adjlist[i]是 AdjGraph 中的存储结点信息的一维数组，n 是顶点个数，e 是边数} 基本运算： Read(Node Place[],int n,int e): 读取 Place[]中存储的景区信息。 CreadMat(MatGraph &Map, int n, int e): 传入邻接矩阵的顶点 n 和边 e 的信息，创建景区的邻接矩阵，。 InOrder(BSTNode *bt): 线索二叉树中序输出，在 bt 不为空的情况下以递归形式输出。 outputmap(MatGraph Map,int n): 输出景区地图，邻接矩阵形式输出，该邻接矩阵应为对称矩阵。 CreatMatGragh(MatGraph &Map, int n, int e): 创建导游有向图,传入有向图的顶点数和边数。 MAtToList(MatGraph g, AdjGraph *&G): 将邻接矩阵 g 转换成邻接表 G。 DispAdj(AdjGraph *G): 输出邻接表 G,查看某个景点能直接到达的景点。 2

DFS(AdjGraph *G, int v): 从导游入口即开始顶点深度优先搜素导游线路图的邻接表的形式。 dfspath(AdjGraph *G,int u,int v,int path[],int d): 输出导游路线回路，这里的 u，v 是同一个顶点，即导游的入口顶点，d 是回路的个数，途经路径存储在 path 数组中。 Findpath(AdjGraph *G,int k)：从邻接表 G 中查找从 k 出发的所有回路，调用 dfspath 输出所有回路。 TopSort(AdjGraph *G): 拓扑排序判断导游路线有无回路。若有回路，则调用 Findpath 函数查找回路。 ppath(int path[],int i,int v): 输出从 i 到 u 的最短路径。 DisPath(int dist[],int path[],int s[],int n,int v,int u): 判断 v 和 u 之间是否存在最短路，若存在，输出最短路径长度，由 path 存储最短路径，调用 ppath 函数输出最短路径。 Dijkstra(MatGraph g,int v,int u): 狄克斯特拉算法从顶点 v 到其余各顶点的最短路径，调用 DisPath 处理最短路径。 InsertBST(BSTNode *&bt, Node k): 排序二叉树插入结点 k，递归结构实现，通过关键字确定插入的位置。 *CreatBST(Node Place[], int n): 创建二叉排序树，调用了 InsertBST 函数，通过结点的插入来实现建树，共 n 个结点。 *SearchBST(BSTNode *bt, int k): 在二叉搜素树中查找编号为 k 的节点，采用递归结构。 Prim(MatGraph Map,int v,BSTNode *bt): prime 算法在邻接矩阵 MatGraph 中查找最小生成树，v 为查找起点。 Pageinfor():显示界面主菜单，无返回值 } 由上面的数据及其逻辑结构的分析我们可以将词工程图形化，转变成我们可以解决的图论问题，下图是建图模型： 3

3 数据的存储结构设计归纳起来，本任务有如下功能模块：（1）创建景区景点分布图；（2）输出景区景点分布图（邻接矩阵）；本工程采用邻接矩阵存储景点分布，及各景点之间的连通程度，景点即为图中的顶点，路径即为图中边。用邻接矩阵存储，一是因为题目中要求，二是邻接矩阵可以直接看出两个景点之间是否存在路径，而且增加删除边也比较容易。它的存储与边数无关，适用于边稠密的图。（3）输出导游线路图；（4）判断导游线路图有无回路；建立导游图和判断导游路线图是否存在回路的时候是把邻接矩阵的转换成邻接表了，因为在深搜导游线路图和拓扑排序的过程中，邻接表的时间复杂度会比较优，邻接矩阵的时间复杂度会比较慢。这样一个转换就使结构在时间上相对优化多了。同时使用 path[]iwei 数组存储路径。（5）求两个景点间的最短路径和最短距离；在使用 Dijkstra 算法求最短路时，遍历的时图的邻接矩阵存储结构，因为在建图的时候就采用邻接矩阵建的图，加上存储的边数比较多，所以用邻接矩阵来进行最短路的搜索还是比较合理的。（6）输出道路修建规划图。 4

这一步就是查找图中的最小生成树，使用二叉排序树的这一结构，可以将图中点的信息保留并且输出来。在找最小生成树的过程中同样还是使用邻接矩阵完成搜索。（7）主程序用菜单选项供用户选择功能模块。这一模块就是在显示屏上直接打印界面就行。 4 项目主要算法（1） MAtToList 将邻接矩阵转化为邻接表的算法：在图的邻接矩阵 g 中查找值部位 0 和∞的元素，若找到这样的元素，表示存在一条边，创建一个 adjvex 域为 j 的边结点，采用头插法将它插到第 i 个单链表中。算法中由两个循环，所以时间复杂度是 O（n^2）。（2） DFS 和 dfspath 一个是深度优先遍历，一个是深度优先搜索查找输出路径，它们的时间复杂度都是 O（n+e），下面是 DFS（G，1）的执行过程： 5

（3） TopSort 算法的方法思想比较简单，有如下步骤： ①从有向图中选择一个入度为 0 的顶点并输出它 ②从图中删除该顶点，并且删除从该顶点出发的所有有向边 ③重复上述两步，直到不存在入度为 0 的顶点使用邻接表实现时间复杂度为 O（n*e）。（4）Dijkstra 算法求解单元最短路的基本思想是：设 G=(V,E)是一个带权有向图，把图中的顶点集合 V 分成两组。第一组为已求出最短路径的顶点集合，用 S 表示，初始时 S 中只有一个源点，以后每求得一条最短路径 v 到 u，就将顶点 u 加入到集合 S 中，直到全部顶点都加入到 S 中；第二组为其余未确定最短路的顶点集合，用 U 表示，按最短路径长度的递增次序依次把第二组的顶点加入 S 中。时间复杂度采用邻接矩阵实现为 O（n^2）。其中路径比较的过程可参照下图理解： 6

资料库

数据结构课程设计报告----景区旅游信息管理系统.doc

相关推荐

课程资源

热门标签

最新资料