1、 数据结构课程设计 设计说明书 图的遍历的实现 数学与计算机科学学院 2014 年 1 月 4 日 学 生 姓 名 学 号 班 级 网 络 1101 班 成 绩 指 导 教 师 课程设计任务书 20132014 学年第一学期 课程设计名称： 数据结构课程设计 课程设计题目： 图的遍历实现 完 成 期 限： 自 2013 年 12 月 23 日至 2014 年 1 月 4 日共 2 周 设计内容： 1. 任务说明 (1) 采用邻接表存储结构创建一个图； (2) 编程实现图的深度优先搜索（或广度优先搜索）遍历算法； (3) 输出遍历结果； (4) 给定具体数据调试程序。 2. 要求 1）问题分析和
2、任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？ 2）逻辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。 5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。 6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法 的时间、空间复杂性分析； 7）编写课程设计报告。 3. 参考资料 指导教师：申静 教研室负责人：余冬梅 课程设计评阅 评语： 指导教师签名： 年 月 日 摘摘 要要
3、 针对图问题中如何更好地实现图的遍历问题，以无向图为例，分别采用广度优先遍历和深度优先 遍历的算法实现对各节点的遍历，以 VC+为开发环境进行系统的设计和实现，其运行结果表明，系统 能很好地完成遍历后节点的输出，实现了遍历的目的，系统界面友好，可操作性强。 关键词：数据结构；存储结构；邻接矩阵 目目 录录 一 课题描述. 1 二 设计目的与任务 2 2.1 课程设计的目的 2 2.2 课程设计的任务 2 三 设计方案和实施 3 3.1 总体设计. 3 3.2 基本操作. 3 3.3 详细设计. 4 四 运行调试结果 6 五 结论与致谢 . 9 六 附录 11 1 一一 课题描述课题描述 数据结
4、构是一门专业基础课，它对学习者的要求很明确：学会分析、研究计算机加工的数据结构 的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算 法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习 者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的规范。 图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的， 图中任意两个数据元素之间都有可能相关。就本课程设计而言应用图论的知识讨论如何在计算机上实 现图的遍历的操作，主要解决图的遍历的几种方法的实现。 本设计采用目前最通用的程序设计语言之
5、一C 语言作为数据结构和算法的描述语言。 2 二二 设计目的与任务设计目的与任务 2.12.1 课程设计的目的课程设计的目的 进一步的了解图的遍历的问题， 图的 DFS,BFS 的递归和非递归算法的实现， 用无向图来实现图的 遍历。 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解 出指定的问题。 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水 平，并在此过程中培养严谨的科学态度和良好的工作作风。 提高综合运用所学的理论知识和方法独立分析和解决问
6、题的能力。 2.22.2 课程设计的任务课程设计的任务 1）任务说明 用 C/C+编写一个程序实现图的遍历的算法。 从键盘上输入一个图的基本信息（图用邻矩阵表示） 。图的 DFS,BFS 的递归和非递归算法的实 现;用有向图实现图的遍历；用无向图实现图的遍历；用邻接矩阵存储图；用邻接表存储图。 2）要求 1首先输入图的结点数； 2依次输入图的各条边（数据之间用空格隔开） ； 3输出的形式：按用户选择的遍历方法给出遍历顺序，各字符间用-分隔； 4程序所能达到的功能：能够按要求输出所要的结果。 3 三三 设计方案和实施设计方案和实施 3.13.1 总体设计总体设计 采用邻接矩阵作为图的存储结构。程序中主要用到以下抽象数据类型： 抽象数据类型的定义 typedef struct
