大數據結構課程設計-最小生成樹

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

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

3、x, int y, int可）合并x,y所在的集合。3、克魯斯卡爾算法的實現該算法的實現位于主函數中：qsort(e, n, sizeof(edge), cmp);將邊排序printf(最小生成樹的各條邊及權值為：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、設計中還包含以下函數：/*比較函數，按權值(相同則按x坐標)非降序排序*/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;快排函數qsort,包含在stdlib.h頭文件里qsort(e, n, sizeof(edge), cmp);C語言提供的隨機數函數srand( unsigned int seed );使用隨機數函數如下：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之間的隨機數，使用rand()%100+1。5、主程序的流程圖一、開始（結束）三、調試分析調試過程中遇到的問題：隨機產生權值時，通過邊數不能確定起點和終點。解決：通過頂點數對所有邊取隨機數。四、用戶使用說明及測試結果1、打開界面：r最小生成樹問題:人為輸入權值請輸入1,隨機生成權值請輸入的:（1）人為輸入權值，輸入1,回車:尹最小生成樹可題:，為輸入權值請輸入上，隨機生成權值請輸入。:請輸入邊的條

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

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

8、，按權值(相同則按x坐標)非降序排序*/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元素所在的集合，回溯時壓縮路徑*/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;/*主函數*/int main()printf(*最小生成樹問題：n);int i, n,h,k=0;int x, y;char chx, chy;printf(n人為輸入權值請輸入1,隨機生成權值請輸入0： n);scanf(%d,&k);if(k=1)/*讀取邊的數目*/printf(請輸入邊的條數(小

10、于436):n);scanf(%d”, &n);getchar();/*讀取邊信息并初始化集合*/printf(請輸入邊的信息(起點，終點，權值(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(請輸入頂點數(=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(隨機生成的各條邊及權值為：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