1、 数学与计算机学院 课程设计说明书 课 程 名 称: : 数据结构与算法课程设计数据结构与算法课程设计 课 程 代 码: 题 目: 图的遍历和生成树求解实现图的遍历和生成树求解实现 目 录 摘摘 要要 3 3 引引 言言 4 4 1 1 需求分析需求分析 5 5 1.1 任务与分析 . 5 1.2 测试数据 5 2 2 概要设计概要设计 5 5 2.1 ADT 描述 5 2.2 程序模块结构 . 7 软件结构设计： 7 2.3 各功能模块 7 3 3 详细设计详细设计 8 8 3.1 结构体定义 19 3.2 初始化 22 3.3 插入操作（四号黑体）22 4 4 调试分析调试分析 2222
2、5 5 用户使用说明用户使用说明 2323 6 6 测试结果测试结果 2424 结结 论论 2 26 6 摘摘 要要 数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨 论其在计算机中的存储表示， 以及在其上进行各种运算时的实现算法， 并对算法的效率进行 简单的分析和讨论。进行数据结构课程设计要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发， 培养软件工作
3、者所应具备的科学 的工作方法和作风。 这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识， 结合起来 才完成了这个程序。 因为图是一种较线形表和树更为复杂的数据结构。 在线形表中， 数据元素之间仅有线性 关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可 以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接 表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和 十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍 历。 关键词：关键词：计算机；图；算法。 引 言 很多
4、涉及图的操作的算法都是以图的遍历操作为基础， 通过遍历的演示， 方便在学习中 更好的理解突地遍历的过程。 通过对图的深度优先遍历和广度优先遍历的演示，分别两种遍历的不同与其优缺点。 我们在对一些问题进行求解时， 会发现有些问题很难找到规律， 或者根本无规律可寻。 对于这样的问题，可以利用计算机运算速度快的特点，先搜索查找所有可能出现的情况，再 根据题目条件从所有可能的情况中，删除那些不符合条件的解。 在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为 按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度 越小的结点越先得到扩展， 也就是说先产
5、生的结点先得以扩展处理， 这种搜索算法称为广度 优先搜索法。很多问题都可以用广度优先搜索进行处理、如翻币问题、最短路径问题等。 在计算机中，有多种方法存储图的信息，由于图的结构复杂，使用广泛，一般应根据 实际的应用， 选择适合的表示方法。 常用的图的存储结构有邻接矩阵、 邻接多重表和邻接表。 在实际问题当中，经常遇到这类问题，为新建的某个机构进行选址、道路交通路线、如何走 完所有路线、旅游线路等一系列问题都涉及到图的知识。图是一种复杂的非线性数据结构， 一个图 G（Grah）由两个集合 V 和 E 构成。图存在两种遍历方式：深度优先遍历和广度优先 遍历。广度优先遍历基本思路是假设从图中某顶点
6、U 出发，在访问了顶点 U 之后依次访问 U 的各个未访问的领接点， 然后分别从这些领接点出发依次访问他们的领接点， 并使先访问的 顶点的领接点先于后访问的顶点被访问。 直至所有领接点被访问到。 深度优先的基本思路是 从某个顶点出发访问此顶点， 然后依次从 V 的未被访问的领接点出发深度优先检索图。 直至 图中所有顶点都被访问到。PRIM 算法KRUSKAL 算法，可以对图形进行最小生成树的求解。 树型结构是一种非线性结构，它用于描述数据元素之间层次关系，如人类社会的族谱等，树 型结构的应用非常广泛，磁盘文件目录结构就是一个典型的例子。 1 1 需求分析需求分析 1.11.1 任务与分析任务与分析 问题描述：问题描述： 图的遍历和生成树求解实现图的遍历和生成树求解实现 图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅 有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中， 数据元素之间有着明显的层次关系， 并且
