数学与计算机学院 课程设计说明书

课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 6014389

题 目: 图的遍历和生成树求解实现 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2012 年 12 月 09 日 完 成 时 间: 2012 年 12 月 26 日 课程设计成绩：

学习态度及平技术水平与实时成绩（30） 际能力（20） 创新（5） 说明书（计算书、图纸、总 分分析报告）撰写质量（45） （100） 指导教师签名： 年 月 日

图的遍历和生成树的求解 杨皓天

目 录

摘 要 ............................................................. 3 引 言 ............................................................. 4 1 需求分析 ........................................................ 5

1.1任务与分析 ........................................................................................................................ 5

1.2测试数据 ............................................................................................................................ 5

2 概要设计 ........................................................ 5

2.1 ADT描述 ............................................................................................................................ 5 2.2程序模块结构 .................................................................................................................... 7 软件结构设计： ....................................................................................................................... 7 2.3 各功能模块 ..................................................................................................................... 7

3 详细设计 ........................................................ 8

3.1结构体定义 ...................................................................................................................... 19 3.2 初始化 ............................................................................................................................. 22 3.3 插入操作（四号黑体） ................................................................................................. 22

4 调试分析 ....................................................... 22 5 用户使用说明 ................................................... 23 6 测试结果 ....................................................... 24 结 论 ........................................................... 26

图的遍历和生成树的求解 杨皓天

摘 要

《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：

? 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ? 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ? 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。

因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。

关键词：计算机；图；算法。