课程设计-图的遍历

1目录一、课题的主要功能............................................21.1设计内容.................................................21.2对课程设计功能的需求分析.................................2二、课题的功能模块的划分.......................................22.1模块划分.................................................22.2系统的概要设计...........................................3三、主要功能的实现............................................43.1算法思想.................................................41.图的邻接矩阵的建立.......................................42.图的遍历的实现...........................................43.2数据结构.................................................43.3主函数流程图.............................................53.4深度优先遍历流程图.......................................63.5深度优先遍历递归.........................................73.6深度优先遍历流程图.......................................93.7广度优先遍历递归流程图..................................10四、程序调试.................................................114.1程序的调试分析..........................................114.2程序的测试结果..........................................11五、总结.....................................................15六、附件.....................................................166.1源程序...............................................................................................................................................162一、课题的主要功能1.1设计内容演示图的深度优先,广度优先遍历过程，并输出原图结构及遍历结果。要求图的结点数不能少于6个。可以由系统随机生成图，也可以由用户手动输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。1.2对课程设计功能的需求分析图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最好的。软件设计必须符合我们使用实际情况的需要。根据要求，图的遍历主要功能如下：1.用户可以随时建立一个有向图或无向图；2.用户可以根据自己的需要，对图进行深度遍历或广度遍历；3.用户可以根据自己的需要对图进行修改；4.在整个程序中,用户可以不断的按照不同的方式对图进行遍历,若不继续,用户也可以随时跳出程序,同时,如果用户输入的序号错误,程序会提示用户重新输入序号；二、课题的功能模块的划分2.1模块划分1.队列的初始化、进队、出队、队列空、队列满的函数voidInitQueue(CirQueue*Q)//初始化队列intQueueEmpty(CirQueue*Q)//队列是否为空intQueueFull(CirQueue*Q)//队列满VoidEnQueue(CirQueue*Q,intx)//将队员进队intDeQueue(CirQueue*Q)//将队员出队2.创建图的函数voidCreateMGraph(MGraph*G)//根据用户需要创建一个图3.图的深度优先遍历递归voidDFSM(MGraph*G,inti)/*含有输出已访问的顶点的语句*/34.图的广度优先遍历递归voidBFSM(MGraph*G,intk)/*含有输出已访问的顶点的语句*/5.深度优先遍历voidDFSTraverseM(MGraph*G)/*调用DFSM函数*/6.广度优先遍历voidBFSTraverseM(MGraph*G)/*调用BFSM函数*/7.主函数main()/*包含一些调用和控制语句*/2.2系统的概要设计开始信息录入菜单选择深度优先修改信息广度优先退出程序4三、主要功能的实现3.1算法思想本课题所采用的是邻接矩阵的方式存储图，实现图的深度、广度两种遍历，并将每种遍历结果输出来。1.图的邻接矩阵的建立对任意给定的图（顶点数和边数自定），根据邻接矩阵的存储结构建立图的邻接距阵。2.图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现，这里我所采用的是递归算法。3.2数据结构#defineMax10#defineFALSE0#defineTRUE1#defineErrorprintf#defineQueueSize30typedefstruct{charvexs[Max];intedges[Max][Max];intn,e;5}MGraph;intvisited[Max];typedefstruct{intfront;intrear;intcount;intdata[QueueSize];}CirQueue;3.3主函数流程图登陆开始6假01233.4深度优先遍历流程图CreateMGraph(G);Ch1=’y’Ch1=’y’真Ch2Ch1=’n’CreateMGraph(G)DFSTraverseM(G)BFSTraverseM(G)BFSTraverseM(G)DFSTraverseM(G)DFSTraverseM(G)DFSTraverseM(G)DFSTraverseM(G)DFSTraverseM(G)DFSTraverseM(G)BFSTraverseM(G)Break结束程序DFSTraverseM(MGraph*G)7真非零零3.5深度优先遍历递归i=0iG-nvisited[i]=FALSEi++i=0!visited[i]DFSM(G,i)iG-ni++结束程序8真DFSM(MGraph*G,inti)visited[i]=TRUEjG-nj=0G-edges[i][j]==1&&!visited[j]DFSM(G,i)J++结束程序输出G-vexs[i]93.6深度优先遍历流程图真非零零BFSTraverseM(MGraph*G)i=0iG-nvisited[i]=FALSEi++i=0!visited[i]BFS(G,i)iG-ni++结束程序103.7广度优先遍历递归流程图真BFSM(MGraph*G,intk)InitQueue(&Q)输出G-vexs[k]visited[i]=TRUEEnQueue(&Q,k)!QueueEmpty(&Q)i=DeQueue(&Q)j=0!visited[i]DFSM(G,i)jG-ni++结束程序11四、程序调试4.1程序的调试分析在调试过程中，程序中出现了许多的错误，有错误的调用,一些变量没有定义等等。不断的对程序进行调试以得到最好的结果，程序中特别要注意的是类的对象作为作为参数时要注意如何去调用它，使程序有一个令人满意的结果，具体的调试是在上机过程中进行的，在编写程序的过程中主要有如下错误：1.在编写程序的过程出现了一些函数名、变量的大小写不统一的错误，导致程序在运行的过程中出现函数名、变量没有被定义等问题；2.在编写程序的过程中数组的大小写没有被确定；3.在编写程序的过程中一些变量没有被定义，导致程序出错；4.数组visited[Max]应定义为全局变量，若不是则会出错；5.函数的返回类型要确定，是void还是其他类型要十分注意；6.在编程的过程中，函数里一些控制语句的嵌套使用，括号要引起注意，4.2程序的测试结果初始进入程序时，程序提示按格式输入图的顶点个数和边数。12输入顶点数和边数后，程序提示输入顶点的序号，为各顶点依次进行编号。将各顶点进行编号后，程序提示按格式输入边的顶点序号。13按格式依次输入边的顶点序号后，按enter键程序会出现“选择菜单”，用户根据需要进行选择。用户选择2进入深度优先搜索，并输出深度优先遍历后的序列，再次输出菜单栏，进行选择。14用户再次选择3进入广度优先搜索，并输出广度优先遍历后的序列，再次输出菜单栏，进行选择。用户选择1后进入更改数据，重新创建一个图。15用户选择0，则退出程序。五、总结通过这次数据结构课程设计实践，我学到了很多东西。本次课程设计对我来说正是一个提高自己能力的机会，我好好的抓住机会，努力做好每一步，完善每一步。自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：1.必须牢固掌握基础知识。由于C语言是大一所学知识，有所遗忘，且未掌握好上学期所学的《数据结构》这门课，所以在实践之初感到棘手。不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉，这时才逐渐有了思路。所以今后一定要牢固掌握好专业基础知识。2.必须培养严谨的态度。自己在编程时经常因为一些小错误而导致出现问题，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的态度。我想这不仅是对于程序设计，做任何事都应如此。3.这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思16想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。在实践过程中，我遇到了许多困难，但都一一克服了。最终我圆满的完成此次课程设计，学到了很多东西。同时，程序还存在着一些缺陷，我会继续努力思考，完善程序，做到最好。总的来说，本次课程设计，不仅我的知识面有所提高，另外我的综合素质也有所提高，这次课程设计为我以后更好的学习和使用c语言打下了基础。六、附件6.1源程序#includestdio.h#includestdlib.h#defineMax10#defineFALSE0#defineTRUE1#defineErrorprintf#defineQueueSize30typedefstruct{charvexs[Max];intedges[Max][Max];intn,e;}MGraph;/*以邻接矩阵作为图的存储结构*/intvisited[Max];/*将visited[Max]定义为全局变量并分配最大空间*/typedefstruct{intfront;17intrear;intcount;intdata[QueueSize];}CirQueue;/*定义队列的数据结构*///初始化队列voidInitQueue(CirQueue*Q){Q-front=Q-rear=0;Q-co