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

《用邻接表存储结构实现图的遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用邻接表存储结构实现图的遍历学生姓名：XXXX指导老师：XXXX摘要本课程设计主要实现用邻接表存储结构对图进行操作。在课程设计中，系统开发平台为Windows2000，程序设计语言采用VisualC++，程序运行平台为Windows98/2000/XP。用邻接表存储结构在图中对顶点进行插入、删除、修改操作，对图进行深度优先及广度优先遍历。程序通过调试运行，实现了设计的目标。关键词程序设计；C++；邻接表；图1引言上学期我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存

2、储方法。图的邻接表存储结构就是图的边信息的矩阵中全部非零元素的三元组的行指针数组结构的三元组链表，是一种顺序存储与链式存储相结合的存储方法[1]。二者各有利弊，具体应用时，要根据图的稠密和稀疏程度以及问题需求进行选择。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低[3]。本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现结点的插入、删除和修改操作，以及对图实现深度优先和广度优先遍历。本课程设计是用C++语言辅助完成，在VisualC++6.0平台实现的。我们大一学过C++，对C++比较熟悉。并且我自己电脑上

3、安装了VisualC++6.0，所以C++是我编程的最佳选择。2问题分析2.1技术分析C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。它是由C语言发展而来的，既可以用于面向过程的结构化程序设计，也可以用于面向对象的程序设计,是一门功能强大的程序设计语言[2]。VisualC++6.0是Microsoft公司在1998年推出的基于Windows9X和WindowsNT一个优秀集成开发环境。该开发环境为用户提供了良好的可视化编程环境，程序员可以利用该开发环境轻松地访问C++源代码编

4、辑器、资源编辑器和使用内部调试器，并且可以创建项目文件。VisualC++6.0不仅包括编译器，而且它还包括许多有用组件，如程序向导AppWizard、类向导ClassWizard等，通过这些组件的协同工作，可以在VisualC++6.0集成开发环境中轻松的完成创建源文件、编辑资源，以及对程序的编译、连接和调试等各项工作[5]2.2需求分析当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点。还有时需要对图进行深度优先及广度优先遍历。本系统将所有这些功能都

5、包括进来，以长沙理工大学的教学楼为顶点构建了一个图。运行本系统可对该图进行顶点的插入、删除和修改，还可对该图进行深度优先及广度优先遍历。控制方法如下：表2-1控制键的功能控制键01234567功能输出输出任插入修改删除深度优广度优退出顶点一顶点顶点顶点顶点先遍历先遍历3系统总框架及算法设计3.1系统总框架系统的主要功能是用邻接表存储结构在图中对顶点进行插入、删除、修改操作，并对图进行深度优先及广度优先遍历。总框架如下：显示“需要输出顶点信息请按0需要输出任一顶点信息请按1需要插入顶点请按2需要修改顶点请按3需要删除顶点请按4需要深度优先遍历请按5需要广度优先遍历请按6需要退出请按7”输入所

6、要执行的功能。顶点的输出、插入、删除与修改退出系统图的深度及广度优先遍历图3-1系统总框架3.2算法设计（1）首先，要定义头文件，在头文件中定义边表结点ArcNode和顶点表结点VertexNode。具体如下：structArcNode//定义边表结点{intadjvex;//邻接点域ArcNode*next;};//指向下一个边结点的指针templatestructVertexNode//定义顶点表结点{Tvertex;//顶点的名称ArcNode*firstedge;};//边表的头指针其次，在头文件中还需定义邻接表存储结构下图的抽象数据类型定义。（2）编写源文件，必须

7、先引入头文件。然后进行图的初始化，首先要输入顶点信息，初始化顶点表。然后依次输入每一条边，并在相应边表中插入结点。再输入边所依附的两个顶点的序号。最后生成一个编表结点，将生成的结点插入到编表的表头。接下来编写对图进行的各种操作。用析构函数~ALGraph()循环删除释放节点空间。ALGraph::~ALGraph(){for(inti=0;i