资源描述：
《课程设计-邻接表---副本.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、摘要本课程设计主要实现用邻接表存储结构对图进行操作。在课程设计中，程序以邻接表对图进行存储，并利用数组、队列等结构加以辅助存储；最终实现图的建立，图的链表结构的输出，图的深度优先遍历及广度优先遍历。关键字:图邻接表队列遍历AbstractThiscurriculumdesignisdesignedtoachieveoperationsofgraphwithadjacencytablestoragestructure.Inthecurriculumdesign,theprogramisstoredwihttheadjacencytable,andbeassistedbyarrays,
2、queue,andsoon.Finally,toachievetheconstructionofagraph,outputtheliststructureofthegraph,depth-firsttraversalgraphandbreadth-firsttraversalgraph.Keyword:GraphAdjacencylistQueueTraversal1.引言本学期我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构是一种
3、顺序存储与链式存储相结合的存储方法。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。2.需求分析2.1原理当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点，而这些操作都需要一图的深度优先及广度优先遍历为基础。本系统将构建一个图，图的结点存储的是int型数据。运行本系统可
4、对该图进行链式结构输出、深度优先及广度优先遍历。控制方法如下：表2-1控制键的功能控制键1230功能输出链表结构深度优先遍历广度优先遍历退出2.2要求（1）建立基于邻接表的图；（2）对图进行遍历；（3）输出遍历结果；2.3运行环境(1)WINDOWS7系统(2)C++编译环境2.4开发工具C++语言3.数据结构分析本课程设计是针对于图的，程序中采用邻接表进行数据存储。邻接表是一种顺序存储与链式存储相结合的存储方法，该存储方式在图比较稀疏是相对于图的邻接矩阵存储有明显优势。设计实现了图的邻接表结构输出、深度有新遍历和广度优先遍历操作的实现。4.算法设计4.1概要设计（1）首先，要定义
5、头文件，在头文件中定义邻接点point、图的基本结点graph以及在广度优先搜索中会用到队列queue。具体如下：structpoint{intn;//邻接点的序号point*next;//指向下一条弧节点的地址};structgraph{intdata;//表接点的数据structpoint*f;//结点的指针域，给出自该结点发出的第一弧节点的地址};structqueue{intelem[d];//队列的容量intfront;//front为首指针，指向第一个元素intrear;//rear为最后一个元素，指向队尾元素的下一个位置}q;其次，在头文件中还需定义邻接表存储结构下图
6、的抽象数据类型定义。（2）编写源文件，进行图的初始化，首先要输入顶点信息，初始化顶点表，在输入点v的值时，同时构造v的邻接点。输入邻接点的序号，最后生成一个邻接点链表。子函数功能：1.voidcreatgraph(intm)//n表示节点的个数构造图的链表结构，在此函数中要输入图结点的值，邻接点的序号。2.voidprint(structgrapha[],intm)将图a的链表结构打印出来,m为结点个数3.voiddpv(structgrapha[],intv)对图进行深度优先遍历。先访问指定的顶点v，从该顶点的未被访问的邻接点中选取一个顶点p,从p出发进行深度优先遍历。重复以上的
7、步骤，直至图中所有和v有路径相通的顶点都被访问到。4.voidwdv(structgrapha[],intv,queue&Q)从v点开始广度优先遍历a是连通图或是连通分量），先访问顶点v，依次访问v的各个未被访问的邻接点v1,v2,…,vk,分别从,v1,v2,…vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问的顶点”被访问，直至图中所有与顶点v有路径相通的顶点都被访问到。5.voidenqueue(queue&Q,inte)e入队列Q
