数据结构课程设计49730new

《数据结构课程设计49730new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计说明书课程名称：数据结构与算法设计题目：图的遍历和生成树的求解院系：计算机科学与信息工程学院学生姓名：学号：专业班级：计算机科学与技术(嵌入式方向)11-1指导教师：2013年6月1课程设计任务书设计题目图的遍历和生成树的求解学生姓名韩银奇所在院系计算机科学与信息工程系专业、年级、班计算机科学与技术（嵌入式方向）11-1设计要求：1)先任意创建一个无向图；2)能够输出显示生成的无向图的顶点和边的信息3)输出该图的深度和广度遍历序列4)通过普利姆算法和克鲁斯卡尔算法求最小生成树，并输出最小生成树的求解构造过程学生应完成的工作：(1)根据课

2、程设计要求，分析思路并构建模型，划分子模块、完善其功能；(2)根据各模块的功能设计并编写程序段、连接各程序段使之形成一个有机的整体；(3)调试、运行程序进而得到正确的结果；(4)根据实验设计运行过程，写出实验论文并总结实验教训。参考文献阅读：(1)C语言程序设计（潭浩强第二版，清华大学出版社）；(2)数据结构（严蔚敏、吴伟民C语言版，清华大学出版社）；(3)数据结构实验教程（高晓兵等，清华大学出版社）；(4)钱能.C++程序设计教程第二版.北京：清华大学出版社.2005；（5）李兰，刘天印.C++程序设计实验指导.北京：北京大学出版社.2006

3、。工作计划：(1)第一周的第一天：小组布置设计题目；说明进度安排。(2)第一周的第二天：小组审题，查阅资料，进行设计前的必要资料准备。(3)第一周的第三天、第四天、第五天：程序编写、上机调试(4)第二周的第一天至第三天：上机调试程序、结果分析。(5)第二周的第四天：撰写设计报告。(6)第二周的第五天：设计答辩。任务下达日期：2013年6月14日任务完成日期：2013年6月28日指导教师（签名）：学生（签名）：图的遍历和最小生成树的求解摘要：图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E构成，图存在两种遍历方式，深度优先遍历和

4、广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索土。直至图中所有顶点都被访问到。在计算机中，图的信息有多种存储方法，由于图的结构复杂，使用广泛，一般应根据实际的应用，选择适合的表示方法。常用的图的存储结构有邻接矩阵、邻接链表等。关键词：图的遍历；邻接矩阵；邻接链表目录1.设计

5、背景11.1图形结构的广泛应用11.2图的需求11.3最小生成树的需求与应用12.设计方案22.1总体设计流程22.2软件结构设计：22.3函数程序流程图33.方案实施43.1图的遍历邻接矩阵的实现43.2图的遍历邻接表的存储44.结果与结论44.1源程序代码概要44.2主函数和其他函数的伪码算法54.3程序运行结果114.4课程设计总结135.收获与致谢136.参考文献147.附件141.设计背景1.1图形结构的广泛应用图有若干各节点和若干条边构成的结构，是一类重要的非线性数据结构。图形结构在客观世界中广泛存在，特别是近年来的迅速发展，已渗入

6、到诸如语言学、逻辑学、物理、化学、电讯工程及数学的其他分支中，图在计算机领域中也得到广泛应用，如在编译程序中，可以用图来表示源程序的语法结构。又如在数据库系统中，图形结构也是信息的重要组织之一。1.2图的需求图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之

7、间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中任意创建一个无环图，实现图的DFS,BFS算法、最小生成树的普利姆算法和克鲁斯卡尔算法。1.3最小生成树的需求与应用对于n个顶点的连通网可以构建许多不同的生成树。寻找最小生成树是连通网的造价最少。假设要在n个城市之间建立通讯联络网，在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价n个城市之间，最多可能设置n（n-1）2条线路。用连通网表示各城市及其间可能设置的通信路线，网的顶点表城市，边

8、表城市间线路，赋予边上的权值表相应的代价。通过最小生成树实现造价最小。142.设计方案2.1总体设计流程1、先任意创建一个无向图。2、根据所建无向图的