数据结构程序设计最小生成树.doc

重庆交通大学信息科学与工程学院 课程设计报告书 专 业 计算机科学与技术 课程设计名称 数据结构 题 目 n 个城市间的最小生成树 班 级 软件一班 设 计 者 王洁松 学 号 631106050108 指 导 教 师 鲁云平 完 成 时 间 2013 年 6 月 16 日至 2013 年 6 月 27 日 重庆交通大学信息科学与工程学院课程设计任务书 课 程 数据结构 班级 软件一班 指导教师 鲁云平 题 目 同组人数1 5人 每人代码量不少于 300行 设计要求 给定一个地区的 N 个城市的距离网 至少 6 个城市 10 跳边 用 Prim 算法或 Kruskal 算法建立最小生成树 并计算得到的最小生成树的代 价 报告书要求 设计报告主要包括内容 参见后面的格式 1 系统的功能需求及分析 2 类结构及类设计说明 3 系统总体结构 4 系统实现及主要代码 5 系统功能测试 6 设计体会 要求 学生完成课程设计后 每个同学均应提交课程设计报告及软件 设计报告要求文字通畅 排版规范 设计报告文字原则上不少于 3000 字 程序代码除外 并装订成册 星期 周次 一二三四五六日 第 17 周 1 41 41 41 41 4 自定自定 第 18 周 1 41 41 41 41 4 自定自定 上机时间安排 指导地 点及考 核时间 1 指导地点 双福校区信息技术实验室 2 考核时间 第 18 周星期五上午 答辩方式考核 学生用 PPT 汇 报及演示 版面要求 1 题目用黑体三号 段后距 18 磅 或 1 行 居中对齐 2 标题用黑体四号 段前 段后距 6 磅 或 0 3 行 3 正文用小四号宋体 行距为固定值 20 程序代码用固定值 15 4 标题按 一 1 顺序编号 目 录 一一 需求分析 需求分析 2 1 问题描述 问题描述 2 2 基本要求基本要求 2 二 二 概要设计概要设计 3 1 程序设计思路程序设计思路 3 2 存储结构设计存储结构设计 3 3 主要算法设计主要算法设计 5 4 存储结构定义存储结构定义 5 三 详细设计三 详细设计 7 1 数据类型定义数据类型定义 7 2 函数实现代码函数实现代码 7 3 函数之间的调用关系函数之间的调用关系 7 四 用户手册四 用户手册 8 五 测试结果五 测试结果 8 六 调试分析及心得体会六 调试分析及心得体会 7 七 参考文献七 参考文献 9 八 附录八 附录 10 一一 需求分析 需求分析 1 问题描述 问题描述 一个地区的 n 个城市间的距离网 用 Prim 算法或 Kruskal 算法建立最小生成树 并计算得到的最小生成树的代价 2 基本要求基本要求 1 城市间的距离网采用邻接矩阵表示 邻接矩阵的存储结构定义采用课本中给出 的定义 若两个城市之间不存在道路 则将相应边的权值设为自己定义的无穷大值 要 求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路 并显示得到的最小生成 树的代价 2 表示城市间距离网的邻接矩阵 要求至少 6 个城市 10 条边 二 二 概要设计概要设计 2 1 程序设计思路 每个城市可以表示成城市网中的顶点 城市间的距离可以用距离网中的边表示 边 的权值表示两地间的直接路径 采用 Kruskal 算法建立最小生成树 历城市生成最小 生成树 通过计算得到最小生成树的代价 1 克鲁斯卡尔算法思想基本描述 克鲁斯卡尔算法思想基本描述 为使生成树上边的权值之和最小 显然 其中每一条边的权值应该尽可 能地小 克鲁斯卡尔算法的做法就是 先构造一个只含 n 个顶点的子图 SG 然 后从权值最小的边开始 若它的添加不使 SG 中产生回路 则在 SG 上加上这条 边 如此重复 直至加上 n 1 条边为止 2 克鲁斯卡尔算法设计克鲁斯卡尔算法设计 a 设置计数器 E 初值为 0 记录已选中的边数 将所有边从小到大排序 存 于 p 中 b 从 p 中选择一条权值最小的边 检查其加入到最小生成树中是否会构成 回路 若是 则此边不加入生成树 否则 加入到生成树中 计数器 E 累加 1 c 从 E 中删除此最小边 转 b 继续执行 直到 k n 1 算法结束 d 判断是否构成回路的方法 设置集合 S 其中存放已加入到生成树中的边所连接的顶点集合 当一条新的 边要加入到生成树中时 检查此边所连接的两个顶点是否都已经在 S 中 若是 则表示构成回路 否则 若有一个顶点不在 S 中 或者两个顶点都不在 S 中 则不够成回路 15 克鲁斯卡尔算法生成最小生成树的过程克鲁斯卡尔算法生成最小生成树的过程 3 防止不能构成最小生成树的图 为避免输入的图构成的不是连通图 设计了 judge 函数来判断输入数 据构成的是否为连通图 此函数的主要算法是源于普里姆 PRIM 算法 经过 改编 形成了新的函数 2 2 存储结构设计 由于各城市间的路径类似网 所以可以用图的结构存储城市信息 城市间的距离可以用距 离网中的边表示 边的权值表示两地间的直接路径 弱一个城市可以到达另一个城市 则两城市间可以互相到达 故可以直接用无向图表示 且相互对称 存储结构定义如下 typedef struct node 构造一个结构体 两个城市可以看成起点和终点 之间的道路 可以看成一个边 int str 起点 int end 终点 int dis 距离 node 01 23 45 15 17 8 14 3 18 7 12 21 01 2 3 4 5 0 1 2 3 4 5 7 3 3 2 4 0 1 3 5 7 3 8 3 5 0 2 4 83 1 3 5 0 2 4 8 14 3 1 3 5 0 2 4 8 14 3 1 3 5 7 77 15 19 12 开始 构造城市信息图 是否为连通 图 求最小生成树 初始化 是否构成 回路 将最小生成树边集合 打印出最小生成树 的权值与最小生成树的 代价 退出 是 是 否 否 node p max temp p 记录城市信息 typedef struct 邻接矩阵存储图结构 int vexs MAX LNT 数组用于存储城市数 int adj max 1 max 1 图的邻接矩阵表示 int n e n 代表城市数 e 代表城市间边数 graph 2 3 主要算法设计 2 3 12 3 1程序的模块结构流程图程序的模块结构流程图 2 3 2该程序的模块结构主要函数该程序的模块结构主要函数 typedef struct node 构造一个结构体 两个城市可以看成起点和终点 之间的道路可以看 成一个边 int str 起点 int end 终点 int dis 距离 node typedef struct 邻接矩阵存储图结构 int vexs MAX LNT 数组用于存储城市数 int adj max 1 max 1 图的邻接矩阵表示 int n e n 代表城市数 e 代表城市间边数 graph 2 3 2 测试用例设计 7 测试用例 1 可以形成最小生成树 测试用例 2 不能形成最小生成树 三 详细设计三 详细设计 1 数据类型定义数据类型定义 typedef struct node 构造一个结构体 两个城市可以看成起点和终点 之间的道路可以看 成一个边 int str 起点 int end 终点 int dis 距离 node typedef struct 邻接矩阵存储图结构 int vexs MAX LNT 数组用于存储城市数 01 2 4 15 17 8 14 3 18 12 21 3 5 19 7 01 2 3 4 5 4 10 7 88 2 9 4 5 3 10 int adj max 1 max 1 图的邻接矩阵表示 int n e n 代表城市数 e 代表城市间边数 graph 2 函数实现代码函数实现代码 a int main 主程序 b int menu 菜单函数 c void create 输入城市信息函数 d void judge 判断是否能够生成最小生成树函数 e void display 打印输出 f void set 初始化 pre rank 函数 g void find 判断是否构成回路函数 h void Union 将能构成最小生成树的边添加到一个集合 l void Krushal 克鲁斯算法求最小生成树 3 函数之间的调用关系函数之间的调用关系 程序执行从主函数 main 开始 首先在运行界面上显示菜单 调用菜单函 menu 根据 switch 函数选择调用的函数 其中选择 1 调用 create 函数 用来创建 城市之间距离的图 选择 2 调用 judge 函数 用来判断输入的图是否能够产 生最小生成树 选择 3 调用 display 函数 用来显示最小生成树 而函数本身 也存在函数的调用 在 display 函数中调用 Kruskal 函数 该函数式用克鲁斯 卡尔算法求最小生成树 而 Kruskal 函数中又调用三个函数 set find Union 它们作用是检验当一条边添加进去 是否会产生回路 四 用户手册四 用户手册 1 运行环境 执行文件 1 编制 调试和运行程序总是依赖所使用的语言环境 当然也令支持语言的系统程序 的基础环境即操作系统环境的影响 此课程设计以 Visual studio C 6 0 为依据 作为运行环境 2 用户界面 Visual studio C 6 0 3 操作过程 点击 Visual studio C 6 0 的快捷图标 进入 Visual studio C 6 0 的开发环境 进入 文件 子菜单 选取 新建 在 新建 对话框选择 C sourse file 在文件名中输入一个文件名 Krushal 选择存储位置后按 确定 编写新的程序 判断改错之后 保存 对文件进行编译和链接 在程序编写后 需要将其编译成可执行文件 按 有错 找出问题修改 继续 按 建立连接 运行 按 按钮进行运行 五 测试结果五 测试结果 测试用例 1 运行结果如下 运行结果如下图所示 2 六 调试分析六 调试分析及心得体会及心得体会 通过两周的 数据结构与 C 语言 课程实训 我不仅对图的概念有了一 个新的认识 而且对算法和 C 语言有了更深的理解 在学习了 数据结构 这 门课后 我慢慢地体会到了其中的奥妙 图能够在计算机中存在 首先要捕捉 它有哪些具体化 数字化的信息 比如说权值 顶点个数等 这也是说明了想 要把生活中的信息转化成到计算机中必须用数字来完整的构成一个信息库 而 图的存在 又涉及到了顶点与顶点之间的联系 图分为有向图和无向图 而无 向图又是有向图在权值双向相等下的一种特例 在这次求可使构成 n 个城市的 最小生成树的程序设计中 我采用了 a i j 数组利用邻接矩阵方式来储存 城市与城市间信息 再利用经典的克鲁斯克尔算法求得了最小生成树 在这次课程设计中 我明白了编写一段代码 我们不仅要考虑它的可行性 更应该考虑它的算法复杂度 运行效率 做同一件事 一万个人有一万种做法 换而言之 一万个人写一段代码实现同一个功能可以得到一万段代码 由此 我们可以看出做一件事要精益求精 多加斟酌 七 参考文献七 参考文献 1 网络资源 2 严蔚敏 吴伟民 数据结构 第二版 北京 清华大学出版社 1992 3 数据结构 C 语言版 李云清 杨庆红 揭安全 编著 人民邮电 出版社 4 C 语言程序设计 第二版 谭浩强 著 清华大学出版社 5 数据结构课程设计 苏仕华 等编著 机械工业出版社 八 附录八 附录 原程序文件名清单 include include include define max 20 城市间边数 define MAX LNT 10 城市数 define INF 32627 两个城市间无直接路径 用大数 32627 表示 typedef struct node 构造一个结构体 两个城市可以看成起点和终点 之间的道路可以看 成一个边 int str 起点 int end 终点 int dis 距离 node node p max temp p 记录城市信息 typedef struct 邻接矩阵存储图结构 int vexs MAX LNT 数组用于存储城市数 int adj max 1 max 1 图的邻接矩阵表示 int n e n 代表城市数 e 代表城市间边数 graph int pre 100 rank 100 用于判断是否构成回路 int arcs MAX LNT MAX LNT n 表示城市个数 arcs 记录城市间权值 int menu 菜单函数 int m printf 2013 年 6 月 25 日 n n printf 求最小生成树 n printf n n printf 1 输入城市之间的信息 n printf 2 判断是否能构成一个最小生成树 n printf 3 遍历所有城市生成最小生成树 n printf 4 退出 n printf n n printf 请输入所选功能 1 4 system color 35 改变界面颜色的 3 表示背景色湖蓝色 5 表示前景色紫色 scanf d return m void create graph g 输入城市信息 int i j k printf 输入城市数为 scanf d printf n printf 输入个城市间边数为 scanf d printf 输入城市的各个顶点为 for i 0 in i scanf d 顶点存入数组 vexs printf 输入 d 条边 建立邻接矩阵 g e printf n for i 0 in i 初始化邻接矩阵 for j 0 jn j if i j g adj i j 0 else g adj i j INF printf 请输入具有邻接关系的两个顶点在矩阵中所在的行与列及权值 n for k 0 ke k 有 g e 条边 即有 g e 个权值 scanf d d scanf d for i 0 in i for j 0 jn j g adj j i g adj i j printf 图的邻接矩阵如下 n for i 0 in i 输出邻接矩阵 g for j 0 jn j if g adj i j INF printf t 3s else printf t 3d g adj i j printf n 下面三个函数作用是检验当一条边添加进去 是否会产生回路 void set int x 初始化 pre x x rank x 0 int find int x 找到这个点的祖先 if x pre x pre x find pre x return pre x void Union int x int y 将这两个添加到一个集合里去 x find x y find y if rank x rank y pre y x rank x else pre y x void Kruskal graph g int ans 0 i j k 0 ans 用来记录生成最小树的权总值 int index int count 0 记录打印边的条数 for i 0 in i 初始化数组 pre x rank x set i for i 0 in i for j i 1 j n j p k str i p k end j p k dis g adj i j 先把所有城市之间的路段看成一个边 for i 0 i k i 把所有的边按从小到大进行排序 index i fo