数据结构课程设计--图的遍历.doc

《数据结构课程设计--图的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.1.引言数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。在软件工程专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机部用相应的数据结构来表示，然后设计一个

2、解此数学模型的算法，再进行编程调试，最后获得问题的解答。图是一种非常重要的数据结构，在《数据结构》中也占着相当大的比重。这个学期的数据结构课程中，我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构是一种顺序存储与链式存储相结合的存储方法。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。本课程设计主要是实现使用邻接

3、表存储结构存储一个图，并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。2.需求分析2.1原理当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点，而这些操作都需要一图的深度优先及广度优先遍历为基础。本系统将构建一个图，图的结点存储的是int型数据。运行本系统可对该图进行链式结构输出、深度优先及广度优先遍历。控制方法如下：表2-1控制键的功能..控制键1230功能输出链表结构

4、深度优先遍历广度优先遍历退出2.2要求（1）建立基于邻接表的图；（2）对图进行遍历；（3）输出遍历结果；2.3运行环境(1)WINDOWS7系统(2)C++编译环境2.4开发工具C++语言3.数据结构分析本课程设计是针对于图的，程序中采用邻接表进行数据存储。在计算机科学中，邻接表描述一种紧密相关的数据结构，用于表征图。在邻接表的表示中，对于图中的每个顶点，我们将保存所有其它与之相连的顶点（即“邻接表”）。邻接表是一种顺序存储与链式存储相结合的存储方法，该存储方式在图比较稀疏是相对于图的邻接矩阵存储有明显优势。设计实现了图的

5、邻接表结构输出、深度有新遍历和广度优先遍历操作的实现。邻接表的结构：（1）、头结点结构firstarcdataFirstarc：结点的指针域（2）、邻接点的结构nextarcadjvexAdjvex：邻接点的数据域；..Nextarc：邻接点的指针域，指向下一个邻接点；在该程序中，除了邻接表结构以外，还有到了一个mark[]数组，它是用来标记结点Vi是否被访问。若Vi被访问，则mark[i]=1，否则为0；它是一个比较简单的一维数组。（注：在每次对图进行遍历之前mark[]都会被清零）图的深度优先访问：从图中每个顶点V出发

6、，访问此顶点，然后依次从V的未访问邻接点出发深度优先遍历图，直至所有与V有通路的顶点被访问，否则选择另外未访问点作为起点，重复上述过程。图的广度优先遍历：从图中每个顶点V出发，访问此顶点，然后依次访问V的未访问邻接点，并保证先被访问的结点的邻接点先于后被访问的结点，直至所有与V有通路的顶点被访问，否则选择另外未访问点作为起点，重复上述过程。4.算法设计（1）首先，要定义头文件，在头文件中定义邻接点point、图的基本结点graph以及在广度优先搜索中会用到队列queue。具体如下：structpoint{intn;//邻接

7、点的序号point*next;//指向下一条弧节点的地址};structgraph{intdata;//表接点的数据structpoint*f;//结点的指针域，给出自该结点发出的第一弧节点的地址};structqueue{intelem[d];//队列的容量intfront;//front为首指针，指向第一个元素intrear;//rear为最后一个元素，指向队尾元素的下一个位置..}q;其次，在头文件中还需定义邻接表存储结构下图的抽象数据类型定义。（2）编写源文件，进行图的初始化，首先要输入顶点信息，初始化顶点表，在输

8、入点v的值时，同时构造v的邻接点。输入邻接点的序号，最后生成一个邻接点链表。子函数功能：1.voidcreatgraph(intm)//n表示节点的个数构造图的链表结构，在此函数中要输入图结点的值，邻接点的序号。2.voidprint(structgrapha[],intm)将图a的链表结构打印出来,m