數(shù)據(jù)結(jié)構(gòu)JAVA課程設(shè)計(jì)

1、 上海電力學(xué)院 數(shù)據(jù)結(jié)構(gòu)（JAVA） 課程設(shè)計(jì) 題目: 最小生成樹問題 學(xué) 號： 20083377 姓 名： 鄭京陽 院系： 計(jì)算機(jī)與信息工程學(xué)院 專業(yè)年級： 軟件工程2008級 2011 年 11 月23日目錄一、設(shè)計(jì)目的：2二、設(shè)計(jì)內(nèi)容：31、問題描述：32、基本要求：33、試驗(yàn)提示：34、選做內(nèi)容：3三、概要設(shè)計(jì)：3四、詳細(xì)設(shè)計(jì)：41、構(gòu)建所有城市頂點(diǎn)全連接：42、對數(shù)組 edges中的值進(jìn)行堆排序：5Sort.sort(edges);53、用克魯斯卡爾算法實(shí)現(xiàn)最小生成樹：64、類的設(shè)計(jì)：9五、程序代碼：141、class Edge：142、class Sort：153、class Ma

2、inTest：16六、程序測試：18七、課程設(shè)計(jì)心得：22八、參考資料：22一、設(shè)計(jì)目的：（1）熟練掌握圖的創(chuàng)建及遍歷基本操作算法。（2） 熟練掌握圖的最小生成樹算法及應(yīng)用。（3）利用以存儲邊(帶權(quán))的數(shù)組表示圖，實(shí)現(xiàn)在n個(gè)城市之間建設(shè)最低的經(jīng)濟(jì)代價(jià)的通信網(wǎng)絡(luò)。二、設(shè)計(jì)內(nèi)容：1、問題描述：若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題。2、基本要求： (1)利用克魯斯卡爾算法求網(wǎng)的最小生成樹。 (2)實(shí)現(xiàn)教科書中定義的抽象數(shù)據(jù)類型MFSet。以此表示構(gòu)造生成樹過程中的連通分量。 (3)以文本形式輸出生成樹中各條邊以及他們

3、的權(quán)值。3、試驗(yàn)提示：通信線路一旦建立，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無向網(wǎng)。設(shè)圖的頂點(diǎn)數(shù)不超過30個(gè)，并為簡單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)，可利用C語言提供的隨機(jī)數(shù)函數(shù)產(chǎn)生。圖的存儲結(jié)構(gòu)的選取應(yīng)和所作操作相適應(yīng)。為了便于選擇權(quán)值最小的邊，此題的存儲結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲邊(帶權(quán))的數(shù)組表示圖。4、選做內(nèi)容：利用堆排序(參見教科書)實(shí)現(xiàn)選擇權(quán)值最小的邊。三、概要設(shè)計(jì)：此次我們設(shè)計(jì)的這個(gè)在n個(gè)城市之間建設(shè)的通信網(wǎng)絡(luò)，用最小生成樹的方法，算出經(jīng)濟(jì)代價(jià)最小的網(wǎng)絡(luò)。我們首先要把通信網(wǎng)絡(luò)所有的帶權(quán)值的邊生成出來，即所有城市頂點(diǎn)間的全連接。接著

4、，利用堆排序算法把所有的帶權(quán)值的邊，從小到大排列起來。然后，用克魯斯卡爾算法，求出最小生成樹。類的設(shè)計(jì)：我們抽象出一個(gè)帶權(quán)值邊的類class Edge，它有三個(gè)屬性（private int start, end, value;），即起點(diǎn)、終點(diǎn)和權(quán)值。在抽象出一個(gè)堆排序類class Sort。其余的都放到public class MainTest的main（）函數(shù)里了。其實(shí)只為了簡單點(diǎn)，所以類少了點(diǎn)，其實(shí)這個(gè)程序本身就很簡單。四、詳細(xì)設(shè)計(jì)：1、構(gòu)建所有城市頂點(diǎn)全連接： 首先，我們隨機(jī)生成15到30vertexNumber個(gè)頂點(diǎn)，生成vertexNumber*(vertexNumber-1)/2個(gè)

5、全連接需要邊edges。然后，這個(gè)問題需要所要城市之間的全連接，但是是無向的并且每個(gè)城市不可形成自環(huán)，所以要有vertexNumber-1個(gè)row和row-1個(gè)column。然后隨機(jī)生值為50到100的權(quán)值x。然后按順序加入到Edge edges里。自此我們得到了所有頂點(diǎn)的全連接，并且記錄了所有帶權(quán)值的邊edges。代碼： int vertexNumber=(int)(Math.random()+1)*15);System.out.println("隨機(jī)生成"+vertexNumber+"個(gè)頂點(diǎn)");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("頂點(diǎn)"+row+"和"+column+"之間的距離為"+x);index+;2、對數(shù)組 edges中的值進(jìn)行堆排序：將所有帶權(quán)值

7、的邊edges按權(quán)值從小到大的順序排列，拆分成了三個(gè)函數(shù)實(shí)現(xiàn)。首先sort.sor(edges)，然后sort中創(chuàng)建最大堆，然后把data數(shù)組中的data0和dataj交換使得權(quán)值最大的edge放到了數(shù)組最后，然后j-，使得得到的權(quán)值最大的edges不用再堆排序，接著又得到了一個(gè)最大權(quán)值的edges的data0和dataj交換則data數(shù)組的倒數(shù)第二個(gè)位置得到了數(shù)組中的倒數(shù)第二個(gè)大的值的edges。一直循環(huán)，得到了帶權(quán)值邊的edges按權(quán)值從小到大排列的數(shù)組。具體代碼如下，其實(shí)就是堆排序，就不詳細(xì)說明了。Sort.sort(edges);public static void sort(Edge

8、 data)int length = data.length;/創(chuàng)建最大堆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) /取其子節(jié)點(diǎn)的較大者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; /跳出循環(huán)3、用克魯斯卡爾算法實(shí)現(xiàn)最小生成樹： 此時(shí)，我們已經(jīng)得到了所有帶權(quán)值的邊權(quán)值從小到大的數(shù)組，我們按照克魯斯卡爾算法就可以從數(shù)組中一條邊一條邊地添加到result數(shù)組中最重輸出。一條一條邊的添加，雖然我們已經(jīng)解決了權(quán)值從小

10、到大的問題，但是我們怎么解決不形成環(huán)的問題呢？也就是如何解決同一連通分量的頂點(diǎn)間的連接問題。 所以，我們要想辦法標(biāo)識加入最終結(jié)果集合result不同的聯(lián)通分量，而且可以看到，沒有加入result中的edges的頂點(diǎn)是懸空的，所以也要標(biāo)識這些懸空的頂點(diǎn)。 我們先將所有沒有加入result中的懸空頂點(diǎn)標(biāo)識為-1int a = new intvertexNumber;/初始時(shí)刻，所有頂點(diǎn)的連通分量編號為-1，表示所有頂點(diǎn)都屬于一個(gè)獨(dú)立的連通分量for(int i = 0; i<a.length; i+)ai = -1;接著標(biāo)識不同的加入result中的連通分量：astart = aend =

11、temp;則： 只要將要加入result的edges的兩個(gè)頂點(diǎn)相等都為-1，說明不和result中的已經(jīng)加入的聯(lián)通分量有關(guān)系，則可以直接加入result。if(astart=aend && aend=-1)astart = aend = temp;resulttemp = e;temp+;如果將要加入的edges的兩個(gè)頂點(diǎn)不相等有三種可能：一是start=-1為懸空頂點(diǎn)，那么就讓start=end，使加入的連通分量和其連接的result中連通分量的標(biāo)識統(tǒng)一。else if (astart != aend) if (astart = -1) astart = aend;一是end

12、=-1為懸空頂點(diǎn)，那么就讓end=start，使加入的連通分量和其連接的result中連通分量的標(biāo)識統(tǒng)一。else if (aend = -1) aend = astart;三是要加入的edges使得result中的兩個(gè)不同的連通分量連接起來，我們就需要將一個(gè)和另外一個(gè)進(jìn)行統(tǒng)一。就遍歷所有的頂點(diǎn)如果值和start相等就都等于end，則兩個(gè)連通分量進(jìn)行了統(tǒng)一。else int t = astart;for (int i = 0; i < vertexNumber; i+) if (ai = t) ai = aend;然后，得到了result，遍歷，輸出，得到結(jié)果。具體代碼如下：/* * k

13、ruskal方法得到最小生成樹 * * a數(shù)組的元素?cái)?shù)等于頂點(diǎn)數(shù) * ai的值表示第i個(gè)頂點(diǎn)所屬的連通分量編號 * ai = aj表示第i和j個(gè)頂點(diǎn)屬于同一連通分量 */int a = new intvertexNumber;/初始時(shí)刻，所有頂點(diǎn)的連通分量編號為-1，表示所有頂點(diǎn)都屬于一個(gè)獨(dú)立的連通分量for(int i = 0; i<a.length; i+)ai = -1;/該數(shù)組用于記錄最小生成樹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("連接頂點(diǎn)"+e.getStart()+"和"+e.getEnd()+"該邊的權(quán)值為"+e.getValue();4、類的設(shè)計(jì)： Edge類中，定義了帶權(quán)值的邊。它有三個(gè)變量起點(diǎn)、終點(diǎn)、權(quán)值

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類中實(shí)現(xiàn)了堆排序。具體代碼如下：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) /取其子節(jié)點(diǎn)的較大者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; /跳出循環(huán)public static void sort(Edge data)int length = data.length;/創(chuàng)建最大堆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類調(diào)用其它類中的方法和自己的算法實(shí)現(xiàn)了一個(gè)網(wǎng)的最小生成樹問題。具體代碼如下：package mcst;public class MainTest public static void main(String args)/* * 初始化 */int vertexNumber=(int)(Math.random()+1)*15);System.out.println("隨機(jī)生成"+vertexNumber+"個(gè)頂

20、點(diǎn)");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("頂點(diǎn)"+row+"和"+column+"之間的距離為"+

21、x);index+;/對數(shù)組 edges中的值進(jìn)行堆排序Sort.sort(edges);/* * kruskal方法得到最小生成樹 * * a數(shù)組的元素?cái)?shù)等于頂點(diǎn)數(shù) * ai的值表示第i個(gè)頂點(diǎn)所屬的連通分量編號 * ai = aj表示第i和j個(gè)頂點(diǎn)屬于同一連通分量 */int a = new intvertexNumber;/初始時(shí)刻，所有頂點(diǎn)的連通分量編號為-1，表示所有頂點(diǎn)都屬于一個(gè)獨(dú)立的連通分量for(int i = 0; i<a.length; i+)ai = -1;/該數(shù)組用于記錄最小生成樹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("連接頂點(diǎn)"+e.getStart()+"和"+e.getEnd()+"該邊的權(quán)值為"+

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) /取其子節(jié)點(diǎn)的較大者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; /跳出循環(huán)public static void sort(Edge data)int length = data.length;/創(chuàng)建最大堆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("隨機(jī)生成"+vertexNumber+"個(gè)頂點(diǎn)");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("頂點(diǎn)"+row+"和"+column+"之間的距離為"+x);index+;/

29、對數(shù)組 edges中的值進(jìn)行堆排序Sort.sort(edges);/* * kruskal方法得到最小生成樹 * * a數(shù)組的元素?cái)?shù)等于頂點(diǎn)數(shù) * ai的值表示第i個(gè)頂點(diǎn)所屬的連通分量編號 * ai = aj表示第i和j個(gè)頂點(diǎn)屬于同一連通分量 */int a = new intvertexNumber;/初始時(shí)刻，所有頂點(diǎn)的連通分量編號為-1，表示所有頂點(diǎn)都屬于一個(gè)獨(dú)立的連通分量for(int i = 0; i<a.length; i+)ai = -1;/該數(shù)組用于記錄最小生成樹Edge result = new EdgevertexNumber-1;int temp = 0;for(Edge e : edges)in