1、 数据结构 课程设计报告 设计题目： 图的邻接矩阵存储结构 院 系 计算机学院 年 级 x 级 学 生 xxxx 学 号 xxxxxxxxxx 指导教师 xxxxxxxxx 起止时间 10-6/10-10 2013 年 10 月 10 日 无向图的邻接矩阵存储结构 2 / 20 目目 录录 1 需求分析 4 2 概要设计 4 2.1 ADT 描述 4 2.2 程序模块结构 5 2.3 各功能模块 . 6 3 详细设计 7 3.1 类的定义 . 7 3.2 初始化 8 3.3 图的构建操作 . 8 3.4 输出操作 9 3.5 get 操作 . 9 3.6 插入操作 10 3.7 删除操作 .1
2、00 3.8 求顶点的度操作 . 111 3.9 深度遍历作.11 3.10 判断连通操作 12 3.11 主函数 13 4 调试分析 16 4.1 调试问题 . 16 4.2 算法时间复杂度 16 5 用户手册 16 5.1 主界面 . 16 5.2 创建图 17 5.3 插入节点 . 17 5.4 深度优先遍历 . 17 5.5 求各顶点的度 . 18 5.6 输出图 18 5.7 判断是否连通 . 19 5.8 求边的权值 . 19 5.9 插入边 19 5.10 删除边 20 结 论 . 20 参考文 献20 无向图的邻接矩阵存储结构 3 / 20 摘摘 要要 随着计算机的普及，涉及计
3、算机相关的科目也越来越普遍，其中数据 结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算 机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构 的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书是对 “无向图的邻接矩阵存储结构”课程设计的说明。 首先是对需求分析的简要阐述， 说明系统要完成的任务和相应的分析， 并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程 序的流程以及各程序模块之间的层次关系，以及 ADT 描述。然后是详细设 计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的 功能及代码实现。再次是对系统的调试分析说明，以及
4、遇到的问题和解决 问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的 分析，最后是对本次课程设计的结论。 关键词：关键词：网络化；计算机；对策；图；储存。 无向图的邻接矩阵存储结构 4 / 20 1 需求分析需求分析 随着计算机的普及,信息的存储逐渐和我们的日常生活变得密切起来，而数据的 存储方式也多种多样，比如树、链表、数组、图等等。 为了充分体现图的矩阵储存结构的优势与功能，要求本系统应达到以下要求： 1. 图是无向带权图 2. 能从键盘上输入各条边和边上的权值； 3. 构造图的邻接矩阵和顶点集。 4. 输出图的各顶点和邻接矩阵 5. 插入一条边 6. 删除一条边 7. 求出
5、各顶点的度 8. 判断该图是否是连通图，若是，返回 1；否则返回 0. 9. 使用深度遍历算法，输出遍历序列。 2 概要概要设计设计 2.1 ADT 描述描述 ADT Glist VR=图的顶点和边 VR= | v,wV, 表示顶点 v 和 w 间的边； 基本操作： 初始化空图； 输入建立图； 深度优先遍历图； 确定图中的顶点数目； 确定图中边的数目； 在图中插入一个顶点； 无向图的邻接矩阵存储结构 5 / 20 在图中插入一条边； 删除图中一个顶点 删除图中的一条边； 求顶点的度； 求最小生成树； ADT Graph; 2.2 程序模块结构程序模块结构 主函数main 创建函数 菜单 边的插
6、入函数顶点的插入函数求顶点的度最小生成树输出函数深度遍历函数判断连通函数 图 2.1：模块结构 2.2.1 结构体定义结构体定义 本系统未采用结构体方法，类的定义如下： 定义顶点: nodecount，edgecount 边：已经分别存放顶点和边的两个数组： aMaxNode和 bMaxNodeMaxNode;其余成员函数均以 public 形式声明。在邻 接矩阵表示的图中，顶点信息用一维数组表示 a。在简单情况下可省略，仅以 下标值代表顶点序号。若需要，顶点信息更加丰富。边（或弧）信息用二维数组 表示 b ，这也是邻接矩阵。包含边的权值。在类中数据成员有 4 个，重要的 无向图的邻接矩阵存储结构 6 / 20 是邻接矩阵 Edge 、总边数 edgecount 和顶点数 nodecount。 c
