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

1、課程設(shè)計(jì)課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)學(xué)院專(zhuān)業(yè)班級(jí)學(xué)號(hào)學(xué)生姓名指導(dǎo)教師2015年7月2日1.需求分析題目：最小生成樹(shù)問(wèn)題若要在n個(gè)城市之間建設(shè)通訊網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通訊網(wǎng)，是一個(gè)網(wǎng)的最小生成樹(shù)問(wèn)題。要求：(1)利用克魯斯卡爾算法求網(wǎng)的最小生成樹(shù)。(2)實(shí)現(xiàn)并查集。以此表示構(gòu)造生成樹(shù)過(guò)程中的連通分量。(3)以文本形式輸出生成樹(shù)中各條邊以及他們的權(quán)值。輸入的形式和輸入值的范圍：十進(jìn)制數(shù)，0100。輸出的形式：十進(jìn)制數(shù)。程序所能達(dá)到的功能：遍歷所有城市生成最小生成樹(shù)。測(cè)試數(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遍歷所有城市得到最小生成樹(shù)的代價(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ù)類(lèi)型定義如下：typedef struct nodeint str; /* 起點(diǎn)*/int end; /* 終點(diǎn)*/int dis;/* 距離*/node;node pmax,temp; /*p 記錄城市信息 */int pre100,rank100;/*用于判斷是否構(gòu)成回路*/權(quán)值*/主程序流程如下輸入城市信息求最小生或樹(shù)初始化將最小生成樹(shù)邊集合打印出最小生成樹(shù)的權(quán)值與最小生

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

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

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

6、是否能構(gòu)成一個(gè)最小生成樹(shù)n");printf("3遍歷所有城市生成最小生成樹(shù)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;/*克魯斯算法求最小生成樹(shù)*/void Kruskal()int ans = 0,i,j,k = 0; /*ans用來(lái)記錄生成最小樹(shù)的權(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)打印出來(lái)*/ans+= pi.dis; /*說(shuō)明這條路段要用*/Union(pi.str,pi.end);printf("t遍歷所有城市得到最小生成樹(shù)的代價(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ì)稱(chēng) */printf("輸入錯(cuò)誤，請(qǐng)重新輸入n");return ;/*顯示生成的最小生成樹(shù)*/void display( )if(n = 0)printf("這里沒(méi)有城市之間的信息n");return;printf("遍歷所有城市得到最小生成樹(shù)為：nnn");Kruskal();/*判斷是否能夠生成最小生成樹(shù)*/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)成最小生成樹(shù) n");elseprintf("能構(gòu)成最小生成樹(shù)n");/*主函數(shù)*/void main()while(1)switch( menu()case 1:create( );break;/輸入城市信息*/case 2:judge( );break;/*R斷是否能夠生成最

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

15、矩陣的形式表 現(xiàn)出來(lái)。城市間的距離網(wǎng)使用鄰接矩陣表示，鄰接矩陣存儲(chǔ)方法（數(shù)組存儲(chǔ)方法）， 利用兩個(gè)數(shù)組來(lái)存儲(chǔ)一個(gè)圖。用a i j數(shù)組，利用鄰接矩陣方式來(lái)儲(chǔ)存城市與城 市間信息。5 .用戶(hù)使用說(shuō)明按順序依次輸入城市之間的信息，判斷是否能構(gòu)成一個(gè)最小生成樹(shù)，再生成 遍歷所有城市的最小生成樹(shù)。如果輸入過(guò)程中出現(xiàn)錯(cuò)誤，需重新輸入。城市存儲(chǔ) 邊（帶權(quán)）矩陣中的8用100表示，矩陣必須對(duì)稱(chēng)。6 .測(cè)試結(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("求最小生成樹(shù)n");printf("nn");printf("1輸入城市之間的信息n");printf("2判斷是否能構(gòu)成一個(gè)最小生成樹(shù)n");printf("3遍歷所有城市生成最小生成樹(shù)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;/*克魯斯算法求最小生成樹(shù)*/void Kruskal()int ans

19、= 0,i,j,k = 0; /*ans用來(lái)記錄生成最小樹(shù)的權(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)打印出來(lái)*/ans+= pi.dis; /*說(shuō)明這條路段要用*/Union(pi.str,pi.end);printf("

21、t遍歷所有城市得到最小生成樹(shù)的代價(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ì)稱(chēng) */printf("輸入錯(cuò)誤，請(qǐng)重新輸入n");return ;/*顯示生成的最小生成樹(shù)*/void display()if(n = 0)printf("這里沒(méi)有城市之間的信息n");return;printf("遍歷所有城市得到最小生成樹(shù)為：nnn");Kruskal();/*判斷是否能夠生成最小生成樹(shù)*/void judge()in