数据结构JAVA课程设计

1、 上海电力学院 数据结构（JAVA） 课程设计 题目: 最小生成树问题 学 号： 20083377 姓 名： 郑京阳 院系： 计算机与信息工程学院 专业年级： 软件工程2008级 2011 年 11 月23日目录一、设计目的：2二、设计内容：31、问题描述：32、基本要求：33、试验提示：34、选做内容：3三、概要设计：3四、详细设计：41、构建所有城市顶点全连接：42、对数组 edges中的值进行堆排序：5Sort.sort(edges);53、用克鲁斯卡尔算法实现最小生成树：64、类的设计：9五、程序代码：141、class Edge：142、class Sort：153、class Ma

2、inTest：16六、程序测试：18七、课程设计心得：22八、参考资料：22一、设计目的：（1）熟练掌握图的创建及遍历基本操作算法。（2） 熟练掌握图的最小生成树算法及应用。（3）利用以存储边(带权)的数组表示图，实现在n个城市之间建设最低的经济代价的通信网络。二、设计内容：1、问题描述：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。2、基本要求： (1)利用克鲁斯卡尔算法求网的最小生成树。 (2)实现教科书中定义的抽象数据类型MFSet。以此表示构造生成树过程中的连通分量。 (3)以文本形式输出生成树中各条边以及他们

3、的权值。3、试验提示：通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机数函数产生。图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边(带权)的数组表示图。4、选做内容：利用堆排序(参见教科书)实现选择权值最小的边。三、概要设计：此次我们设计的这个在n个城市之间建设的通信网络，用最小生成树的方法，算出经济代价最小的网络。我们首先要把通信网络所有的带权值的边生成出来，即所有城市顶点间的全连接。接着

4、，利用堆排序算法把所有的带权值的边，从小到大排列起来。然后，用克鲁斯卡尔算法，求出最小生成树。类的设计：我们抽象出一个带权值边的类class Edge，它有三个属性（private int start, end, value;），即起点、终点和权值。在抽象出一个堆排序类class Sort。其余的都放到public class MainTest的main（）函数里了。其实只为了简单点，所以类少了点，其实这个程序本身就很简单。四、详细设计：1、构建所有城市顶点全连接： 首先，我们随机生成15到30vertexNumber个顶点，生成vertexNumber*(vertexNumber-1)/2个

5、全连接需要边edges。然后，这个问题需要所要城市之间的全连接，但是是无向的并且每个城市不可形成自环，所以要有vertexNumber-1个row和row-1个column。然后随机生值为50到100的权值x。然后按顺序加入到Edge edges里。自此我们得到了所有顶点的全连接，并且记录了所有带权值的边edges。代码： int vertexNumber=(int)(Math.random()+1)*15);System.out.println("随机生成"+vertexNumber+"个顶点");Edge edges=new EdgevertexNu

6、mber*(vertexNumber-1)/2;for(int row=0, index=0; row<vertexNumber; row+)for(int column=0; column<row; column+)int x=(int)(Math.random()+1)*50);edgesindex = new Edge(row, column, x);System.out.println("顶点"+row+"和"+column+"之间的距离为"+x);index+;2、对数组 edges中的值进行堆排序：将所有带权值

7、的边edges按权值从小到大的顺序排列，拆分成了三个函数实现。首先sort.sor(edges)，然后sort中创建最大堆，然后把data数组中的data0和dataj交换使得权值最大的edge放到了数组最后，然后j-，使得得到的权值最大的edges不用再堆排序，接着又得到了一个最大权值的edges的data0和dataj交换则data数组的倒数第二个位置得到了数组中的倒数第二个大的值的edges。一直循环，得到了带权值边的edges按权值从小到大排列的数组。具体代码如下，其实就是堆排序，就不详细说明了。Sort.sort(edges);public static void sort(Edge

8、 data)int length = data.length;/创建最大堆for(int i = length/2-1; i>=0; i-)sift(data, i, length-1);/排序for (int j = length - 1; j > 0; j-) /交换data0和datajEdge e = data0;data0 = dataj;dataj = e;sift(data, 0, j-1);public static void sift(Edge a, int root, int limit)int i = root;int j = i*2+1;while (j &

9、lt;= limit) /取其子节点的较大者if (j < limit && aj.getValue() < aj + 1.getValue() j+;if (aj.getValue() > ai.getValue() Edge e = ai;ai = aj;aj = e;i = j;j = i * 2 + 1;elsebreak; /跳出循环3、用克鲁斯卡尔算法实现最小生成树： 此时，我们已经得到了所有带权值的边权值从小到大的数组，我们按照克鲁斯卡尔算法就可以从数组中一条边一条边地添加到result数组中最重输出。一条一条边的添加，虽然我们已经解决了权值从小

10、到大的问题，但是我们怎么解决不形成环的问题呢？也就是如何解决同一连通分量的顶点间的连接问题。 所以，我们要想办法标识加入最终结果集合result不同的联通分量，而且可以看到，没有加入result中的edges的顶点是悬空的，所以也要标识这些悬空的顶点。 我们先将所有没有加入result中的悬空顶点标识为-1int a = new intvertexNumber;/初始时刻，所有顶点的连通分量编号为-1，表示所有顶点都属于一个独立的连通分量for(int i = 0; i<a.length; i+)ai = -1;接着标识不同的加入result中的连通分量：astart = aend =

11、temp;则： 只要将要加入result的edges的两个顶点相等都为-1，说明不和result中的已经加入的联通分量有关系，则可以直接加入result。if(astart=aend && aend=-1)astart = aend = temp;resulttemp = e;temp+;如果将要加入的edges的两个顶点不相等有三种可能：一是start=-1为悬空顶点，那么就让start=end，使加入的连通分量和其连接的result中连通分量的标识统一。else if (astart != aend) if (astart = -1) astart = aend;一是end

12、=-1为悬空顶点，那么就让end=start，使加入的连通分量和其连接的result中连通分量的标识统一。else if (aend = -1) aend = astart;三是要加入的edges使得result中的两个不同的连通分量连接起来，我们就需要将一个和另外一个进行统一。就遍历所有的顶点如果值和start相等就都等于end，则两个连通分量进行了统一。else int t = astart;for (int i = 0; i < vertexNumber; i+) if (ai = t) ai = aend;然后，得到了result，遍历，输出，得到结果。具体代码如下：/* * k

13、ruskal方法得到最小生成树 * * a数组的元素数等于顶点数 * ai的值表示第i个顶点所属的连通分量编号 * ai = aj表示第i和j个顶点属于同一连通分量 */int a = new intvertexNumber;/初始时刻，所有顶点的连通分量编号为-1，表示所有顶点都属于一个独立的连通分量for(int i = 0; i<a.length; i+)ai = -1;/该数组用于记录最小生成树Edge result = new EdgevertexNumber-1;int temp = 0;for(Edge e : edges)int start = e.getStart();

14、int end = e.getEnd();if(astart=aend && aend=-1)astart = aend = temp;resulttemp = e;temp+;else if (astart != aend) if (astart = -1) astart = aend;else if (aend = -1) aend = astart;else int t = astart;for (int i = 0; i < vertexNumber; i+) if (ai = t) ai = aend;resulttemp = e;temp+;/System.o

15、ut.println("-");/System.out.println(Arrays.toString(a);if(temp = vertexNumber-1)break;System.out.println("最小生成树为：");for(Edge e : result)System.out.println("连接顶点"+e.getStart()+"和"+e.getEnd()+"该边的权值为"+e.getValue();4、类的设计： Edge类中，定义了带权值的边。它有三个变量起点、终点、权值

16、。具体代码如下：package mcst;public class Edge private int start, end, value;public Edge(int start,int end,int value)this.start=start;this.end=end;this.value=value;public int getStart() return start;public void setStart(int start) this.start = start;public int getEnd() return end;public void setEnd(int end)

17、 this.end = end;public int getValue() return value;public void setValue(int value) this.value = value;Sort类中实现了堆排序。具体代码如下：package mcst;public class Sort public static void sift(Edge a, int root, int limit)int i = root;int j = i*2+1;while (j <= limit) /取其子节点的较大者if (j < limit && aj.getVa

18、lue() < aj + 1.getValue() j+;if (aj.getValue() > ai.getValue() Edge e = ai;ai = aj;aj = e;i = j;j = i * 2 + 1;elsebreak; /跳出循环public static void sort(Edge data)int length = data.length;/创建最大堆for(int i = length/2-1; i>=0; i-)sift(data, i, length-1);/排序for (int j = length - 1; j > 0; j-) /

19、交换data0和datajEdge e = data0;data0 = dataj;dataj = e;sift(data, 0, j-1);MainTest类调用其它类中的方法和自己的算法实现了一个网的最小生成树问题。具体代码如下：package mcst;public class MainTest public static void main(String args)/* * 初始化 */int vertexNumber=(int)(Math.random()+1)*15);System.out.println("随机生成"+vertexNumber+"个顶

20、点");Edge edges=new EdgevertexNumber*(vertexNumber-1)/2;for(int row=0, index=0; row<vertexNumber; row+)for(int column=0; column<row; column+)int x=(int)(Math.random()+1)*50);edgesindex = new Edge(row, column, x);System.out.println("顶点"+row+"和"+column+"之间的距离为"+

21、x);index+;/对数组 edges中的值进行堆排序Sort.sort(edges);/* * kruskal方法得到最小生成树 * * a数组的元素数等于顶点数 * ai的值表示第i个顶点所属的连通分量编号 * ai = aj表示第i和j个顶点属于同一连通分量 */int a = new intvertexNumber;/初始时刻，所有顶点的连通分量编号为-1，表示所有顶点都属于一个独立的连通分量for(int i = 0; i<a.length; i+)ai = -1;/该数组用于记录最小生成树Edge result = new EdgevertexNumber-1;int te

22、mp = 0;for(Edge e : edges)int start = e.getStart();int end = e.getEnd();if(astart=aend && aend=-1)astart = aend = temp;resulttemp = e;temp+;else if (astart != aend) if (astart = -1) astart = aend;else if (aend = -1) aend = astart;else int t = astart;for (int i = 0; i < vertexNumber; i+) i

23、f (ai = t) ai = aend;resulttemp = e;temp+;/System.out.println("-");/System.out.println(Arrays.toString(a);if(temp = vertexNumber-1)break;System.out.println("最小生成树为：");for(Edge e : result)System.out.println("连接顶点"+e.getStart()+"和"+e.getEnd()+"该边的权值为"+

24、e.getValue();五、程序代码：1、class Edge：package mcst;public class Edge private int start, end, value;public Edge(int start,int end,int value)this.start=start;this.end=end;this.value=value;public int getStart() return start;public void setStart(int start) this.start = start;public int getEnd() return end;pu

25、blic void setEnd(int end) this.end = end;public int getValue() return value;public void setValue(int value) this.value = value;2、class Sort：package mcst;public class Sort public static void sift(Edge a, int root, int limit)int i = root;int j = i*2+1;while (j <= limit) /取其子节点的较大者if (j < limit &

26、amp;& aj.getValue() < aj + 1.getValue() j+;if (aj.getValue() > ai.getValue() Edge e = ai;ai = aj;aj = e;i = j;j = i * 2 + 1;elsebreak; /跳出循环public static void sort(Edge data)int length = data.length;/创建最大堆for(int i = length/2-1; i>=0; i-)sift(data, i, length-1);/排序for (int j = length -

27、1; j > 0; j-) /交换data0和datajEdge e = data0;data0 = dataj;dataj = e;sift(data, 0, j-1);3、class MainTest：package mcst;public class MainTest public static void main(String args)/* * 初始化 */int vertexNumber=(int)(Math.random()+1)*15);System.out.println("随机生成"+vertexNumber+"个顶点");Ed

28、ge edges=new EdgevertexNumber*(vertexNumber-1)/2;for(int row=0, index=0; row<vertexNumber; row+)for(int column=0; column<row; column+)int x=(int)(Math.random()+1)*50);edgesindex = new Edge(row, column, x);System.out.println("顶点"+row+"和"+column+"之间的距离为"+x);index+;/

29、对数组 edges中的值进行堆排序Sort.sort(edges);/* * kruskal方法得到最小生成树 * * a数组的元素数等于顶点数 * ai的值表示第i个顶点所属的连通分量编号 * ai = aj表示第i和j个顶点属于同一连通分量 */int a = new intvertexNumber;/初始时刻，所有顶点的连通分量编号为-1，表示所有顶点都属于一个独立的连通分量for(int i = 0; i<a.length; i+)ai = -1;/该数组用于记录最小生成树Edge result = new EdgevertexNumber-1;int temp = 0;for(Edge e : edges)in