1、 数据结构（JAVA）课程设计 题 目:_最小生成树_ 学生姓名：_*_ 学 号：_*_ 院 系： 计算机科学与技术学院 专业年级： _*_级 目录目录 1.设计题目1 2.需求分析1 1 1） 运行环境1 2 2） 输入的形式和输入值的范围1 3 3） 输出的形式描述1 4 4） 功能描述1 5 5）测试数据.1 3.概要设计1 1 1）抽象数据类型定义描述.1 .2 2）功能模块设计1 3 3） 模块层次调用关系图2 4.详细设计。实现概要设计中定义的所有的类的定义及类中成员函 数，并对主要的模块写出伪码算法。 .2 5.调试分析。包括调试过程中遇到的问题及解决的方法、 算法的时间 空间复
2、杂性分析、经验体会。 .6 6.用户使用说明。详细列出每一步的操作说明。 .7 7. 测试结果.7 8.附录： 程序设计源代码.9 1 一、设计题目一、设计题目 1).1).问题描述问题描述 若要在 n 个城市之间建设通信网络，只需要架设n-1 条线路即可。如何以 最低的经济代价建设这个通信网，是一个网的最小生成树问题。 2). 2). 基本要求基本要求 以邻接多重表存储无向带权图， 利用克鲁斯卡尔算法或普瑞姆算法求网的最 小生成树。 二、需求分析二、需求分析 1）运行环境 软件在JDK运行，硬件支持windows系统 2 2）输入的形式和输入值的范围输入的形式和输入值的范围 自动生成顶点数据
3、在1020之间；各个顶点之间权值在2550之间；通过程序 改动亦可生成已知顶点权值之间的最小生成树，需将随机生成代码改为 edge edge=new edge(0,1,16),new（0,2,18）； 将已知顶点、权值通过其函数输入再生成其所对应最小生成树。 3 3） 输出的形式描述输出的形式描述 输出随机生成顶点个数以及各个顶点之间权值； 然后输出本次生成顶点之间 构成的最小生成树。 4 4）功能描述功能描述 该程序会自动生成介于1020个数顶点模拟各城市，再随机生成介于2550 之间数值作为权值模拟各个城市间的距离，并同时生成此次顶点、权值相对应的 最小生成树，模拟各城市间的最小距离，最小
4、生成树。如有确定城市顶点及其权 值，则可改动程序令其不再随机生成顶点权值，在程序中输入如下代码: edge edge=new edge(0,1,16),new（0,2,18） 输入数组为edge数组，edge（起点，终点，权值） 。通过将随机生成代码改 动就可以生成该城市对应权值的最小生成树。 5 5）测试数据）测试数据 生成数据之后检验生成顶点数值是否介于1020之间；检验各顶点间权值大 小是否介于2550间；同时检验其自动生成最小生成树是否正确。 三、概要设计三、概要设计 1 1）抽象数据类型定义描述）抽象数据类型定义描述 定义排序类sort，将各个顶点按照其两顶点之间权值大小排序，从大到
5、小排 序，用到堆排序算法； 定义带权值的边edge，分别存在start（起点） 、end（终点） 、value(权值) 三个变量； 2 定义main类，调用sort、edge类与自身函数通过Kruskal函数实现最小生成 树。 2 2）功能模块设计）功能模块设计 主函数随机生成1020个顶点作为城市并同时生成任意两顶点间2550的权 值作为两城市距离；在界面输出随机生成顶点个数及任意两顶点间权值；再调用 sort函数对权进行排序，按照权值的大小有小到大排序；排序之后实现Kruskal 函数，通过kruskal函数生成最小生成树；最后输出所生成的最小生成树。 3 3）模块层次调用关系图）模块层次
6、调用关系图 四、详细设计四、详细设计 实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块 写出伪码算法。 1. 定义带权值的边及其三个变量start（起点） 、end（终点） 、value（权值） ； 定义该属性为下边的根据权值排序、Kruskal实现最小生成树做下铺垫；函数实 现如下： packagepackage tree; publicpublic classclass sort publicpublic staticstatic voidvoid sift(edge a, intint root, intint limit) 3 intint i = root; intint j = i*2+1;/j为i的左孩子 whilewhile (j =0; i-)/创建最大堆 sift(data, i, length-1); forfor (intint j = lengt
