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

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

2、用C語言提供的隨機(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ù)組表示圖。2、 詳細(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(

3、int x, int y, int w)合并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ù)：（1）/* 比較函數(shù)，按權(quán)值(相同則按x坐標(biāo))非降序排序 */

4、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;（2） 快排函數(shù)qsort,包含在stdlib.h頭文件里 qsort(e, n, sizeof(edge), cmp);（3）C語言提供的隨機(jī)數(shù)函數(shù)srand( unsigned int seed );使用隨機(jī)數(shù)函數(shù)如下：srand( (unsigned)time( NULL ) );for( i

5、 = 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); 輸出1100之間的隨機(jī)數(shù)，使用rand()%100+1。開始5、 主程序的流程圖 選擇手動(dòng)或隨機(jī)輸入權(quán)值 輸入頂點(diǎn)數(shù)輸入邊的信息存儲(chǔ)邊的信息隨機(jī)產(chǎn)生權(quán)值并存儲(chǔ)邊升序排序判斷是否回路，不回路則輸出結(jié)束三、調(diào)試分析調(diào)試過程中遇到的問題：隨機(jī)產(chǎn)生權(quán)值時(shí)，通過邊數(shù)不能確定起點(diǎn)和終點(diǎn)。解決：通過頂點(diǎn)數(shù)對(duì)所有邊取隨機(jī)數(shù)。四、用戶使用說明及測試結(jié)果1、打開界面：（1）

6、人為輸入權(quán)值，輸入1，回車：輸入7，回車：輸入邊的信息及結(jié)果如下：（2）隨機(jī)生成權(quán)值，輸入0：輸入頂點(diǎn)數(shù)5，結(jié)果如下：五、經(jīng)驗(yàn)和體會(huì)通過本次課程設(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) */

7、int fatherMAX; /* 比較函數(shù)，按權(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(fat

8、herx)x=fatherx;return x; /* 合并x,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(*最小生成樹問題：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(%

9、d,&k); if(k=1) /* 讀取邊的數(shù)目 */printf(請(qǐng)輸入邊的條數(shù)（小于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( (

10、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); printf(最小生