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

1、數(shù)據(jù)結(jié)構(gòu)期末課程設(shè)計(jì)題目第8題：最小生成樹問(wèn)題 TOC o 1-5 h z 學(xué)院專業(yè)班別學(xué)號(hào)姓名陳聰2015年7月6日一、需求分析1、問(wèn)題描述若要在n個(gè)城市之間建設(shè)通訊網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最 低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通訊網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問(wèn)題。2、基本要求（1）利用克魯斯卡爾算法求網(wǎng)的最小生成樹。（2）實(shí)現(xiàn)并查集。以此表示構(gòu)造生成樹過(guò)程中的連通分量。（3）以文本形式輸出生成樹中各條邊以及他們的權(quán)值。3、實(shí)現(xiàn)提示通訊線路一旦建立，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無(wú)向 網(wǎng)。設(shè)圖的頂點(diǎn)數(shù)不超過(guò)30個(gè)，并為簡(jiǎn)單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的 整數(shù)，可利用C語(yǔ)言提供

2、的隨機(jī)數(shù)函數(shù)產(chǎn)生。圖的存儲(chǔ)結(jié)構(gòu)的選取應(yīng)和所作操作向適應(yīng)。為了便于選擇權(quán)值最小的邊，此 題的存儲(chǔ)結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲(chǔ)邊 （帶權(quán)）的數(shù)組即邊集數(shù)組表示圖。二、詳細(xì)設(shè)計(jì)根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊，分別是：圖的存儲(chǔ)結(jié)構(gòu)，并查 集的實(shí)現(xiàn)，克魯斯卡爾算法的實(shí)現(xiàn)。1、邊集數(shù)組的類型定義：typedef structint x, y;int w;edge;x表示起點(diǎn)，y表示終點(diǎn)，w為權(quán)值。2、并查集功能的實(shí)現(xiàn)由以下函數(shù)實(shí)現(xiàn)：Make_Set（int x）初始化集合；Find_Set（int x）查找x元素所在的集合，回溯時(shí)壓縮路徑； Union（int

3、x, int y, int可）合并x,y所在的集合。3、克魯斯卡爾算法的實(shí)現(xiàn)該算法的實(shí)現(xiàn)位于主函數(shù)中：qsort(e, n, sizeof(edge), cmp);將邊排序printf(最小生成樹的各條邊及權(quán)值為：n);for (i = 0; i n; i+)x = Find_Set(ei.x);y = Find_Set(ei.y);if (x != y )printf(%c - %c : %dn, ei.x + A, ei.y + A, ei.w);Union(x, y, ei.w);4、設(shè)計(jì)中還包含以下函數(shù)：/*比較函數(shù)，按權(quán)值(相同則按x坐標(biāo))非降序排序*/int cmp(const v

4、oid *a, const void *b)if (*(edge *)a).w = (*(edge *)b).w)return (*(edge *)a).x - (*(edge *)b).x;return (*(edge *)a).w - (*(edge *)b).w;快排函數(shù)qsort,包含在stdlib.h頭文件里qsort(e, n, sizeof(edge), cmp);C語(yǔ)言提供的隨機(jī)數(shù)函數(shù)srand( unsigned int seed );使用隨機(jī)數(shù)函數(shù)如下：srand( (unsigned)time( NULL );for( i = 0; i n;i+ )ei.w=rand()

5、%100+1;ei.x = chx - A;if(chy=h+48) chx+;ei.y = (chy+) - A;if(chy=h+49) chy=chx+1;Make_Set (i);輸出1100之間的隨機(jī)數(shù)，使用rand()%100+1。5、主程序的流程圖一、開始（結(jié)束）三、調(diào)試分析調(diào)試過(guò)程中遇到的問(wèn)題：隨機(jī)產(chǎn)生權(quán)值時(shí)，通過(guò)邊數(shù)不能確定起點(diǎn)和終點(diǎn)。解決：通過(guò)頂點(diǎn)數(shù)對(duì)所有邊取隨機(jī)數(shù)。四、用戶使用說(shuō)明及測(cè)試結(jié)果1、打開界面：r最小生成樹問(wèn)題:人為輸入權(quán)值請(qǐng)輸入1,隨機(jī)生成權(quán)值請(qǐng)輸入的:（1）人為輸入權(quán)值，輸入1,回車:尹最小生成樹可題:，為輸入權(quán)值請(qǐng)輸入上，隨機(jī)生成權(quán)值請(qǐng)輸入。:請(qǐng)輸入邊的條

6、數(shù)（小于436）:輸入7，回車:最刁生成權(quán)寸問(wèn)題=人為輸入權(quán)值請(qǐng)輸入L隨機(jī)生成枳直請(qǐng)輸入觸:1請(qǐng)輸入邊的條數(shù)（小于理非）=請(qǐng)輸入邊的信息.起點(diǎn)n袈點(diǎn)n枳值Sm.）分別用空格隅升二輸入邊的信息及結(jié)果如下:最小生成樹問(wèn)題:，為輸入權(quán)值請(qǐng)輸入，隨機(jī)生成權(quán)值請(qǐng)輸入& ：輸入邊的條數(shù)（小于436）:帝輸入邊的信息（起點(diǎn)，終點(diǎn)，權(quán)值106）分別用空格隔開:k b 3k d 8k e 10b d 6d e 9b c 15L e 12快小生成樹的各條邊及權(quán)值為：a b ： 3b - d ： 6fl - e ： 9c e ： 12Process exited uitli return value 0 Press

7、 any key to continue . . . H（2）隨機(jī)生成權(quán)值，輸入0：五、經(jīng)驗(yàn)和體會(huì)通過(guò)本次課程設(shè)計(jì)，我學(xué)會(huì)了利用克魯斯卡爾算法求最小生成樹。另外學(xué)會(huì)了利 用隨機(jī)函數(shù)產(chǎn)生隨機(jī)數(shù)，以及課本沒有提到的邊集數(shù)組的定義和使用。六、附錄源代碼#include #include #include time.h#define MAX 435 /*定義邊(x,y)，權(quán)為w */ typedef structint x, y;int w;edge;edge eMAX;/* rankx表示x的秩*/int rankMAX;/* fatherx表示x的父節(jié)點(diǎn)*/int fatherMAX;/*比較函數(shù)

8、，按權(quán)值(相同則按x坐標(biāo))非降序排序*/int cmp(const void *a, const void *b)if (*(edge *)a).w = (*(edge *)b).w)return (*(edge *)a).x - (*(edge *)b).x;return (*(edge *)a).w - (*(edge *)b).w;/*初始化集合*/void Make_Set(int x)fatherx = x;rankx = 0;/*查找x元素所在的集合，回溯時(shí)壓縮路徑*/int Find_Set(int x)while(fatherx)x=fatherx;return x;/*合并x

9、,y所在的集合*/void Union(int x, int y, int w)if (x = y) return;/*將秩較小的樹連接到秩較大的樹后*/if (rankx ranky)fathery = x;elseif (rankx = ranky)ranky+;fatherx = y;/*主函數(shù)*/int main()printf(*最小生成樹問(wèn)題：n);int i, n,h,k=0;int x, y;char chx, chy;printf(n人為輸入權(quán)值請(qǐng)輸入1,隨機(jī)生成權(quán)值請(qǐng)輸入0： n);scanf(%d,&k);if(k=1)/*讀取邊的數(shù)目*/printf(請(qǐng)輸入邊的條數(shù)(小

10、于436):n);scanf(%d”, &n);getchar();/*讀取邊信息并初始化集合*/printf(請(qǐng)輸入邊的信息(起點(diǎn)，終點(diǎn)，權(quán)值(100)分別用空格隔開:n);for (i = 0; i n; i+)scanf(%c %c %d”, &chx, &chy, &ei.w);getchar();ei.x = chx - A;ei.y = chy - A;Make_Set(i);elseprintf(請(qǐng)輸入頂點(diǎn)數(shù)(=30):n);scanf(%d”, &h);getchar();srand( (unsigned)time( NULL );n=(h-1)*h/2;chx=49;chy=50;for( i = 0; i n;i+ )ei.w=rand()%100+1;ei.x = chx - A;if(chy=h+48) chx+;ei.y = (chy+) - A;if(chy=h+49) chy=chx+1;Make_Set(i);printf(隨機(jī)生成的各條邊及權(quán)值為：n);for (i = 0; i n; i+)printf(%c - %c : %dn, ei.x + A, ei.y + A, ei.w);/*將邊排序*/qsort(e, n, sizeof(edge), cmp