(完整word版)廣工數(shù)據(jù)結(jié)構(gòu)課程設計最小生成樹(word文檔良心出品)

1、課程設計課程名稱數(shù)據(jù)結(jié)構(gòu)學院專業(yè)班級學號學生姓名指導教師2015年7月2日1.需求分析題目：最小生成樹問題若要在n個城市之間建設通訊網(wǎng)絡，只需要架設n-1條線路即可。如何以最低的經(jīng)濟代價建設這個通訊網(wǎng)，是一個網(wǎng)的最小生成樹問題。要求：(1)利用克魯斯卡爾算法求網(wǎng)的最小生成樹。(2)實現(xiàn)并查集。以此表示構(gòu)造生成樹過程中的連通分量。(3)以文本形式輸出生成樹中各條邊以及他們的權(quán)值。輸入的形式和輸入值的范圍：十進制數(shù)，0100。輸出的形式：十進制數(shù)。程序所能達到的功能：遍歷所有城市生成最小生成樹。測試數(shù)據(jù)：正確數(shù)據(jù)：城市個數(shù)3; 3個城市的鄰接矩陣：(1,2,3;2,100,4;3,4,6)輸出結(jié)果

2、：第1條路段為12,權(quán)值為2第2條路段為13,權(quán)值為3遍歷所有城市得到最小生成樹的代價為：5錯誤數(shù)據(jù)：城市個數(shù)3;城市的鄰接矩陣：(-2,5,1;3,0,1;3,2,1) 輸出結(jié)果：輸入錯誤，請重新輸入2 .概要設計數(shù)據(jù)類型定義如下：typedef struct nodeint str; /* 起點*/int end; /* 終點*/int dis;/* 距離*/node;node pmax,temp; /*p 記錄城市信息 */int pre100,rank100;/*用于判斷是否構(gòu)成回路*/權(quán)值*/主程序流程如下輸入城市信息求最小生或樹初始化將最小生成樹邊集合打印出最小生成樹的權(quán)值與最小生

3、成樹的代價int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市個數(shù)，arcs叩記錄城市問3 .詳細設計(1)克魯斯卡爾算法思想基本描述：假設連通圖N= (V, E),則令最小生成樹的初始狀態(tài)為只有 n頂點而無 邊的非連通圖T=(V, ),圖中每個頂點自成一個連通分量。在 E中選擇代價最 小的邊，若該邊依附的頂點落在 T中不同的連通分量上，則將此邊加入到 T中, 否則舍去此邊而選擇下一條代價最小的邊。以此類推，直至 T中所有頂點都在 同一個連通分量上為止。(2)克魯斯卡爾算法設計：a.設置計數(shù)器E,初值為0,記錄已選中的邊數(shù)。將所有邊從小到大排序， 存于p口中。b.從p中選擇一條

4、權(quán)值最小的邊，檢查其加入到最小生成樹中是否會構(gòu)成 回路，若是，則此邊不加入生成樹；否則，加入到生成樹中，計數(shù)器E累加1。c.從E中刪除此最小邊，轉(zhuǎn)b繼續(xù)執(zhí)行，直到k=n-1,算法結(jié)束。判斷是否回路：設置集合S,其中存放已加入到生成樹中的邊所連接的頂點集合，當一條新 的邊要加入到生成樹中時，檢查此邊所連接的兩個頂點是否都已經(jīng)在 S中，若是, 則表示構(gòu)成回路，否則，若有一個頂點不在 S中或者兩個頂點都不在S中，則 不夠成回路。/*需要的函數(shù)聲明*/int main ( )/主程序int menu ( )/煤單函數(shù)void create ( )/#俞入城市信息函數(shù)void judge ( )/判斷是

5、否能夠生成最小生成樹函數(shù)void display()打印輸出void set ( )/初始化 pre,rank函數(shù)void find () 判斷是否構(gòu)成回路函數(shù)void Union ( )/將能構(gòu)成最小生成樹的邊添加到一個集合void Krushal( )/克魯斯算法求最小生成樹/*菜單函數(shù)*/int menu() int m;printf("2015年 7 月 2 日nn");printf("求最小生成樹n");printf("nn");printf("1輸入城市之間的信息n");printf("2判斷

6、是否能構(gòu)成一個最小生成樹n");printf("3遍歷所有城市生成最小生成樹n");printf("0 退出 n");printf("nn");printf("請輸入所選功能0-3n");scanf("%d",&m);if(m<0|m>3) return 4;return m;/*下面三個函數(shù)作用是檢驗當一條邊添加進去，是否會產(chǎn)生回路*/void set(int x)/* 初始化 */prex = x;rankx = 0;/*找到這個點的祖先*/int find(i

7、nt x)if(x != prex)prex = find(prex);return prex;/*將這兩個數(shù)添加到一個集合里去*/void Union(int x,int y)x = find(x);y = find(y);if(rankx >= ranky)prey = x;rankx +;else prey = x;/*克魯斯算法求最小生成樹*/void Kruskal()int ans = 0,i,j,k = 0; /*ans用來記錄生成最小樹的權(quán)總值*/ int index;int count = 0;/*記錄打印邊的條數(shù)*/for(i = 1;i <= n;i +)/*

8、初始化數(shù)組 prex,rankx*/set(i);for(i = 1;i <= n;i +)for(j = i + 1;j <= n;j +)p+k.str = i;pk.end = j;pk.dis = arcsij; /*先把所有城市之間的路段看成一個邊*/for(i=1;i<=k;i+)/*把所有的邊按從小到大進行排序*/index=i;for(j=i+1;j<=k;j+) if(pj.dis <pindex.dis) index=j;temp=pindex;pindex=pi;pi=temp;for(i = 1;i <= k;i +)if(find(

9、pi.str) != find(pi.end)/*如果這兩點連接在一起不構(gòu)成一個回路，則 執(zhí)行下面操作*/printf("t 第 d 條路段為：d-%d,權(quán)值為 dn",+ count,pi.str,pi.end,pi.dis);/*將這條邊的起點、終點打印出來*/ans+= pi.dis; /*說明這條路段要用*/Union(pi.str,pi.end);printf("t遍歷所有城市得到最小生成樹的代價為：%dnn",ans);/*輸入城市信息*/void create()int i,j；printf("請輸入城市的個數(shù)(1 30) :n&

10、quot;);scanf("%d",&n);if(n<=0|n>30) printf("輸入錯誤，t#重新輸入 n");return ; printf("輸入個城市存儲邊(帶權(quán))的數(shù)組(數(shù)值范圍：1-99, 用100表示，)：n",n)；for(i = 1;i <= n;i +)for(j = 1;j <= n;j +)scanf("%d”,&arcsij);if(arcsij<1|arcsij>100)printf("輸入錯誤，請重新輸入n");ret

11、urn ;for(i=0;i<n;i+)for(j=0;j<i;j+)if(arcsij!=arcsji)/* 判斷矩陣是否對稱 */printf("輸入錯誤，請重新輸入n");return ;/*顯示生成的最小生成樹*/void display( )if(n = 0)printf("這里沒有城市之間的信息n");return;printf("遍歷所有城市得到最小生成樹為：nnn");Kruskal();/*判斷是否能夠生成最小生成樹*/void judge()int close100,low100,i,j,ans = 0

12、;/*closej表示離 j 最近的頂點，lowj表示離 j 最短的距離*/int use100;use1 = 1;for(i = 2;i <= n;i +)lowi = arcs1i; /* 初始化 */closei = 1;usei = 0;for(i = 1;i < n;i +)int min = 100000000,k = 0;for(j = 2;j <= n;j +)if(usej = 0 && min > lowj)/* 找到最小的 low口 值，并記錄*/min = lowj;k = j;for(j = 2;j <= n;j +)if

13、(usej = 0 && lowj > arcskj)lowj = arcskj; /* 修改 low口 值和 close值*/closej = k;ans += arcsclosekk;if(ans >= 100000000) printf("不能構(gòu)成最小生成樹 n");elseprintf("能構(gòu)成最小生成樹n");/*主函數(shù)*/void main()while(1)switch( menu()case 1:create( );break;/輸入城市信息*/case 2:judge( );break;/*R斷是否能夠生成最

14、小生成樹 */case 3:display( );break;/*顯示生成的最小生成樹*/case 0:exit();default:printf("輸入錯誤，請重新選擇。n");break;4 .調(diào)試分析本課程設計重點在于生成最小生成樹算法?？唆斔箍査惴▽D中邊按其權(quán)值由小到大的次序順序選取，若選邊后不形成回路，則保留作為一條邊，若形成回 路則除去，依次選夠（n-1）條邊，即得最小生成樹。在克魯斯卡爾算法中，圖的存 貯結(jié)構(gòu)采用邊集數(shù)組，且權(quán)值相等的邊在數(shù)組中排列次序可以是任意的，該方法 對于邊相對比較多的不是很實用。本課程設計為求最小生成樹，先要構(gòu)造一個結(jié)構(gòu)體，再用鄰接

15、矩陣的形式表 現(xiàn)出來。城市間的距離網(wǎng)使用鄰接矩陣表示，鄰接矩陣存儲方法（數(shù)組存儲方法）， 利用兩個數(shù)組來存儲一個圖。用a i j數(shù)組，利用鄰接矩陣方式來儲存城市與城 市間信息。5 .用戶使用說明按順序依次輸入城市之間的信息，判斷是否能構(gòu)成一個最小生成樹，再生成 遍歷所有城市的最小生成樹。如果輸入過程中出現(xiàn)錯誤，需重新輸入。城市存儲 邊（帶權(quán)）矩陣中的8用100表示，矩陣必須對稱。6 .測試結(jié)果7 .源代碼#include<stdio.h>#include <string.h>#include <stdlib.h>#define max 100#define

16、MAX_LNT 30typedef struct node /*構(gòu)造一個結(jié)構(gòu)體，兩個城市可以看成起點和終點，之間的道 路可以看成一個邊*/int str; /* 起點 */int end; /* 終點*/int dis;/* 品E 離*/node;node pmax,temp; /*p 記錄城市信息 */int pre100,rank100;/*用于判斷是否構(gòu)成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市個數(shù)，arcs叩記錄城市間權(quán)值*/int menu( )/* 菜單函數(shù)*/int m;printf("2015年 7 月 2 日nn");p

17、rintf("求最小生成樹n");printf("nn");printf("1輸入城市之間的信息n");printf("2判斷是否能構(gòu)成一個最小生成樹n");printf("3遍歷所有城市生成最小生成樹n");printf("0 退出 n");printf("nn");printf("請輸入所選功能0-3n");scanf("%d",&m);if(m<0|m>3) return 4;return

18、m;/*下面三個函數(shù)作用是檢驗當一條邊添加進去，是否會產(chǎn)生回路*/void set(int x)/* 初始化 */prex = x;rankx = 0;int find(int x)/*找到這個點的祖先*/if(x != prex)prex = find(prex);return prex;void Union(int x,int y)/*將這兩個添加到一個集合里去 */x = find(x);y = find(y);if(rankx >= ranky)prey = x;rankx +;else prey = x;/*克魯斯算法求最小生成樹*/void Kruskal()int ans

19、= 0,i,j,k = 0; /*ans用來記錄生成最小樹的權(quán)總值*/ int index;int count = 0;/*記錄打印邊的條數(shù)*/for(i = 1;i <= n;i +)/*初始化數(shù)組 prex,rankx*/set(i);for(i = 1;i <= n;i +)for(j = i + 1;j <= n;j +)p+k.str = i;pk.end = j;pk.dis = arcsij;/*先把所有城市之間的路段看成一個邊*/for(i=1;i<=k;i+)/*把所有的邊按從小到大進行排序*/index=i;for(j=i+1;j<=k;j+)

20、 if(pj.dis <pindex.dis) index=j;temp=pindex;pindex=pi;pi=temp;for(i = 1;i <= k;i +)if(find(pi.str) != find(pi.end)/*如果這兩點連接在一起不構(gòu)成一個回路，則 執(zhí)行下面操作*/printf("t 第 d 條路段為：d-%d,權(quán)值為 dn",+ count,pi.str,pi.end,pi.dis);/*將這條邊的起點、終點打印出來*/ans+= pi.dis; /*說明這條路段要用*/Union(pi.str,pi.end);printf("

21、t遍歷所有城市得到最小生成樹的代價為：%dnn",ans);/*輸入城市信息*/void create()int i,j；printf("請輸入城市的個數(shù)(1 30) :n");scanf("%d",&n);if(n<=0|n>30) printf("輸入錯誤，t#重新輸入 n");return ; printf("輸入個城市存儲邊(帶權(quán))的數(shù)組(數(shù)值范圍：1-99, 用100表示，)：n",n)；for(i = 1;i <= n;i +)for(j = 1;j <= n;

22、j +)scanf("%d”,&arcsij);if(arcsij<1|arcsij>100)printf("輸入錯誤，請重新輸入n");return ;for(i=0;i<n;i+)for(j=0;j<i;j+)if(arcsij!=arcsji)/* 判斷矩陣是否對稱 */printf("輸入錯誤，請重新輸入n");return ;/*顯示生成的最小生成樹*/void display()if(n = 0)printf("這里沒有城市之間的信息n");return;printf("遍歷所有城市得到最小生成樹為：nnn");Kruskal();/*判斷是否能夠生成最小生成樹*/void judge()in