图的遍历实现课程设计 数据结构 程序 图

1、图的遍历实现课程设计-数据结图-程序-构数据结构课程设计设计说明图的遍历的实现学生姓名英茜1118064033学号级班网络1101班绩成教导指师静申数学与计算机科学学院2014年1月4日课程设计任务书2014学年第一学期2013课程设数据结构课程设计计名称：课程设图的遍历实现计题目：自2013年12月23日至2014完成年1月4期限：日共2周设计内容：1.任务说明(1)采用邻接表存储结构创建一个图；(2)编程实现图的深度优先搜索(或广度优先搜索)遍历算法；(3)输出遍历结果；(4)给定具体数据调试程序。2.要求问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？逻

2、辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调指导教师签名用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告。3.参考资料指导教师：申静教研室负责人：余冬梅课程设计评阅评语2摘要针对图问题中如何更好地实现图的遍历问题，以无向图为例，分别采用广度优先遍历和深度优先遍历的算法实现对各节点的遍历，以VC+为开发

3、环境进行系统的设计和实现，其运行结果表明，系统能很好地完成遍历后节点的输出，实现了遍历的目的，系统界面友好，可操作性强。关键词：数据结构；存储结构；邻接矩阵目录课题描述1设计目的与任务2II2.1课程设计的目的2I2.2课程设计的任务设计方案和实施4II3.1总体设计4I3.2基本操作4I3.3详细设计6I四运行调试结果9I五结论与致谢9附录11课题描述数据结构是一门专业基础课，它对学习者的要求很明确：学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训

4、练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确易读，符合软件工程的规范。图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。就本课程设计而言应用图论的知识讨论如何在计算机上实现图的遍历的操作，主要解决图的遍历的几种方法的实现。本设计采用目前最通用的程序设计语言之一一c语言作为数据结构和算法的描述语言。1设计目的与任务课程设计的目的进一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用无向图来实现图的遍历。初步掌握软件开发过程的问题分析、系统设计、程序编码、测2试等基本方法和技能。训练学生灵活

5、应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题。训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风。提高综合运用所学的理论知识和方法独立分析和解决问题的能力。21.）2课程任设务计的说任务明用C/C+编写一个程序实现图的遍历的算法。从键盘上输入一个图的基本信息（图用邻矩阵表示）。用有向图实现图的遍历；;DFS,BFS的递归用无向图实现图的遍历；用邻接和非递归算法的实现图的矩阵存储图；用邻接表存储图。2）要求1首先输入图的结点数；2依次输入图的各条边（数据之间用空格隔开）；3

6、输出的形式：按用户选择的遍历方法给出遍历顺序，各字符间用-分隔；4程序所能达到的功能：能够按要求输出所要的结果。设计方案和实施总体设计采用邻接矩阵作为图的存储结构。程序中主要用到以下抽象数据类型：抽象数据类型的定义typedefstructchar*vexs;/顶点向量intarcsMAX_VEXMAX_VEX;/邻接矩阵intvexnum,arcnum;/图的当前顶点数和弧数Graph;基本操作CreateUDN(Graph&G)操作结果：用邻接矩阵创建带权无向网图。DFS(GraphG,intk)操作结果：对已存在的图进行深度优先遍历BFS(GraphG)操作结果：对已存在的图进行广度优先

7、遍历choose(GraphG)操作结果：对将要实现的操作步骤进行选择4程序包含两个模块主程序模块，其中主函数为intmain输入信息；根据输入要求进行选择操作和输出；输出结果；选择操作模块实现具体选择的对应操作及输出操作。两模块之间关系如下图3.1所示5主函数模块选择操作模块递归调用图3.1模块关系图详细设计程序流程图如图3.2所示主函创建无向网函数据输入选择操作模块1.深度优先遍历2.广度优先遍历数据输出数据输出结束6图3.2程序流程图函数设计程序设计中主要包括下列函数用邻接矩阵创建一个图：voidCreateUDN(Graph&G)用邻接矩阵创建一个带权无向网图;输入顶点数和弧数;输入各

8、个顶点及各条弧;递归方法实现图的遍历：voidDFS(GraphG,intk)用递归的方法访问图中的结点;对图进行深度优先遍历;非递归方法实现图的遍历：voidBFS(GraphG)用队列辅助访问图中的结点;对图进行广度优先遍历;选择输出需要的遍历方法：7voidchoose（GraphG）给出程序运行的选项;对相应的输入选项调用相应的函数以执行操作；8运行调试结果例：遍历如下无向图（图4.1）（a,b,c,d,e分别表示V1V2V3V4V5五个顶点）4.4图广度优先结果11以图4.1为例步骤一：运行程序，按提示首先输入顶点数和弧数图步4.2骤输入顶二点数和：弧数输入顶点和弧（1）输入顶点图4

9、.3输入各2顶）点输入弧10步骤三：选择便利方式以及选择后输入各条弧4.3图结果1操作显示广度优先编历结果选择选2操作显示深度优先遍历图4.4深度优先遍历结果12结论与致谢在程序设计中我主要是解决的是给出一个图如何用多种方法完成图的遍历的问题，也包括如何创建一个图，深度优先遍历和广度优先遍历一个图，递归和非递归的方法实现图的遍历。程序最终通过调试运行，初步实现了设计目标。图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。用邻接矩阵作为图的数据存储结构很好地解决了图的结构难点，借助于邻接矩阵容易判定任意两个顶点之间是否有边（

10、或弧）相连，并容易求得各个顶点的度。该程序通俗易懂且实用性强并且该程序清单详细具体、全面、具有很强六附录的可读性；系统整体上比较完美，可以从键盘获取输入元素，并且可以根据用户输入进行选择性地输出；整体输出画面效果整洁、大方。这次课程设计也让我充分认识到数据结构这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。最后，我还要特别感谢我们的辅导老师申静老师，在她的精心辅导和帮助下，我的设计才得以顺利完成。对她为我们的设计所提出的宝贵意见表示忠心的感谢！13参考文献1谭浩强.C程序设计第三版.北京:清华大学出版社.2罗宇等.数据结构M.北京邮

11、电大学出版社.3严藯敏.数据结构C语言版.北京:清华大学出版社.4杨路明.C语言程序设计教程.北京邮电大学出版社.5徐孝凯.数据结构课程实验.清华大学出版社.14 源程序代码/程序功能：采用递归和非递归算法，有向图和无向图，邻接矩阵和邻接表等多种结构存储实现图的遍历。/程序作者：英茜/最后修改日期：2014-1-3#includestdio.h#includestdlib.h#defineINFINITY32767#defineMAX_VEX20/最大顶点个数#defineQUEUE_SIZE(MAX_VEX+1)/队列长度bool*visited;intz=1;结构/访问标志数组/图的邻接矩

12、阵存储typedefstructchar*vexs;/顶点向量intarcsMAX_VEXMAX_VEX;/邻接矩阵intvexnum,arcnum;/图的当前顶点数和弧数Graph;classQueue/队列类public:voidInitQueue()base=(int*)malloc(QUEUE_SIZE*sizeof(int);front=rear=0;voidEnQueue(inte)baserear=e;rear=(rear+1)%QUEUE_SIZE;voidDeQueue(int&e)e=basefront;front=(front+1)%QUEUE_SIZE;int*base

13、;intfront;intrear;intLocate(GraphG,charc)/图G中查找元素c的位置for(inti=0;iG.vexnum;i+)if(G.vexsi=c)returni;return-1;voidCreateUDN(Graph&G)/创建无向网inti,j,w,s1,s2;chara,b,c,temp;牰湩晴尨输入顶点数和弧数(顶点数和弧数之间以空格隔开):);scanf(%d%d,&G.vexnum,&G.arcnum);17temp=getchar();/接收回车G.vexs=(char*)malloc(G.vexnum*sizeof(char);/分配顶点数目牰

14、湩晴尨输入d个顶点.n,G.vexnum);for(i=0;iG.vexnum;i+)/初始化顶点scanf(%c,&G.vexsi);temp=getchar();/接收回车for(i=0;iG.vexnum;i+)/初始化邻接矩阵for(j=0;jG.vexnum;j+)G.arcsij=INFINITY;牰湩晴尨输入d条弧.n,G.arcnum);for(i=0;i=0&kG.vexnum)/k合理for(inti=0;i=0&i=0&19jG.vexnum)/i,j合理for(intk=j+1;kG.vexnum;k+)if(G.arcsik!=INFINITY)returnk;ret

15、urn-1;/深度优先遍历voidDFS(GraphG,intk)inti;DFS执第一次行/if(k=-1)时-1,k为for(i=0;i%c,G.vexsk);+z;/访问第k个顶点if(z-1)%G.vexnum=0)z=1;for(i=FirstVex(G,k);i=0;i=NextVex(G,k,i)if(!visitedi)DFS(G,i);对k的尚未访问的邻接顶点i递归调用DFS/广度优先遍历voidBFS(GraphG)intk;QueueQ;/辅助队列QQ.InitQueue();for(inti=0;i=0;w=NextVex(G,k,w)if(!visitedw)w为k的

16、尚未访问的邻接顶点visitedw=true;printf(-%c,G.vexsw);Q.EnQueue(w);printf(请继续选择:n);voidchoose(GraphG)/对输入选项调用相应的函数执行操作inti,m;visited=(bool*)malloc(G.vexnum*sizeof(bool);22scanf(%d,&m);switch(m)case1:牰湩晴尨广度优先遍历:);for(i=0;iG.vexnum;i+)visitedi=false;BFS(G);choose(G);printf();break;case2:牰湩晴尨深度优先遍历:);for(i=0;iG.vexnum;i+)visitedi=fal