1、 数 据 结 构 课 程 设 计 设计题目： 图的邻接表存储及其应用 课题名称 图的邻接表存储及其应用 院 系 年级专业 学 号 课题设计 目的与 设计意义 1、课题设计目的： 一、是让我们通过实习掌握数据结构中的知识。 对于图的遍历这一课题来说，所要求掌握的数据结构知识主要 有：图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实 现、图的广度优先搜索、图的深度优先搜索算法实现。 二、是通过实习巩固并提高实习者的 C 语言知识，并初步了解 C+的知识，提高编程能力与专业水平。 2、课题设计意义：一、通过对邻接表表示图及深广度优先遍历 程序的编写，对数据结构的理解更为加深。二、培养了我们独立
2、设 计程序与解决问题的能力，培养了我们团队协作集成程序模块及调 试能力。三、培养了学生初步的软件设计及软件测试的能力。 指导教师： 年 月 日 目目 录录 第一章 课程设计目的 第二章 课程设计内容和要求 2.1 课程设计内容 2.1.1 图的邻接表的建立与输出 . 2.1.2 图的遍历的实现 2.2 运行环境 . 第三章 课程设计分析 3.1 图的存储 3.2 图的遍历 . 3.2.1 图的深度优先遍历 3.2.2 图的广度优先遍历 第四章 算法（数据结构）描述 4.1 图的存储结构的建立。 . 4.1.1 定义邻接表的边结点类型以及邻接表类型 4.1.2 初始化图的邻接表 4.1.3 建立
3、并输出图的邻接表 4.2 图的遍历 . 4.2.1 深度优先遍历图的邻接表 4.2.2 广度优先遍历图的邻接表 第五章 源代码 第六章 运行结果分析 第七章 结束语 第八章 参考文献 第一章第一章 课程设计目的课程设计目的 本学期我们对数据结构这门课程进行了学习。这门课程是一门实践性非常强的课程，为 了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程 设计不但要求实习者掌握数据结构中的各方面知识，还要求实习者具备一定的 C 语言基础和 编程能力。 具体说来，这次课程设计主要有两大方面目的。 一是让实习者通过实习掌握数据结构中的知识。对于图的遍历这一课题来说，所
4、要 求掌握的数据结构知识主要有：图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、 图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。 二是通过实习巩固并提高实习者的 C 语言知识，并初步了解 Visual C+的知识，提高其编程 能力与专业水平。 第二章第二章 课程设计内容和要求课程设计内容和要求 2.1 课程设计内容 该课题要求以邻接表的方式存储图，输出邻接表，并要求实现图的深度、广度两种遍历。 2.1.1 图的邻接表的建立与输出 对任意给定的图（顶点数和边数自定） ，并且对有向图与无向图都应进行讨论，根据邻接表 的存储结构建立图的邻接表并输出之。尽量用图形化的方式输出邻
5、接表。 2.1.2 图的遍历的实现 图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本 运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出 发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优 先遍历则采用递归或非递归算法来实现。 2.2 运行环境 该程序的运行环境为 Windows xp 系统，Microsoft Visual C+6.0 版本。 第三章第三章 课程设计分析课程设计分析 3.1 图的存储 本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构，在邻接表中，对图中每 个顶点建立一
6、个单链表，第 i 个单链表中的结点表示依附于顶点 Vi 的边（对有向图是以顶点 Vi 为尾的在图中的位置，链域（nextarc）指示下一条弧） 。每个结点由 3 个域组成，其中邻接点域 （adjvex）指示与顶点 Vi 邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数 据域（info）存储和边或弧相关的信息，如权值等。 所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后 根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号， 建立图的邻接表。此时要分两种情况：有向图与无向图。对于无向图，一条边的两的个顶点，互 为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表 表头插入一边结点，即起点。对于有向图，只能向起点的单链表的表头插入一个边结点，即终点。 但不能反过来。至于邻接表的输出，由于不了解
