图的遍历的实现课程设计

武汉理工大学《数据结构》课程设计说明书1学号：课程设计题目图的遍历的实现学院计算机科学与技术学院专业软件工程班级姓名指导教师2013年12月23日武汉理工大学《数据结构》课程设计说明书2课程设计任务书学生姓名：专业班级：指导教师：工作单位：计算机科学与技术学院题目:图的遍历的实现初始条件：理论：学习了《数据结构》课程，掌握了一种计算机高级语言。实践：计算机技术系实验中心提供计算机及软件开发环境。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：1)先任意创建一个图；2)图的DFS,BFS的递归或非递归算法的实现3)要求用有向图或无向图分别实现4)要求用邻接矩阵、邻接表多种结构存储实现2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构设计、算法设计、有关技术的讨论、设计体会等；（4）结束语；（5）参考文献。时间安排：2013年12月16日--25日12月19日查阅资料12月20日系统设计12月21日-22日编程并上机调试12月23日撰写报告12月24日验收程序，提交设计报告书指导教师签名：2013年12月14日系主任（或责任教师）签名：年月日武汉理工大学《数据结构》课程设计说明书3图的遍历的实现摘要本课程设计主要目的在于更深一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用有向图和无向图分别实现图的遍历，广度优先遍历和深度优先遍历的实现，用邻接矩阵和邻接表等多种结构存储存储图。在课程设计中，程序设计设计语言采用VisualC，程序运行平台为Windows98/2000/XP。在程序设计中我主要是解决的是给出一个图如何用多种方法完成图的遍历的问题，也包括如何创建一个图，深度优先遍历和广度优先遍历一个图，递归和非递归的方法实现图的遍历。程序最终通过调试运行，初步实现了设计目标。关键词程序设计；数据结构；有向图；无向图；存储结构；邻接矩阵；递归算法武汉理工大学《数据结构》课程设计说明书4AbstractThepurposeofthiscoursedesignistofurtherunderstandtheproblemofgraphtraversal,figureDFSandBFSrecursiveandnon-recursivealgorithmsofimplementation,usingdirectedgraphandundirectedgraph,graphtraversalisimplemented,breadth-firsttraversalandtherealizationofthedepth-firsttraversal,usingadjacencymatrixandadjacencylistandsoonthemanykindsofstructuretostore.Incurriculumdesign,usingVisualCprogrammingdesignlanguage,applicationplatformforWindowsXP/98/2000.InprogrammingisgivenafigureImainlysolvehowtouseavarietyofmethodstocompletegraphtraversalproblems,includinghowtocreateafigure,depth-firsttraversalandbreadth-firsttraversalafigure,themethodofrecursiveandnon-recursivetraversalgraph.Programdebuggingandrunning,ultimatelythroughpreliminarydesigngoalisrealized.Keywordsprogramdesign;Datastructure;Directedgraph;Undirectedgraph.Storagestructure;Adjacencymatrix武汉理工大学《数据结构》课程设计说明书5目录1.引言..........................................................62.需求分析.......................................................72.1原理......................................................72.2要求......................................................72.3运行环境..................................................72.4开发工具..................................................73.数据结构分析...................................................83.1邻接表的结构：............................................83.2图的深度优先访问：........................................83.3图的广度优先遍历：........................................84.算法设计......................................................94.1结构体定义及函数的声明....................................94.2主要模块的算法描述.......................................104.3函数调用图...............................................115.程序实现及测试................................................135.1创建工程并建立文件.......................................136.心得体会.....................................................147.结束语........................................................15参考文献........................................................16附源程序清单和运行结果........................................17运行结果（截图）................................................22武汉理工大学《数据结构》课程设计说明书6本科生课程设计成绩评定表........................................241.引言数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。在软件工程专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。图是一种非常重要的数据结构，在《数据结构》中也占着相当大的比重。这个学期的数据结构课程中，我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构是一种顺序存储与链式存储相结合的存储方法。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。武汉理工大学《数据结构》课程设计说明书72.需求分析2.1原理当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点，而这些操作都需要一图的深度优先及广度优先遍历为基础。本系统将构建一个图，图的结点存储的是int型数据。运行本系统可对该图进行链式结构输出、深度优先及广度优先遍历。控制方法如下：表2-1控制键的功能2.2要求(1)先任意创建一个图；(2)图的DFS,BFS的递归或非递归算法的实现(3)要求用有向图或无向图分别实现(4)要求用邻接矩阵、邻接表多种结构存储实现2.3运行环境(1)WINDOWS7系统(2)C++编译环境2.4开发工具C++语言控制键123功能广度优先遍历深度优先遍历退出程序武汉理工大学《数据结构》课程设计说明书83.数据结构分析本课程设计是针对于图的，程序中采用邻接表进行数据存储。在计算机科学中，邻接表描述一种紧密相关的数据结构，用于表征图。在邻接表的表示中，对于图中的每个顶点，我们将保存所有其它与之相连的顶点（即“邻接表”）。邻接表是一种顺序存储与链式存储相结合的存储方法，该存储方式在图比较稀疏是相对于图的邻接矩阵存储有明显优势。设计实现了图的邻接表结构输出、深度有新遍历和广度优先遍历操作的实现。3.1邻接表的结构：（1）、头结点结构Firstarc：结点的指针域（2）、邻接点的结构Adjvex：邻接点的数据域；Nextarc：邻接点的指针域，指向下一个邻接点；在该程序中，除了邻接表结构以外，还有到了一个mark[]数组，它是用来标记结点Vi是否被访问。若Vi被访问，则mark[i]=1，否则为0；它是一个比较简单的一维数组。（注：在每次对图进行遍历之前mark[]都会被清零）3.2图的深度优先访问：从图中每个顶点V出发，访问此顶点，然后依次从V的未访问邻接点出发深度优先遍历图，直至所有与V有通路的顶点被访问，否则选择另外未访问点作为起点，重复上述过程。3.3图的广度优先遍历：从图中每个顶点V出发，访问此顶点，然后依次访问V的未访问邻接datafirstarcnextarcadjvex武汉理工大学《数据结构》课程设计说明书9点，并保证先被访问的结点的邻接点先于后被访问的结点，直至所有与V有通路的顶点被访问，否则选择另外未访问点作为起点，重复上述过程。4.算法设计4.1结构体定义及函数的声明（1）首先，要定义头文件，在头文件中定义邻接点point、图的基本结点graph以及在广度优先搜索中会用到队列queue。具体如下：structpoint{intn;//邻接点的序号point*next;//指向下一条弧节点的地址};structgraph{intdata;//表接点的数据structpoint*f;//结点的指针域，给出自该结点发出的第一弧节点的地址};structqueue{intelem[d];//队列的容量intfront;//front为首指针，指向第一个元素intrear;//rear为最后一个元素，指向队尾元素的下一个位置}q;其次，在头文件中还需定义邻接表存储结构下图的抽象数据类型定义。（2）编写源文件