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

用邻接表存储结构实现图的遍历学生姓名：XXXX指导老师：XXXX摘要本课程设计主要实现用邻接表存储结构对图进行操作。在课程设计中，系统开发平台为Windows2000，程序设计语言采用VisualC++，程序运行平台为Windows98/2000/XP。用邻接表存储结构在图中对顶点进行插入、删除、修改操作，对图进行深度优先及广度优先遍历。程序通过调试运行，实现了设计的目标。关键词程序设计；C++；邻接表；图1引言上学期我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构就是图的边信息的矩阵中全部非零元素的三元组的行指针数组结构的三元组链表，是一种顺序存储与链式存储相结合的存储方法[1]。二者各有利弊，具体应用时，要根据图的稠密和稀疏程度以及问题需求进行选择。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低[3]。本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现结点的插入、删除和修改操作，以及对图实现深度优先和广度优先遍历。本课程设计是用C++语言辅助完成，在VisualC++6.0平台实现的。我们大一学过C++，对C++比较熟悉。并且我自己电脑上安装了VisualC++6.0，所以C++是我编程的最佳选择。2问题分析2.1技术分析C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。它是由C语言发展而来的，既可以用于面向过程的结构化程序设计，也可以用于面向对象的程序设计,是一门功能强大的程序设计语言[2]。VisualC++6.0是Microsoft公司在1998年推出的基于Windows9X和WindowsNT一个优秀集成开发环境。该开发环境为用户提供了良好的可视化编程环境，程序员可以利用该开发环境轻松地访问C++源代码编辑器、资源编辑器和使用内部调试器，并且可以创建项目文件。VisualC++6.0不仅包括编译器，而且它还包括许多有用组件，如程序向导AppWizard、类向导ClassWizard等，通过这些组件的协同工作，可以在VisualC++6.0集成开发环境中轻松的完成创建源文件、编辑资源，以及对程序的编译、连接和调试等各项工作[5]2.2需求分析当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点。还有时需要对图进行深度优先及广度优先遍历。本系统将所有这些功能都包括进来，以长沙理工大学的教学楼为顶点构建了一个图。运行本系统可对该图进行顶点的插入、删除和修改，还可对该图进行深度优先及广度优先遍历。控制方法如下：表2-1控制键的功能控制键01234567功能输出输出任插入修改删除深度优广度优退出顶点一顶点顶点顶点顶点先遍历先遍历3系统总框架及算法设计3.1系统总框架系统的主要功能是用邻接表存储结构在图中对顶点进行插入、删除、修改操作，并对图进行深度优先及广度优先遍历。总框架如下：图3-1系统总框架显示“需要输出顶点信息请按0需要输出任一顶点信息请按1需要插入顶点请按2需要修改顶点请按3需要删除顶点请按4需要深度优先遍历请按5需要广度优先遍历请按6需要退出请按7”输入所要执行的功能。顶点的输出、插入、删除与修改图的深度及广度优先遍历退出系统3.2算法设计（1）首先，要定义头文件，在头文件中定义边表结点ArcNode和顶点表结点VertexNode。具体如下：structArcNode//定义边表结点{intadjvex;//邻接点域ArcNode*next;};//指向下一个边结点的指针templateclassTstructVertexNode//定义顶点表结点{Tvertex;//顶点的名称ArcNode*firstedge;};//边表的头指针其次，在头文件中还需定义邻接表存储结构下图的抽象数据类型定义。（2）编写源文件，必须先引入头文件。然后进行图的初始化，首先要输入顶点信息，初始化顶点表。然后依次输入每一条边，并在相应边表中插入结点。再输入边所依附的两个顶点的序号。最后生成一个编表结点，将生成的结点插入到编表的表头。接下来编写对图进行的各种操作。用析构函数~ALGraph()循环删除释放节点空间。ALGraphT::~ALGraph(){for(inti=0;ivertexNum;i++){ArcNode*p=adjlist[i].firstedge;while(p!=NULL)//循环删除{adjlist[i].firstedge=p-next;deletep;//释放结点空间p=adjlist[i].firstedge;}}用函数Get(inti)输出图中某一顶点的数据信息。输入顶点的位置就可以输出顶点的信息。用函数Put(inti,Tvalue)将图中顶点的数据域置为value，修改图的顶点的信息。输入需要修改的位置和顶点信息，就可以将顶点信息修改。用函数Insert(inti,Tvalue)在图中指定的位置插入一个顶点。输入需要插入的位置及插入的内容即可完成。用函数Delete(inti)在图中删除指定的顶点。输入需要删除顶点的位置就可以成功删除顶点。用函数DFSTraverse(intv)对图从指定顶点进行深度优先遍历。先访问指定的顶点v，从该顶点的未被访问的邻接点中选取一个顶点p,从p出发进行深度优先遍历。重复以上步骤，直至图中所有和v有路径相通的顶点都被访问到，用函数BFSTraverse(intv)对图从指定顶点进行广度优先遍历。先访问顶点v，依次访问v的各个未被访问的邻接点v1,v2,…,vk,分别从,v1,v2,…vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问的顶点”被访问，直至图中所有与顶点v有路径相通的顶点都被访问到。（3）编写主函数。用数组存放图的五个顶点：工科楼、教学楼、实验楼、文法楼、理科楼。输入所要进行的操作的序号，并设置每次只能选择一种功能。用switch进行功能选择。调用相应的函数。4具体实现及运行结果4.1创建工程并建立文件（1）启动MicrosoftVisualC++6.0。（2）新建工程名为“邻接表”的Win32控制台应用程序。（3）建立头文件“graph.h”，在其中定义图类AlGraph。定义结构体边表结点ArcNode和定点表结点VertexNode。（4）建立源文件“graph.cpp”，在其中定义图类AlGraph的构造函数AlGraph、析构函数~AlGraph、获取顶点信息的函数Get()、修改顶点的函数Put()、插入顶点的函数Insert()、删除顶点的函数Delete()、深度优先遍历的函数DFSTraverse()、广度优先遍历的函数BFSTraverse()。（5）建立源文件“graphmain.cpp”，在其中输入顶点信息，输出操作列表。通过主函数调用其他各函数，实现设计目的。4.2运行状况为使每次操作后，运行进程回到同一状态，就必须设置一个初始状态并且在用户退出使用后回到这一状态。由于每次操作用户都需根据操作列表进行选择，故将操作列表设为初始状态。如图4-1所示。图4-1初始状态输出全部顶点的信息，按0键。输出情况如图4-2所示图4-2所有顶点的信息按1键，输出任一顶点的信息。输入所要输出的顶点，这里以顶点1为例。如图4-3（1）。若输入的顶点图中不存在，则如图4-3（2）所示、图4-3（1）输出顶点1图4-3（2）需要输出的顶点不存在按2键，插入一个顶点。输入需要插入的顶点及名字。这里以在0位置插入艺术楼为例。如图4-4（1）所示。若插入位置不正确，则显示插入位置不正确，如图4-4（2）所示。图4-4（1）在0处插入艺术楼图4-4（2）在7处插入艺术楼按3键，修改顶点，输入需要修改的顶点及名字，这里以将1顶点的教学楼修改为艺术楼为例。如图4-5（1）所示。如果输入的顶点不存在，则显示顶点不存在。如图4-5（2）所示。图4-5（1）修改顶点2图4-5（2）输入位置错误按4键，删除顶点。输入想要删除的顶点。这里以删除1顶点为例。如图4-6所示。图4-6删除顶点1按5键，对图进行深度优先遍历。输入开始遍历的顶点。输出如图4-7所示。4-7图的深度优先遍历按6键，对图进行广度优先遍历，输入开始遍历的顶点。输出如图4-8所示。图4-8图的广度优先遍历按7键，退出系统。如图4-9所示。图4-9退出系统5结束语经过两周的努力，我的课程设计终于出炉了。本课程设计主要运用数据结构知识和C++程序设计完成了用邻接表存储结构实现对图的操作。该系统的主要功能为：顶点的插入、顶点的删除、顶点的修改、深度优先遍历、广度优先遍历。在这次数据结构的课程设计中，曾遇到过一些问题，在老师和同学的帮助下，得到了解决。在此，我衷心感谢指导老师龚晓萍老师和学校给予的良好环境的帮助可以让我们顺利完成这次课程设计。同时，也要感谢我的数据结构任课老师——陈倩诒老师，她以详细清晰的讲解带着我们完成了数据结构（C++版）的学习。参考文献[1]朱战立.数据结构——使用C++语言.西安：西安电子科技大学出版社，2000[2]谭浩强.C++程序设计.北京：清华大学出版社，2004[3]周海英，马巧梅.数据结构与算法设计.北京：国防工业出版社，2007[4]王红梅，胡明，王涛.数据结构（C++版）.北京：清华大学出版社，2005[5]〔美〕D.S.Malik.++编程——数据结构与程序设计方法.北京：清华大学出版社，2005附录1：源文件主函数程序设计清单//程序名称：graphmain.cpp//程序功能：输出操作列表，调用操作函数//程序作者：张娜//最后修改日期：2009-9-20#includeiostream#includestring#includegraph.cppusingnamespacestd;intvisited[MaxSize];voidmain()//输出操作列表{intwhich;intj;stringname;intchoose=1;//选择一项功能stringa[5]={工科楼,教学楼,实验楼,文法楼,理科楼};ALGraphstringalgraphTest(a,5,0);//构造图while(choose==1)//控制{cout需要输出顶点信息请按0endl;//输入所要进行的操作的序号cout需要输出任意一个顶点信息请按1endl;cout需要插入顶点请按2endl;cout需要修改顶点请按3endl;cout需要删除顶点请按4endl;cout需要深度优先遍历请按5endl;cout需要广度优先遍历请按6endl;cout需要退出请按7endl;cinwhich;switch(which)//功能选择{case0:for(j=0;j5;j++)coutalgraphTest.GetVex(j);//输出顶点coutendl;break;case1:inti;cout请输入顶点：endl;cini;try{coutalgraphTest.GetVex(i)endl;}//输出i顶点的数据域catch(char*s){coutsendl;}break;case2://在图中的i位置插入一顶点值为namecout请输入顶点及名字：endl;cininame;try{algraphTest.InsertVex(i,name);}catch(char*s){coutsendl;}break;c