最小生成树数据结构课程设计报告

本文档由prim和克鲁斯卡尔两种算法编写,并附源代码

河北科技大学

课程设计报告

号：专业班级： 计算机113班 课程名称： 数据结构课程设计 学年学期：

指导教师： 郑 广

2014年6月

本文档由prim和克鲁斯卡尔两种算法编写,并附源代码

课程设计成绩评定表

本文档由prim和克鲁斯卡尔两种算法编写,并附源代码

目 录

一、需求分析说明 ........................................................................................................................................................ 1

1.1最小生成树总体功能要求 ............................................................................................................................. 1 1.2基本功能 .......................................................................................................................................................... 1 1.3 模块分析 ........................................................................................................................................................ 1 二、 概要设计说明 ...................................................................................................................................................... 1

2.1设计思路 ......................................................................................................................................................... 1 2.2模块调用图 ..................................................................................................................................................... 2 2.3数据结构设计 ................................................................................................................................................. 2

2.3.1.抽象数据类型 .................................................................................................................................... 2 2.3.2方法描述 ............................................................................................................................................. 2

三、详细设计说明 ........................................................................................................................................................ 3

3.1主函数模块 ..................................................................................................................................................... 3 3.2邻接表输出子模块 ......................................................................................................................................... 3 3.3邻接矩阵输出子模块 ..................................................................................................................................... 3 3.4创建邻接矩阵子模块 ..................................................................................................................................... 3 3.5创建邻接表子模块 ......................................................................................................................................... 3 3.6 Prim子模块 ................................................................................................................................................... 3 3.7 Kruscal子模块 ............................................................................................................................................. 4 四、调试分析 ................................................................................................................................................................ 4

4.1实际完成情况说明 ......................................................................................................................................... 4 4.2 出现的问题及解决方案 ................................................................................................................................ 4 4.3程序中可以改进的地方 ................................................................................................................................. 4 六、课程设计总结 ........................................................................................................................................................ 7 七、测试数据 ................................................................................................................................................................ 7 八、参考书目 ................................................................................................................................................................ 7

本文档由prim和克鲁斯卡尔两种算法编写,并附源代码

一、需求分析说明

1.1最小生成树总体功能要求

在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。

1.2基本功能

在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。

程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。

1.3 模块分析

主模块：用于生成界面和调用各个子模块。 Kruscal模块：以kruscal算法实现最小生成树。 Prim模块：以prim算法实现最小生成树。 邻接表模块：用邻接表方式存储图。 邻接表输出模块：输出邻接表。

邻接矩阵模块：用邻接矩阵方式存储图。 邻接矩阵模块：输出邻接矩阵。

二、概要设计说明

2.1设计思路

问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。

1) 普利姆算法就是先选择根， …… 此处隐藏：9252字，全部文档内容请下载后查看。喜欢就下载吧 ……