数据结构课设_c语言课设__图的遍历的演

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

1、算法与数据结构课程设计题目：图遍历的演示专业班级：09级网络姓名：李勋辉学号：09780011指导教师：成绩：_______________II目录摘要1前言1正文1问题描述1逻辑设计1详细设计6程序编码7程序的调试与测试10结果分析12使用说明13设计总结13参考文献14六、附件15II摘要（1）使用键盘的操作实行各种信息的输入（包括员图的结点、结点之间的连线）；并将相应结果输出等功能；（2）建立图，规定图的结点的个数少于十个，实现图的遍历（3）算法对于一些精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出

2、出错信息；（4）图的遍历的方法有广度优先遍历和深度优先遍历，按照设计任务书的要求实现图的两种遍历，并且输出结果（5）较高要求：实现图形化操作界面。前言该设计要求学生本学期对数据结构的学习为背景，设计出一个简单的能够实现图的遍历的系统。通过该题目的设计过程，可以加深理解图、图的遍历、图的广度优先遍历，图的深度优先遍历、图的创建等一系列算法的创建，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。正文问题描述该课题要求熟悉图的结构和其基本操作，掌握数组的建立和使用方法，学会利用递归和非递归的方法对其进行遍历。和树的遍历

3、类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。遍历常用两种方法：深度优先搜索遍历；广度优先搜索遍历逻辑设计1图的创建18该课题主要是以邻接矩阵的方式存储图，并以图形的方式输出图，所以在图的创建的过程中主要是输入图中各结点的关系，比方说1号结点和2号结点之间有联系，那么就得输入（1，2），但是总得设置一个结束的条件，在这里我就以（0，0）结束，这样比较好控制。而且初始化时得把所有邻接矩阵都初始化为0，那么当两个结点有关系时就可以设置为1.2图的输出图的输出主要是以printfgraph（）函数实现的。因为

4、输出图的特殊性，结点的位置如果随机的定义，工程量太大，而且涉及到数学方面的计算，所以我就把结点初定为6个。并且已经定好结点的位置，但是结点与结点之间的联系却没有定好，是按用户输入的情况进行连接的。3图的深度优先遍历当用户需要深度优先遍历时，由于公共变量visited里的值可能会受到其他的变化，所以一开始就把所有结点都定义为未访问，然后当其访问到哪个结点时再把相应的结点的visited设置为1，即已经访问。再用visitvex函数显示该结点已访问。再查找该结点的下一个结点，实行递归。直到所有的结点都已经访问完。4图的广度优先遍历当用户需要广度优先遍历时，首先得初始化一个

5、队列，并初始化其为一个空队列。而且由于公共变量visited里的值可能会受到其他的变化，所以一开始就把所有结点都定义为未访问，然后当其访问到哪个结点时再把相应的结点的visited设置为1，即已经访问。再用visitvex函数显示该结点已访问。然后再把该结点入队。只要队不为空。就把队里的结点出队。并查找下一个结点，直到所有的结点都已经访问完5输入输出的要求5．1输入的要求本来可以手动输入要遍历的总结点数，但是由于结点位置如果以这种方式的话就无法确定，即使有一定的规律，而边的确定也不好把握，所以本设计中已经定好了结点的相应位置，我们只需要输入结点之间是不是有边连接就可行

6、，并输入那条边所连接的起始点和终点。5．2输出的要求18因为本课题要求的是演示图的遍历过程，所以我们必须在构建好邻接矩阵后要把整个图给显示出来。而且重点要演示图的遍历，所以在图中要演示这个过程，在本设计中我是遍历一个结点要求再按一个键再遍历下一个结点，这样也不会因为遍历过程太快根本就看不到这个过程，而且我是用填充图形的方式显示这个结点，这样比较打眼。当使用另外一种遍历方式时，我就把填充图形函数的方式的颜色更改一下。这样就可以完成整个设计的需要。5.3设计方案5.3、1总体设计流程1图的初始化定义图并初始化图2.建立图的邻接表3.图的遍历1.图的深度优先搜索2.图的广度

7、优先搜索5.3、2图的遍历的模块化1.图的存储结构；2.图的输入；3.BFS和DFS编码；18概要设计主函数main()2.1主函数功能模块图：Printfgraph(g)输出整个图Creatgraph(g,n)初始化图，并使之存在邻接矩阵里Printfvertex（）输出结点的位置输入menu调用dfstraverse(g)调用BESTraverse(g)退出重新输入图2.1.1主函数功能模块图18主流程图结束图的遍历的演示输出遍历结果输出遍历结果DFSGrahp()：深度优先遍历BFSGrahp()：广度优先遍历输入结点名称和结点直接的接连关系按