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

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

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

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

4、權(quán)值最小的邊，檢查其加入到最小生成樹中是否會(huì)構(gòu)成 回路，若是，則此邊不加入生成樹；否則，加入到生成樹中，計(jì)數(shù)器E累加1。c.從E中刪除此最小邊，轉(zhuǎn)b繼續(xù)執(zhí)行，直到k=n-1,算法結(jié)束。判斷是否回路：設(shè)置集合S,其中存放已加入到生成樹中的邊所連接的頂點(diǎn)集合，當(dāng)一條新 的邊要加入到生成樹中時(shí)，檢查此邊所連接的兩個(gè)頂點(diǎn)是否都已經(jīng)在 S中，若是, 則表示構(gòu)成回路，否則，若有一個(gè)頂點(diǎn)不在 S中或者兩個(gè)頂點(diǎn)都不在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)成最小生成樹的邊添加到一個(gè)集合void Krushal( )/克魯斯算法求最小生成樹/*菜單函數(shù)*/int menu() int m;printf("2015年 7 月 2 日nn");printf("求最小生成樹n");printf("nn");printf("1輸入城市之間的信息n");printf("2判斷

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

7、nt x)if(x != prex)prex = find(prex);return prex;/*將這兩個(gè)數(shù)添加到一個(gè)集合里去*/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; /*先把所有城市之間的路段看成一個(gè)邊*/for(i=1;i<=k;i+)/*把所有的邊按從小到大進(jìn)行排序*/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)/*如果這兩點(diǎn)連接在一起不構(gòu)成一個(gè)回路，則 執(zhí)行下面操作*/printf("t 第 d 條路段為：d-%d,權(quán)值為 dn",+ count,pi.str,pi.end,pi.dis);/*將這條邊的起點(diǎn)、終點(diǎn)打印出來*/ans+= pi.dis; /*說明這條路段要用*/Union(pi.str,pi.end);printf("t遍歷所有城市得到最小生成樹的代價(jià)為：%dnn",ans);/*輸入城市信息*/void create()int i,j；printf("請(qǐng)輸入城市的個(gè)數(shù)(1 30) :n&

10、quot;);scanf("%d",&n);if(n<=0|n>30) printf("輸入錯(cuò)誤，t#重新輸入 n");return ; printf("輸入個(gè)城市存儲(chǔ)邊(帶權(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("輸入錯(cuò)誤，請(qǐng)重新輸入n");ret

11、urn ;for(i=0;i<n;i+)for(j=0;j<i;j+)if(arcsij!=arcsji)/* 判斷矩陣是否對(duì)稱 */printf("輸入錯(cuò)誤，請(qǐng)重新輸入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 最近的頂點(diǎn)，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("輸入錯(cuò)誤，請(qǐng)重新選擇。n");break;4 .調(diào)試分析本課程設(shè)計(jì)重點(diǎn)在于生成最小生成樹算法?？唆斔箍査惴▽D中邊按其權(quán)值由小到大的次序順序選取，若選邊后不形成回路，則保留作為一條邊，若形成回 路則除去，依次選夠（n-1）條邊，即得最小生成樹。在克魯斯卡爾算法中，圖的存 貯結(jié)構(gòu)采用邊集數(shù)組，且權(quán)值相等的邊在數(shù)組中排列次序可以是任意的，該方法 對(duì)于邊相對(duì)比較多的不是很實(shí)用。本課程設(shè)計(jì)為求最小生成樹，先要構(gòu)造一個(gè)結(jié)構(gòu)體，再用鄰接

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

16、MAX_LNT 30typedef struct node /*構(gòu)造一個(gè)結(jié)構(gòu)體，兩個(gè)城市可以看成起點(diǎn)和終點(diǎn)，之間的道 路可以看成一個(gè)邊*/int str; /* 起點(diǎn) */int end; /* 終點(diǎn)*/int dis;/* 品E 離*/node;node pmax,temp; /*p 記錄城市信息 */int pre100,rank100;/*用于判斷是否構(gòu)成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市個(gè)數(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)成一個(gè)最小生成樹n");printf("3遍歷所有城市生成最小生成樹n");printf("0 退出 n");printf("nn");printf("請(qǐng)輸入所選功能0-3n");scanf("%d",&m);if(m<0|m>3) return 4;return

18、m;/*下面三個(gè)函數(shù)作用是檢驗(yàn)當(dāng)一條邊添加進(jìn)去，是否會(huì)產(chǎn)生回路*/void set(int x)/* 初始化 */prex = x;rankx = 0;int find(int x)/*找到這個(gè)點(diǎn)的祖先*/if(x != prex)prex = find(prex);return prex;void Union(int x,int y)/*將這兩個(gè)添加到一個(gè)集合里去 */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;/*先把所有城市之間的路段看成一個(gè)邊*/for(i=1;i<=k;i+)/*把所有的邊按從小到大進(jìn)行排序*/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)/*如果這兩點(diǎn)連接在一起不構(gòu)成一個(gè)回路，則 執(zhí)行下面操作*/printf("t 第 d 條路段為：d-%d,權(quán)值為 dn",+ count,pi.str,pi.end,pi.dis);/*將這條邊的起點(diǎn)、終點(diǎn)打印出來*/ans+= pi.dis; /*說明這條路段要用*/Union(pi.str,pi.end);printf("

21、t遍歷所有城市得到最小生成樹的代價(jià)為：%dnn",ans);/*輸入城市信息*/void create()int i,j；printf("請(qǐng)輸入城市的個(gè)數(shù)(1 30) :n");scanf("%d",&n);if(n<=0|n>30) printf("輸入錯(cuò)誤，t#重新輸入 n");return ; printf("輸入個(gè)城市存儲(chǔ)邊(帶權(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("輸入錯(cuò)誤，請(qǐng)重新輸入n");return ;for(i=0;i<n;i+)for(j=0;j<i;j+)if(arcsij!=arcsji)/* 判斷矩陣是否對(duì)稱 */printf("輸入錯(cuò)誤，請(qǐng)重新輸入n");return ;/*顯示生成的最小生成樹*/void display()if(n = 0)printf("這里沒有城市之間的信息n");return;printf("遍歷所有城市得到最小生成樹為：nnn");Kruskal();/*判斷是否能夠生成最小生成樹*/void judge()in