數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)java--最小生成樹

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：16 大?。?.67MB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語一試題真題（含答案詳解+作文范文）_第1頁

已閱讀1頁，還剩15頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　數(shù)據(jù)結(jié)構(gòu)（JAVA）課程設(shè)計(jì)　　題目:____最小生成樹_______　　學(xué)生姓名：_****___________　　學(xué) 號(hào)：_____*******_______　　院系：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　　專

2、業(yè)年級(jí)： ______*****___級(jí)　　目錄　　1.設(shè)計(jì)題目................................................1　　2.需求分析................................................1

3、　　1）運(yùn)行環(huán)境................................................1　　2）輸入的形式和輸入值的范圍................................1　　3）輸出的形式描述........................................

4、..1　　4）功能描述................................................1　　5）測(cè)試數(shù)據(jù)...............................................1　　3.概要設(shè)計(jì).................................

5、...............1　　1）抽象數(shù)據(jù)類型定義描述...................................1　　.2）功能模塊設(shè)計(jì)..........................................1　　3）模塊層次調(diào)用關(guān)系圖........................

6、..............2　　4.詳細(xì)設(shè)計(jì)。實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的類的定義及類中成員函數(shù)，并對(duì)主要的模塊寫出偽碼算法。...........................2　　5.調(diào)試分析。包括調(diào)試過程中遇到的問題及解決的方法、算法的時(shí)間空間復(fù)雜性分析、經(jīng)驗(yàn)體會(huì)。.................................6</p&

7、gt;　　6.用戶使用說明。詳細(xì)列出每一步的操作說明。.................7　　7. 測(cè)試結(jié)果...............................................7　　8.附錄：程序設(shè)計(jì)源代碼.....................................9&

8、lt;p>　　一、設(shè)計(jì)題目　　1).問題描述　　若要在 n 個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1 條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題。　　2). 基本要求

9、;　　以鄰接多重表存儲(chǔ)無向帶權(quán)圖，利用克魯斯卡爾算法或普瑞姆算法求網(wǎng)的最小生成樹。　　二、需求分析　　1）運(yùn)行環(huán)境　　軟件在JDK運(yùn)行，硬件支持windows系統(tǒng)<p

10、>　　輸入的形式和輸入值的范圍　　自動(dòng)生成頂點(diǎn)數(shù)據(jù)在10~20之間；各個(gè)頂點(diǎn)之間權(quán)值在25~50之間；通過程序改動(dòng)亦可生成已知頂點(diǎn)權(quán)值之間的最小生成樹，需將隨機(jī)生成代碼改為　　edge edge[]={new edge(0,1,16),new（0,2,18）......}；　　將已知頂點(diǎn)、權(quán)值通過其函數(shù)輸入

11、再生成其所對(duì)應(yīng)最小生成樹。　　輸出的形式描述　　輸出隨機(jī)生成頂點(diǎn)個(gè)數(shù)以及各個(gè)頂點(diǎn)之間權(quán)值；然后輸出本次生成頂點(diǎn)之間構(gòu)成的最小生成樹。　　功能描述　　該程序會(huì)自動(dòng)生成介于10~20個(gè)數(shù)頂點(diǎn)模擬各城市

12、，再隨機(jī)生成介于25~50之間數(shù)值作為權(quán)值模擬各個(gè)城市間的距離，并同時(shí)生成此次頂點(diǎn)、權(quán)值相對(duì)應(yīng)的最小生成樹，模擬各城市間的最小距離，最小生成樹。如有確定城市頂點(diǎn)及其權(quán)值，則可改動(dòng)程序令其不再隨機(jī)生成頂點(diǎn)權(quán)值，在程序中輸入如下代碼:　　edge edge[]={new edge(0,1,16),new（0,2,18）......}　　輸入數(shù)組為edge數(shù)組

13、，edge（起點(diǎn)，終點(diǎn)，權(quán)值）。通過將隨機(jī)生成代碼改動(dòng)就可以生成該城市對(duì)應(yīng)權(quán)值的最小生成樹。　　5）測(cè)試數(shù)據(jù)　　生成數(shù)據(jù)之后檢驗(yàn)生成頂點(diǎn)數(shù)值是否介于10~20之間；檢驗(yàn)各頂點(diǎn)間權(quán)值大小是否介于25~50間；同時(shí)檢驗(yàn)其自動(dòng)生成最小生成樹是否正確。　　三、概要設(shè)

14、計(jì)　　1）抽象數(shù)據(jù)類型定義描述　　定義排序類sort，將各個(gè)頂點(diǎn)按照其兩頂點(diǎn)之間權(quán)值大小排序，從大到小排序，用到堆排序算法；　　定義帶權(quán)值的邊edge，分別存在start（起點(diǎn)）、end（終點(diǎn)）、value(權(quán)值)三個(gè)變量；　　定義main類，調(diào)用so

15、rt、edge類與自身函數(shù)通過Kruskal函數(shù)實(shí)現(xiàn)最小生成樹。　　2）功能模塊設(shè)計(jì)　　主函數(shù)隨機(jī)生成10~20個(gè)頂點(diǎn)作為城市并同時(shí)生成任意兩頂點(diǎn)間25~50的權(quán)值作為兩城市距離；在界面輸出隨機(jī)生成頂點(diǎn)個(gè)數(shù)及任意兩頂點(diǎn)間權(quán)值；再調(diào)用sort函數(shù)對(duì)權(quán)進(jìn)行排序，按照權(quán)值的大小有小到大排序；排序之后實(shí)現(xiàn)Kruskal函數(shù)，

16、通過kruskal函數(shù)生成最小生成樹；最后輸出所生成的最小生成樹。　　3）模塊層次調(diào)用關(guān)系圖　　四、詳細(xì)設(shè)計(jì)　　實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的類的定義及類中成員函數(shù)，并對(duì)主要的模塊　　寫出偽碼算法。&

17、lt;/p>　　定義帶權(quán)值的邊及其三個(gè)變量start（起點(diǎn)）、end（終點(diǎn)）、value（權(quán)值）；定義該屬性為下邊的根據(jù)權(quán)值排序、Kruskal實(shí)現(xiàn)最小生成樹做下鋪墊；函數(shù)實(shí)現(xiàn)如下：　　package tree;　　public class sort {　　public static

18、void sift(edge a[], int root, int limit)　　{　　int i = root;　　int j = i*2+1;//j為i的左孩子　　while (j <= limit) //沿較小值孩子節(jié)點(diǎn)

19、向下篩選　　{　　if (j < limit && a[j].getValue() < a[j + 1].getValue())//數(shù)組元素比較　　{　　j++;//j

20、為左右孩子的較小者　　}　　if (a[j].getValue() > a[i].getValue()) //若父親節(jié)點(diǎn)值較大　　{　　edge e = a[i];//孩子節(jié)點(diǎn)中較小值上移&

21、lt;/p>　　a[i] = a[j];　　a[j] = e;　　i = j;　　j = i * 2 + 1;//i、j向下一層　　}</b&g

22、t;　　else{　　break; //跳出循環(huán)　　}　　}　　}<

23、/p>　　public static void sort(edge data[])　　{　　int length = data.length;　　for(int i = length/2-1; i>=0; i--)//創(chuàng)建最大堆</p&

24、gt;　　{　　sift(data, i, length-1);　　}　　for (int j = length - 1; j > 0; j--)//每趟把最大值交換到后面字，再生成堆&

25、lt;p>　　{　　edge e = data[0];　　data[0] = data[j];　　data[j] = e;　　sift(data, 0, j-1);

26、}　　}　　}　　隨機(jī)生成介于10~20之間個(gè)頂點(diǎn)作為各個(gè)城市，并同時(shí)生成任意兩頂點(diǎn)間權(quán)值，介于25~50之間；每n個(gè)頂點(diǎn)之間最多生成n*(n-1)條邊；生成vertexNumber-1個(gè)row（行）和row-1個(gè)co

27、lumn（列）可以防止同一個(gè)頂點(diǎn)生成自環(huán)；　　函數(shù)實(shí)現(xiàn)如下：　　int vertexNumber=(int)((Math.random()+1)*10);　　System.out.println("隨機(jī)生成"+vertexNumber+"個(gè)頂點(diǎn)&

28、quot;);　　edge edges[]=new edge[vertexNumber*(vertexNumber-1)/2];　　for(int row=0, index=0; row<vertexNumber; row++)　　{//row行、column列、index數(shù)組<

29、;p>　　for(int column=0; column<row; column++)　　{　　int x=(int)((Math.random()+1)*25);//random隨機(jī)的　　edges[index] = new edge(row, column,

30、 x);　　System.out.println("頂點(diǎn)"+row+"和"+column+"之間的距離為"+x);　　index++;　　}<p&g

31、t;　　}　　定義排序類sort，按照堆排序函數(shù)對(duì)數(shù)組edge[]按照權(quán)值大小從小到大進(jìn)行排序（參照課本299頁）；　　package tree;　　public class sort {　　public static void si

32、ft(edge a[], int root, int limit)　　{　　int i = root;　　int j = i*2+1;//j為i的左孩子　　while (j <= limit) //沿較小值孩子節(jié)點(diǎn)向下篩選<

33、;/p>　　{　　if (j < limit && a[j].getValue() < a[j + 1].getValue())//數(shù)組元素比較　　{　　j++;//j為左右孩子的較

34、小者　　}　　if (a[j].getValue() > a[i].getValue()) //若父親節(jié)點(diǎn)值較大　　{　　edge e = a[i];//孩子節(jié)點(diǎn)中較小值上移</p&g

35、t;　　a[i] = a[j];　　a[j] = e;　　i = j;　　j = i * 2 + 1;//i、j向下一層　　}</

36、p>　　else{　　break; //跳出循環(huán)　　}　　}　　}

37、　　public static void sort(edge data[])　　{　　int length = data.length;　　for(int i = length/2-1; i>=0; i--)//創(chuàng)建最大堆&l

38、t;p>　　{　　sift(data, i, length-1);　　}　　for (int j = length - 1; j > 0; j--)//每趟把最大值交換到后面字，再生成堆

39、;　　{　　edge e = data[0];　　data[0] = data[j];　　data[j] = e;　　sift(data, 0, j-1);　　}</b

40、>　　}　　}　　Kruskal方法實(shí)現(xiàn)最小生成樹。　　Kruskal方法與Prim方法都是基于最小生成樹的MST性質(zhì)：設(shè)G(V,E)是一個(gè)聯(lián)通帶權(quán)無向圖，TV是頂點(diǎn)集合V的一個(gè)非空真子集。

41、若（tv，v）包含于E是一條權(quán)值最小的邊，其中tv包含于TV，v包含于V-TV，則必定存在G的一棵最小生成樹T,T包含邊(tv,v)。其Kruskal算法參照課本334頁。其算法如下：　　int a[] = new int[vertexNumber];　　//初始時(shí)刻，所有頂點(diǎn)的連通分量編號(hào)為-1，表示所有頂點(diǎn)都屬于一個(gè)獨(dú)立的連通分量

42、　　for(int i = 0; i<a.length; i++)　　{　　a[i] = -1;　　}　　edge result[] = new edge[vertex

43、Number-1];　　//該數(shù)組用于記錄最小生成樹　　int temp = 0;　　for(edge e : edges){　　int start = e.getStart();　　int end = e.getEnd();&l

44、t;/p>　　if(a[start]==a[end] && a[end]==-1){　　a[start] = a[end] = temp;　　result[temp] = e;　　temp++;<p&g

45、t;　　}　　else if (a[start] != a[end]) {　　if (a[start] == -1) {　　a[start] = a[end];　　}<

46、;p>　　else if (a[end] == -1) {　　a[end] = a[start];　　}　　else {　　int t = a[start];<

47、p>　　for (int i = 0; i < vertexNumber; i++) {　　if (a[i] == t) {　　a[i] = a[end];　　}　　}</p&g

48、t;　　}　　result[temp] = e;　　temp++;　　}　　五、調(diào)試分析</

49、p>　　包括調(diào)試過程中遇到的問題及解決的方法、算法的時(shí)間空間復(fù)雜性分析、　　經(jīng)驗(yàn)體會(huì)。　　Sort排序類算法時(shí)間復(fù)雜度為O（log2n），Kruskal算法時(shí)間復(fù)雜度為O(1)；　　調(diào)試過程中，Kruskal算法實(shí)現(xiàn)出現(xiàn)問題，剛開始無法實(shí)現(xiàn)該函數(shù)，

50、無法生成最小生成樹；經(jīng)請(qǐng)教同學(xué)、查看資料、查看課本解決問題。實(shí)現(xiàn)堆排序過程無法實(shí)現(xiàn)，參考課本之后解得堆排序算法實(shí)現(xiàn)過程：調(diào)用sift（）方法n/2次，使得數(shù)據(jù)序列成為最大堆；對(duì)j=n-1，n-2...1，執(zhí)行下列n-1次完成排序操作：交換根end[0]和元素end[j]，調(diào)用sift（）方法將end[j]的前j個(gè)元素調(diào)整成最大堆。　　在編程過程中如遇難題可對(duì)其題目進(jìn)行認(rèn)真分析，然后參考課本或者其

51、他資料已現(xiàn)有代碼亦或聞詢他人幫助，在自己查詢或者問詢他人過程中也是自己學(xué)習(xí)的過程，可以從中學(xué)習(xí)到很多知識(shí)。　　用戶使用說明　　程序運(yùn)行后會(huì)自動(dòng)跳出10~20個(gè)隨機(jī)頂點(diǎn)作為各個(gè)城市，同時(shí)隨機(jī)生成25~50的權(quán)值x，并生成此次所有頂點(diǎn)及其權(quán)值構(gòu)成的最小生成樹。

52、　測(cè)試結(jié)果　　1.生成0-12共13個(gè)頂點(diǎn)：　　2.生成最小生成樹為：　　程序隨機(jī)自動(dòng)生成介于10~20之間個(gè)頂點(diǎn)正確運(yùn)行，隨機(jī)自動(dòng)生成介于25~50之間權(quán)值正確運(yùn)行，使得任意兩頂點(diǎn)之間權(quán)值于25~50之間；經(jīng)驗(yàn)證該生成樹為最小生成樹，程序運(yùn)行正確。

53、　最小生成樹定義：設(shè)G是一個(gè)帶權(quán)連通無向圖，w（e）是邊e上的權(quán)，T是G的生成樹，T中各邊的權(quán)值之和稱為生成樹T的權(quán)值或者代價(jià)（cost）。權(quán)值最小的生成樹稱之為最小生成樹（minimum cost spanning tree），簡(jiǎn)稱最小生成樹。　　八、附錄：程序設(shè)計(jì)源代碼　　package tree;　　pub

54、lic class sort {　　public static void sift(edge a[], int root, int limit)　　{　　int i = root;　　int j = i*2+1;//j為i的左孩子&l

55、t;/p>　　while (j <= limit) //沿較小值孩子節(jié)點(diǎn)向下篩選　　{　　if (j < limit && a[j].getValue() < a[j + 1].getValue())//數(shù)組元素比較

56、;　　{　　j++;//j為左右孩子的較小者　　}　　if (a[j].getValue() > a[i].getValue()) //若父親節(jié)點(diǎn)值較大　　{</b&

57、gt;　　edge e = a[i];//孩子節(jié)點(diǎn)中較小值上移　　a[i] = a[j];　　a[j] = e;　　i = j;　　j = i * 2 +

58、 1;//i、j向下一層　　}　　else{　　break; //跳出循環(huán)　　}　　}<

59、/b>　　}　　public static void sort(edge data[]){　　int length = data.length;　　for(int i = length/2-1; i>=0; i--)//創(chuàng)

60、建最大堆　　{　　sift(data, i, length-1);　　}　　for (int j = length - 1; j > 0; j--)//每趟把最大值交換到后面字，再生成堆&l

61、t;/p>　　{　　edge e = data[0];　　data[0] = data[j];　　data[j] = e;　　sift(data, 0, j-1);

62、　　}　　}　　}　　package tree;　　public class edge {　　private int

63、 start, end, value;//定義開始、結(jié)束、權(quán)值　　public edge(int start,int end,int value){　　this.start=start;　　this.end=end;　　this.value=value;

64、;　　}　　public int getStart() {　　return start;　　}　　public void setStart(int start) {</

65、p>　　this.start = start;　　}　　public int getEnd() {　　return end;　　}<p&g

66、t;　　public void setEnd(int end) {　　this.end = end;　　}　　public int getValue() {　　return value;<

67、;b>　　}　　public void setValue(int value) {　　this.value = value;　　}　　}<p

68、>　　package tree;　　public class main 　　{　　public static void main(String args[])　　{&

69、lt;p>　　int vertexNumber=(int)((Math.random()+1)*10);　　System.out.println("隨機(jī)生成"+vertexNumber+"個(gè)頂點(diǎn)");　　edge edges[]=new edge[vertexNumber*(vertexNumber-1)/2

70、];　　for(int row=0, index=0; row<vertexNumber; row++)　　{//row行、column列、index數(shù)組　　for(int column=0; column<row; column++)　　{

71、　　int x=(int)((Math.random()+1)*25);//random隨機(jī)的　　edges[index] = new edge(row, column, x);　　System.out.println("頂點(diǎn)"+row+"和"+colu

72、mn+"之間的距離為"+x);　　index++;　　}　　}　　sort.sort(edges);//對(duì)數(shù)組 edges[]中的值進(jìn)行堆

73、排序　　int a[] = new int[vertexNumber];　　for(int i = 0; i<a.length; i++)　　//初始時(shí)刻，所有頂點(diǎn)的連通分量編號(hào)為-1，表示所有頂點(diǎn)都屬于一個(gè)獨(dú)立的連通分量　　{

74、　　a[i] = -1;//a[i]的值表示第i個(gè)頂點(diǎn)所屬的連通分量編號(hào)　　}　　//該數(shù)組用于記錄最小生成樹　　edge result[] = new edge[vertexNumber-1];<p&

75、gt;　　int temp = 0;　　for(edge e : edges){　　int start = e.getStart();　　int end = e.getEnd();　　if(a[start]==a[end] && a[end]==-1)//

76、只要將要加入result[]的edges的兩個(gè)頂點(diǎn)相等都為-1，　　//說明不和result[]中的已經(jīng)加入的聯(lián)通分量有關(guān)系，則可以直接加入result[]。　　{　　a[start] = a[end] = temp;　　result

77、[temp] = e;　　temp++;　　}　　else if (a[start] != a[end]) 　　{

78、　if (a[start] == -1) 　　//start=-1為懸空頂點(diǎn)，那么就讓start=end，使加入的連通分量和其連接的result[]中連通分量的標(biāo)識(shí)統(tǒng)一。　　{　　a[start] = a[end];

79、　　}　　else if (a[end] == -1) 　　//end=-1為懸空頂點(diǎn)，那么就讓end=start，使加入的連通分量和其連接的result[]中連通分量的標(biāo)識(shí)統(tǒng)一。　　{　　a[end] = a[s

80、tart];　　}　　else {　　int t = a[start];　　for (int i = 0; i < vertexNumber; i++) <p&

81、gt;　　//要加入的edges使得result中的兩個(gè)不同的連通分量連接起來，需將一個(gè)和另外一個(gè)進(jìn)行統(tǒng)一　　//遍歷所有的頂點(diǎn)如果值和start相等就都等于end，則兩個(gè)連通分量進(jìn)行了統(tǒng)一　　{　　if (a[i] == t) &l

82、t;b>　　{　　a[i] = a[end];　　}　　}　　}　　result[temp

83、] = e;//得到了result[]　　temp++;　　}　　//System.out.println("------------");　　//System.out.pri

84、ntln(Arrays.toString(a));　　if(temp == vertexNumber-1)　　{　　break;　　}

85、　　}　　System.out.println("最小生成樹為：");　　for(edge e : result)　　{　　System.out.printl

86、n("連接頂點(diǎn)"+e.getStart()+"和"+e.getEnd()+"該邊的權(quán)值為"+e.getValue());　　}　　}　　}&

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)java--最小生成樹

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)java--最小生成樹

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載