1、 数 据 结 构 课 程 设 计 设计题目： 无向图的操作 学生姓名： 专业班级： 指导教师： 完成时间： 课题名称 无向图的操作 院 系 年级专业 学 号 姓 名 成 绩 课题设计 目的与 设计意义 1、课题设计目的：一、熟悉图的两种常用的存储结构，邻接矩阵。 二、建立有向图，用邻接表存储结构存储。 三、在邻接表存储结构上实现深度优先遍历。 2、课题设计意义：一、能够熟悉关于无向图邻接矩阵和无向图邻接 表的输出建立等操作。 二、能够理解关于无向图的基本操作有何目的与 意义。 三、将以上的理解加以运用与操作。 指导教师： 年 月 日 目目 录录 第一章第一章 课程设计的目的与意义课程设计的目的
2、与意义 . 1 第二章第二章 课程设计的内容与要求课程设计的内容与要求 . 1 2.1 课程设计的内容 1 2.1.1 定义. 1 2.1.2 操作. 2 2.2 课程设计的要求 2 第三章第三章 需求分析需求分析 . 2 3.1 原理 2 3.2 要求 3 3.3 系统总框架 3 3.4 运行环境 3 3.5 程序的输入（包含输入的数据格式和说明） 3 3.6 开发工具 4 第四章第四章 算法与描述算法与描述 . 4 4.1 图的深度优先遍历 4 4.2 具体过程应为 4 第五章第五章 源程序源程序 5 第六章第六章 运行结果运行结果 . 12 第七章第七章 结束语结束语 16 第八章第八章
3、 参考文献参考文献 . 17 1 第一章第一章 课程设计的目的与意义课程设计的目的与意义 图是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、计算机科 学等领域中，图结构有着广泛的应用。 在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结 点只有一个直接前趋和直接后继。 在树形结构中， 结点之间的关系实质上是层次关系， 除根结点之外，每个结点都只能有一个双亲（前趋） ，但每个结点可以有零个或多个 孩子（后继） 。因此，层次关系是非线性的。但是，它在树的结点之间建立了一个层 次结构；同层次上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只 能和上一层的一个
4、结点（即双亲）相关（根节点除外） 。然而在土结构中，对结点（图 中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图 中任意两个结点之间都可能相关。 邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法，类似于 树的孩子链表表示法。由于它只考虑非零元素,因而节省了零元素所占的存储空间。它 对于无向图和有向图都适用。 本学期我们学了很多图的存储结构，有邻接矩阵。邻接表等。其中邻接矩阵和邻 接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是吧图的边信息与链式 存数相结合的存储方法。 从空间性能上说， 图越洗漱邻接表的空间效率也相应的越高。 从
5、时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要第。 本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现 深度优先和广度优先遍历以及其链表结构的输出。 通过实习巩固并提高我的 C 语言知 识，并初步了解 Visual C+的知识，提高编程能力与专业水平。 第二章第二章 课程设计的内容与要求课程设计的内容与要求 2.1 课程设计的内容 2.1.1 定义 有向图与无向图：图是一种复杂的非线性结构。图 G 由两个集合 V 和 E 组成，记为 G=（V，E） ，其中 V 是顶点的有穷非空集合，E 是 V 中顶点偶对 （称为边）的有穷集。通常，也将图 G 的顶点集和边集分别记为
6、 V （G）和 E（G） 。E（G）可以是空集，若 E（G）为空，则图 G 只 有顶点而没有边。若图 G 中的每条边都是有方向的，则称 G 为有 向图；若图 G 中的每条边都是没有方向的，则称 G 为无向图。 邻接矩阵：邻接矩阵是表示定点之间相邻关系的矩阵。 2 邻接表：对于图 G 中的每个顶点 vi，该方法把所有邻接于 vi的顶点 vj 链成一个单链 变，这个单链表就成为顶点 vi的邻接表。 2.1.2 操作 熟悉掌握关于无向图邻接表和邻接矩阵的运用以及操作，包括： 无向图邻接矩阵的建立、 无向图邻接矩阵的输出、 无向图邻接表的建立、 无向图邻接表的输出、 无向图邻接表的深度遍历、 无向图邻接矩阵的深度遍历、 无向图邻接表的广度遍历、 无向图邻接矩阵的广度遍历。 2.2 课程设计的要求 一、能够熟悉关于无向图邻接矩阵和无向图邻接表的输出建立等操作。 二、能够理解关于无向图的基本操作有何目的与意义。 三、将以上的理解加以运用与操作。 第三章第三章 需求分析需求分析 3.1 原理 本课
