数据结构课程设计__图的遍历

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

1、—、一一、前吕1.1课程设计的目的与意义21.2对课程设计功能的需求分析2二、算法思想3三、数据结构设计3四、算法的概要设计4.1、有关队列的一系列函数44.2、创建图的函数44.3、图的深度优先遍历递归44.4、图的广度优先遍历递归44.5、深度优先遍历44.6、广度优先遍历44.7、主函数4五、算法的详细设计5.1、系统功能模块图45.2、各模块流程图7六、程序的调试分析以及测试结果6.1、程序的调试分析86.2、程序的测试结果9七、课程设计心得体会12八、参考文献13九、附录13一、前言1.1课程设计的H的与意义上学期我们对《数据结构》这门课程进

2、行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求我们掌握《数据结构》中的各方面知识，还要求我们具备一定的c语言基础和编程能力。通过实践我们掌握《数据结构》中的知识。对于《图的遍历》这一课题來说,所要求我们掌握的数据结构知识主耍有：图的存储结构、队列的基木运算实现、图的深度优先遍历算法实现、图的广度优先遍历算法实现。对于我们学生來讲，此次课程设计是为了让我们训练自己的实际设计能力,通过设计实践，去真正获得此项Fl管理和团队协作等方面的基本训练和T作经验。通过课程

3、设计的一系列训练，我们能提高如何综合运用所学知识解决实际问题的能力，以及获得此项H管理和团队协作等等众多方面的具体经验，增强对相关课程具体内容的理解和掌握能力，培养对整体课程知识综合运用和融会贯通能力。1・2对课程设计功能的需求分析图的遍历并不需要是一个过于复朵的工作环境，一般来说：最合适的才是最好的。软件设计必须符合我们使用实际情况的需耍。根据要求，图的遍历主要功能如下：1、用户可以随时建立一个有向图或无向图；2、用户可以根据自己的需要，对图进行深度遍历或广度遍历；3、用户可以根据自己的需要对图进行修改；4、在整个程序中，用户可以不断的按照不同的方式

4、对图进行遍历，若不继续,用户也可以随时跳出程序，同时，如果用户输入的序号错误，程序会提示用户重新输入序号；二、算法思想本课题本人所采用的是邻接矩阵的方式存储图，，实现图的深度、广度两种遍历，并将每种遍历结果输出来。2.1.1图的邻接矩阵的建立对任意给定的图（顶点数和边数自定），‘根据邻接矩阵的存储结构建立图的邻接矩阵。2.1.2图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是

5、否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现，这里我所采用的是递归算法。三.数据结构设计#defineMax10#defineF7LSE0#defineTRUE1#defineErrorprintf#defineQueueSze30typedefstruct{charvexs[Max]:intedges[Max][Max]:intn,e;JMGraph;intvisited[Max];typedefstructintfront;intrear;intcount;intdata[QueueSze];}QrQueue;四、算法的概

6、要设计4.1、队列的初始化、进队、出队、队列宇、队列满的函数；voidInitQueue(QrQueue*Q)〃初始化队列intQueueEmpty(QrQueue*Q)〃队列是否为空intQueueFull(CirQueue*Q)〃队列满VoidEnQueue(CirQueue*Q,intx)〃将队员进队intDeQueue(OrQueue*Q)〃将队员出队4.2、创建图的函数voidCreateMGraph(MGr即h*G)〃根据用户需要创建一个图4.3、图的深度优先遍历递归voidDFSM(MGraph*G,inti)/*含有输出已访问的顶点的语

7、句*/4.4、图的广度优先遍历递归voidBFSM(MGraph*G,intk)/*含有输出已访问的顶点的语句*/4.5、深度优先遍历voidDFSTraverseM(MGraph*G)/*调用DFSM函数*/4.6、广度优先遍历voidBFSTraverseM(MGraph*G)/*调用BFSM函数*/4.7、主函数main()厂包含一些调用和控制语句*/五、算法的详细设计丿度优先遍历图进入菜单选择▼修改图的信息V度优先遍历图__远退出程序图一、系统功能模块图图二、主函数流程图DFSTraverseM(MGraph*图三、深度优先遍历流程图BFSTr

8、averseM(MGraph*G)图四、广度优先遍历流程图六、程序的调试分析以及测试结果6.1