用邻接表存储结构实现图的遍历.doc

张娜 用邻接表存储结构实现图的遍历 第 PAGE 6 页 共23 页 用邻接表存储结构实现图的遍历 学生姓名：张娜 指导老师：龚晓萍 摘 要 本课程设计主要实现用邻接表存储结构对图进行操作。在课程设计中，系统开发平台为Windows 2000，程序设计语言采用Visual C++，程序运行平台为Windows 98/2000/XP。用邻接表存储结构在图中对顶点进行插入、删除、修改操作，对图进行深度优先及广度优先遍历。程序通过调试运行，实现了设计的目标。 关键词 程序设计；C++；邻接表；图 1 引 言 上学期我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构就是图的边信息的矩阵中全部非零元素的三元组的行指针数组结构的三元组链表，是一种顺序存储与链式存储相结合的存储方法[1]。二者各有利弊，具体应用时，要根据图的稠密和稀疏程度以及问题需求进行选择。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低[3]。 本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现结点的插入、删除和修改操作，以及对图实现深度优先和广度优先遍历。 本课程设计是用C++语言辅助完成，在Visual C++6.0平台实现的。我们大一学过C++，对C++比较熟悉。并且我自己电脑上安装了Visual C++6.0，所以C++是我编程的最佳选择。 2 问题分析 2.1 技术分析 C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。它是由C语言发展而来的，既可以用于面向过程的结构化程序设计，也可以用于面向对象的程序设计,是一门功能强大的程序设计语言[2]。 Visual C++6.0是Microsoft公司在1998年推出的基于Windows 9X和Windows NT一个优秀集成开发环境。该开发环境为用户提供了良好的可视化编程环境，程序员可以利用该开发环境轻松地访问C++源代码编辑器、资源编辑器和使用内部调试器，并且可以创建项目文件。Visual C++6.0不仅包括编译器，而且它还包括许多有用组件，如程序向导AppWizard、类向导Class Wizard等，通过这些组件的协同工作，可以在VisualC++6.0集成开发环境中轻松的完成创建源文件、编辑资源，以及对程序的编译、连接和调试等各项工作[5] 2.2 需求分析 当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点。还有时需要对图进行深度优先及广度优先遍历。本系统将所有这些功能都包括进来，以长沙理工大学的教学楼为顶点构建了一个图。运行本系统可对该图进行顶点的插入、删除和修改，还可对该图进行深度优先及广度优先遍历。控制方法如下： 表2-1 控制键的功能 控制键 0 1 2 3 4 5 6 7 功能 输出 输出任 插入 修改 删除 深度优 广度优 退出 顶点 一顶点 顶点 顶点 顶点 先遍历 先遍历 3 系统总框架及算法设计 3.1 系统总框架 系统的主要功能是用邻接表存储结构在图中对顶点进行插入、删除、修改操作，并对图进行深度优先及广度优先遍历。总框架如下： 显示 显示“需要输出顶点信息请按0 需要输出任一顶点信息请按1 需要插入顶点请按2 需要修改顶点请按3 需要删除顶点请按4 需要深度优先遍历请按5 需要广度优先遍历请按6 需要退出请按7” 输入所要执行的功能。 顶点的输出、插入、删除与修改退出系统 顶点的输出、插入、删除与修改 退出系统 图的深度及广度优先遍历 图3-1 系统总框架 3.2 算法设计 （1）首先，要定义头文件，在头文件中定义边表结点ArcNode和顶点表结点VertexNode。具体如下： struct ArcNode