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

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

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

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

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

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

6、按5 需要广度优先遍历请按6 需要退出请按7”输入所要执行的功能。顶点的输出、插入、删除与修改退出系统图的深度及广度优先遍历图3-1 系统总框架3.2 算法设计 （1）首先，要定义头文件，在头文件中定义边表结点ArcNode和顶点表结点VertexNode。具体如下：struct ArcNode /定义边表结点int adjvex; /邻接点域 ArcNode *next; ;/指向下一个边结点的指针template <class T>struct VertexNode /定义顶点表结点T vertex; /顶点的名称 ArcNode *firstedge; ; /边表的头指针其次

7、，在头文件中还需定义邻接表存储结构下图的抽象数据类型定义。（2）编写源文件，必须先引入头文件。然后进行图的初始化，首先要输入顶点信息，初始化顶点表。然后依次输入每一条边，并在相应边表中插入结点。再输入边所依附的两个顶点的序号。最后生成一个编表结点，将生成的结点插入到编表的表头。接下来编写对图进行的各种操作。用析构函数ALGraph( )循环删除释放节点空间。ALGraph<T>:ALGraph( ) for (int i=0; i<vertexNum; i+) ArcNode * p=adjlisti.firstedge;while(p!=NULL) /循环删除 adjlis

8、ti.firstedge=p->next; delete p; /释放结点空间 p=adjlisti.firstedge; 用函数Get(int i)输出图中某一顶点的数据信息。输入顶点的位置就可以输出顶点的信息。用函数Put(int i, T value)将图中顶点的数据域置为value，修改图的顶点的信息。输入需要修改的位置和顶点信息，就可以将顶点信息修改。用函数Insert(int i, T value)在图中指定的位置插入一个顶点。输入需要插入的位置及插入的内容即可完成。用函数Delete(int i)在图中删除指定的顶点。输入需要删除顶点的位置就可以成功删除顶点。用函数DFST

9、raverse(int v)对图从指定顶点进行深度优先遍历。先访问指定的顶点v，从该顶点的未被访问的邻接点中选取一个顶点p,从p出发进行深度优先遍历。重复以上步骤，直至图中所有和v有路径相通的顶点都被访问到，用函数BFSTraverse(int v)对图从指定顶点进行广度优先遍历。先访问顶点v，依次访问v的各个未被访问的邻接点v1,v2,vk,分别从,v1,v2,vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问的顶点”被访问，直至图中所有与顶点v有路径相通的顶点都被访问到。（3）编写主函数。用数组存放图的五个顶点：工科楼、教学楼、实验楼、文法楼、理科楼。输入所要

10、进行的操作的序号，并设置每次只能选择一种功能。用switch进行功能选择。调用相应的函数。4 具体实现及运行结果4.1 创建工程并建立文件（1）启动Microsoft Visual C+ 6.0。（2）新建工程名为“邻接表” 的Win32控制台应用程序。（3）建立头文件“graph.h”，在其中定义图类AlGraph。定义结构体边表结点ArcNode和定点表结点VertexNode。（4）建立源文件“graph.cpp”， 在其中定义图类AlGraph的构造函数AlGraph、析构函数AlGraph、获取顶点信息的函数Get()、修改顶点的函数Put()、插入顶点的函数Insert()、删除顶

11、点的函数Delete()、深度优先遍历的函数DFSTraverse()、广度优先遍历的函数BFSTraverse()。（5）建立源文件“graphmain.cpp”，在其中输入顶点信息，输出操作列表。通过主函数调用其他各函数，实现设计目的。4.2 运行状况为使每次操作后，运行进程回到同一状态，就必须设置一个初始状态并且在用户退出使用后回到这一状态。由于每次操作用户都需根据操作列表进行选择，故将操作列表设为初始状态。如图4-1所示。 图4-1 初始状态输出全部顶点的信息，按0键。输出情况如图4-2所示 图4-2 所有顶点的信息 按1键，输出任一顶点的信息。输入所要输出的顶点，这里以顶点1为例。如

12、图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键，删除顶点。输入想

13、要删除的顶点。这里以删除1顶点为例。如图4-6所示。图4-6 删除顶点1按5键，对图进行深度优先遍历。输入开始遍历的顶点。输出如图4-7所示。4-7 图的深度优先遍历按6键，对图进行广度优先遍历，输入开始遍历的顶点。输出如图4-8所示。 图4-8 图的广度优先遍历按7键，退出系统。如图4-9所示。 图4-9 退出系统 5 结束语 经过两周的努力，我的课程设计终于出炉了。本课程设计主要运用数据结构知识和C+程序设计完成了用邻接表存储结构实现对图的操作。该系统的主要功能为：顶点的插入、顶点的删除、顶点的修改、深度优先遍历、广度优先遍历。在这次数据结构的课程设计中，曾遇到过一些问题，在老师和同学的帮

14、助下，得到了解决。在此，我衷心感谢指导老师龚晓萍老师和学校给予的良好环境的帮助可以让我们顺利完成这次课程设计。同时，也要感谢我的数据结构任课老师陈倩诒老师，她以详细清晰的讲解带着我们完成了数据结构（C+版）的学习。 参考文献1 朱战立.数据结构使用C+语言.西安：西安电子科技大学出版社，20002 谭浩强. C+程序设计. 北京：清华大学出版社，20043 周海英，马巧梅.数据结构与算法设计.北京：国防工业出版社，20074 王红梅，胡明，王涛. 数据结构（C+版）. 北京：清华大学出版社，20055 美D.S.Malik. +编程 数据结构与程序设计方法 . 北京：清华大学出版社，2005附

15、录1：源文件主函数程序设计清单/ 程序名称：graphmain. cpp/ 程序功能：输出操作列表，调用操作函数/ 程序作者：张娜/ 最后修改日期：2009-9-20#include <iostream>#include <string>#include "graph.cpp"using namespace std;int visitedMaxSize;void main( )/输出操作列表 int which;int j;string name;int choose=1;/选择一项功能string a5 = "工科楼",&quo

16、t;教学楼","实验楼","文法楼","理科楼"ALGraph<string> algraphTest( a, 5, 0); /构造图while ( choose=1 ) /控制 cout << "需要输出顶点信息请按0" << endl; /输入所要进行的操作的序号 cout << "需要输出任意一个顶点信息请按1" << endl; cout << "需要插入顶点请按2" <<

17、endl; cout << "需要修改顶点请按3" << endl; cout << "需要删除顶点请按4" << endl; cout << "需要深度优先遍历请按5" << endl; cout << "需要广度优先遍历请按6" << endl; cout << "需要退出请按7" << endl; cin >> which; switch( which ) /

18、功能选择case 0:for(j=0;j<5;j+ )cout<<algraphTest.GetVex(j)<<" " /输出顶点 cout<<endl; break;case 1:int i;cout<<"请输入顶点："<<endl;cin>>i;trycout<<algraphTest.GetVex(i)<<endl; /输出i顶点的数据域catch(char* s)cout<<s<<endl;break;case 2: /在

19、图中的i位置插入一顶点值为namecout<<"请输入顶点及名字："<<endl;cin>>i>>name;tryalgraphTest.InsertVex(i, name); catch(char* s)cout<<s<<endl; break;case 3: /修改图中一顶点的值cout<<"请输入顶点及名字："<<endl;cin>>i>>name; tryalgraphTest.PutVex(i, name); catch(ch

20、ar* s) cout<<s<<endl; break;case 4: /删除图中一顶点的值cout<<"请输入顶点："<<endl;cin>>i; try algraphTest.DeleteVex(i); catch(char* s)cout<<s<<endl;break; case 5: /图的深度优先搜索 cout<<"请输入顶点："<<endl;cin>>i;cout<<endl<<"从第&q

21、uot;<<i<<"个顶点深度优先遍历图"<<endl; tryfor (int ii=0; ii<MaxSize; ii+) visitedii = 0; algraphTest.DFSTraverse(i); catch(char* s) cout<<s<<endl; break;case 6: /图的广度优先搜索cout<<"请输入顶点："<<endl;cin>>i;cout<<endl<<"从第"<

22、;<i<<"个顶点广度优先遍历图"<<endl; tryfor (int ii=0; ii<MaxSize; ii+) visitedii = 0;algraphTest.BFSTraverse(i); catch(char*s)cout<<s<<endl;break;case 7: /退出choose=0; break; 附录2 源文件程序设计清单/ 程序名称：graph. cpp/ 程序功能：定义操作函数/ 程序作者：张娜/ 最后修改日期：2009-9-20#include<iostream>#in

23、clude "graph.h" /引入头文件template <class T>ALGraph<T>:ALGraph(T a , int n, int e) arcNum = e; /边数vertexNum=n; /顶点数 int i,j;for (i=0; i<vertexNum; i+) VertexNode<T> tempvertex; tempvertex.vertex = ai; tempvertex.firstedge = NULL; adjlisti = tempvertex;for (int k=0; k<ar

24、cNum; k+) /依次输入每一条边，并在相应边表中插入结点 cout<<"请输入边所依附的两个顶点的序号"cin>>i>>j; /输入边所依附的两个顶点的序号 ArcNode *s=new ArcNode; s->adjvex=j; /生成一个边表结点s s->next=adjlisti.firstedge; /将结点s插入到结点i的边表的表头 adjlisti.firstedge=s;InsertArc(0,1); /插入边InsertArc(0,2);InsertArc(0,3);InsertArc(1,3);Inse

25、rtArc(1,4);InsertArc(2,0);InsertArc(2,4);InsertArc(3,1);InsertArc(3,4);InsertArc(4,2);InsertArc(4,3)；template <class T>ALGraph<T>:ALGraph( )for (int i=0; i<vertexNum; i+) ArcNode * p=adjlisti.firstedge;while (p!=NULL) /循环删除adjlisti.firstedge=p->next; delete p; /释放结点空间 p=adjlisti.fi

26、rstedge; template <class T>T ALGraph<T>:GetVex(int i)if ( i>vertexNum | i<0 ) throw "输入顶点的位置不正确" /顶点i不存在则抛出异常return adjlisti.vertex; /返回第i个顶点的数据域 template <class T>void ALGraph<T>:PutVex(int i, T value)if ( i>vertexNum | i<0 ) throw "输入顶点的位置不正确"

27、; /顶点i不存在则抛出异常adjlisti.vertex = value; /第i个顶点的数据域置为valuetemplate <class T>void ALGraph<T>:InsertVex(int i, T value)if ( i>vertexNum | i<0 | i>MaxSize ) throw "输入顶点的位置不正确" /顶点i不存在则抛出异常if (i<vertexNum | i>MaxSize) throw "输入顶点的位置不正确"vertexNum+; /顶点数加1Verte

28、xNode<T> tempvertex;tempvertex.vertex = value;tempvertex.firstedge = NULL;adjlisti = tempvertex; /第i个顶点的数据域置为value template <class T>void ALGraph<T>:DeleteVex(int i)if ( i<0 | i>MaxSize) throw "位置" /顶点输入错误则抛出异常int k;for ( k=0; k<vertexNum; k+) /删掉入度边 if(k!=i) Del

29、eteArc(k, i);ArcNode *s; /生成一个边表结点sif( adjlisti.firstedge != NULL)ArcNode *s; s=adjlisti.firstedge->next; while(s!=NULL)ArcNode *p; p = s;adjlisti.firstedge->next = s->next;s=s->next;delete p; /删除p结点s=adjlisti.firstedge;adjlisti.firstedge=NULL;delete s;for (k=i; k<vertexNum; k+) adjli

30、stk=adjlistk+1; /存储顶点信息 vertexNum-; /顶点数减1 for (k=0; k<vertexNum; k+)if( adjlistk.firstedge != NULL )s=adjlistk.firstedge; /将结点s插入到结点i的边表的表头while(s!=NULL)if(s->adjvex > i) /搜索i结点s->adjvex-;s = s->next; template <class T>void ALGraph<T>:InsertArc(int i, int j)if ( i>MaxS

31、ize | j>MaxSize) throw "位置"/顶点输入错误则抛出异常ArcNode *s=new ArcNode; s->adjvex=j; /生成一个边表结点ss->next=adjlisti.firstedge; /将结点s插入到结点i的边表的表头 adjlisti.firstedge=s; template <class T>void ALGraph<T>:DeleteArc(int i, int j)if ( i>MaxSize| j>MaxSize) throw "位置" /顶点输

32、入错误则抛出异常ArcNode *s; ArcNode *tempnode;s = adjlisti.firstedge;tempnode = adjlisti.firstedge;while(s!=NULL && s->adjvex!=j)tempnode = s;s = s->next;if(s!=NULL)tempnode->next = s->next;delete s;template <class T>void ALGraph<T>:DFSTraverse(int v)if ( v>vertexNum) thro

33、w "位置" /顶点输入错误则抛出异常ArcNode * p; int j;cout<<adjlistv.vertex<<" " visitedv=1; p=adjlistv.firstedge; while (p) /依次搜索顶点v的邻接点j j=p->adjvex; if (visitedj=0) DFSTraverse(j); p=p->next; template <class T>void ALGraph<T>:BFSTraverse(int v) if ( v>vertexNum) throw "位置" /顶点输入错误则抛出异常 int front,rear,j; ArcNode * p; /生成一个边表结点p int QMaxSize; front=rear=-1; /初始化队列, 假设队列采用顺序存储且不会发生溢出 cout<<adjlistv.vertex<<" " visitedv=1;