1、華南農業大學信息學院課程設計實驗學院數 學 與班級14 網工學號201430350114 姓名賴文杰信 息 學1院實驗題設計性綜合性目代碼直觀，有調理，按時完成，獨立完成，實驗報告詳細，還添加了其他功能，不自 過注釋不過詳細，表達能力不好，部分代碼直接照抄網上，總體良好。我評價能夠實現實驗要求的功能 全部部分算法有新意 有一般教程序運行通過 全部部分師算法注釋說明 完善僅有功能說明評接口參數說明 有無語按期上交文檔資料及源程序 所有 部分獨立完成實驗 能不能體現團隊合作精神。 能夠 不能成績實驗題目：并查集班級： 14 網絡工程一班姓名：賴文杰學號： 201430350114完成日期： 201

2、5/9/30一 題目要求 ：1. 實驗的要求：本次實驗題目要求是實現并查集的初始化、合并集合、查找節點所在集合和與并查集相關的應用的實現。2. 并查集的簡介：在一些問題中， 我們需要劃分個不同的元素成若干組， 每一組的元素構成一個集合。這種問題的一個解決辦法是，在開始時，讓每個元素自成一個單元集合，然后按一定順序將屬于同一組的元素所在的集合合并。期間要反復用到查找一個元素屬于哪一個集合的運算。適合于描述這類問題的抽象數據類型稱為并查集(union-find sets)3. 代碼簡介：（1） Find 函數，用來查找某節點所在的集合，需要一個整形參數（節點的編號），返回一個整形值。（所在集合的頭

3、節點的編號）（2） min 函數，用來連接輸入的兩個節點所在的集合，需要兩個整形參數（兩個節點的編號），無返回值。（3） chushihua 函數，用來創建新的并查集，需要兩個整形參數（分別是節點的個數和連接節點的通道的數目），無返回值。（4） count 函數，用來計算并查集含有集合的個數，需要一個整形參數（節點的個數），返回一個整形值。（并查集含有集合的個數）（5） 代碼能實現并查集的創建，初始化，合并集合，查找節點所在集合和計算并查集中所含集合的數目。二 解題思路：1. 創建兩個數組 pre 和 t ， pre 數組下標用于表示節點的編號，數組內容表示節點的上級。 t 用于標記獨立塊的根

4、結點2. 首先定義出主函數的基本框架流程，用while 和 switch 函數來實習功能的選擇3. 由主函數中接收到參數 N、M給 chushihua 函數，然后函數用 for 循環給 pre 數組賦值，使得并查集中每個節點都編好號而且每個節點自己成為一個集合，然后用 mix 函數把需要連接的節點連起來，創建出一個新的并查集。4由主函數中接受到參數 x 給 Find 函數，函數通過對 pre 數組的下標是否和數組的內容相等，從而判斷該節點是否是根節點，找到后根節點的編號返回給主函數。5. 由主函數接受到參數 x，y 給 mix 函數，函數通過 Find 函數分別找到 x 和 y 的根節點，然后

5、通過把 y 所在集合的根節點的數組值改成 x 所在集合根節點的數組下標，從而使得 x 所在集合的根節點成為 y 所在集合的根結點的上級。從而把兩個集合合并。6. 由主函數接受到參數 N給 count 函數，用 for 循環把各個節點遍歷，如果第 i 個節點是根節點，就把第 i 個節點所在的 t 數組的值賦值為 1，否則為 0，然后用 ans 標志 t 數組中 1 的個數。最后把 ans 返回給主函數。該代碼用了線性表的數據結構。三 調試分析：1 代碼演示：生成的并查集圖為：合并后并查集圖為：初始化后并查集的圖：合并后并查集的圖：2. 調試遇到的問題：基本沒遇到什么大問題，只是有很多輸入語句后面

6、沒加分號，輸入語句沒加取地址之類的小錯誤。3. 經驗體會：這是第一次自己在沒有人指點的情況下自己去學習一種數據結構，剛剛開始會覺得可能會很難，抱著恐懼的心情去上網查找資料，不過在找到資料后，認真閱讀了一遍，發現沒有想象中恐怖和困難，挺簡單的，看了幾遍就懂了并查集是什么和并查集的基本操作，覺得自己還是挺厲害的（自夸）。在我們計算機類，自學是很重要的，計算機專業知識更新快，書本上的知識只是基礎而且很微不足道，我們要學會自己查找資料自學，不要恐懼自學，沒試過就不知道難易程度，不要被聽起來很可怕名字嚇到，就像這次，自學了才發現原來并查集沒有自己想象的那么困難。四 相關應用：題目表述：設地圖中有若干做城

7、鎮，每個城鎮可以看作一個點，城鎮間有若干條路，試求還需要多少條路才能使全地圖聯通。輸入格式第一行輸入兩個整數個 n，m，表述有 n 個城鎮，m條路。接下來 m行，每行輸入每條路聯通的城鎮。輸出格式輸出聯通全地圖所需路的條數。輸入樣例5 31 22 34 5輸出樣例1解題代碼：#include <iostream>#include <stdio.h>#include <stdlib.h>int pre1000 ;using namespace std;int find(int x)int r=x;while (prer !=r)r=prer ;int i=x;

8、 int j;while(i!=r)j=prei ;prei =r;i=j;return r;int main()int n,m,p1,p2,i,total,f1,f2;while(scanf("%d",&n) && n)/讀入n，如果 n 為 0，結束剛開始的時候，有 n 個城鎮，一條路都沒有 / 那么要修 n-1 條路才能把它們連起來total=n-1;/ 每個點互相獨立，自成一個集合，從 1 編號到 n / 所以每個點的上級都是自己for(i=1;i<=n;i+) prei =i; / 共有 m條路 scanf("%d"

9、;,&m); while(m-)/ 下面這段代碼，其實就是 join 函數，只是稍作改動以適應題目要求/ 每讀入一條路，看它的端點 p1，p2 是否已經在一個連通分支里了scanf("%d %d",&p1,&p2);f1=find(p1);f2=find(p2);/ 如果是不連通的，那么把這兩個分支連起來/ 分支的總數就減少了 1，還需建的路也就減了 1if(f1!=f2)pref2 =f1; total-;/ 如果兩點已經連通了，那么這條路只是在圖上增加了一個環 / 對連通性沒有任何影響，無視掉/ 最后輸出還要修的路條數 printf("

10、%dn",total);return 0;五 附錄：源代碼：#include<iostream>#include <stdio.h>#include <stdlib.h>#include<cstring>using namespace std;int pre1050;bool t1050;/t用于存儲節點用于標記獨立塊的根結點int Find(int x)/查找節點所在集合int r=x;while(r!=prer)r=prer;int i=x,j;while(prei!=r)j=prei;prei=r;i=j;return r;voi

11、d mix(int x,int y)/int fx=Find(x),fy=Find(y);if(fx!=fy)合并結合prefy=fx;int chushihua(int N,int M)/初始化int a,b,i; /N節點的個數M 連接通道的數目for(i=1;i<=N;i+)prei=i;for(i=1;i<=M;i+)/吸收并整理數據printf(" 輸入第%d條通道連接的兩個個節點： ",i); scanf("%d%d",&a,&b);mix(a,b);int count(int N)/有多少個集合int ans,i

12、;memset(t,0,sizeof(t);for(i=1;i<=N;i+)/標記根結點tFind(i)=1;for(ans=0,i=1;i<=N;i+)if(ti)ans+;return ans;int main()int a,b,c,d,N,M,e,f;printf("首先創建一個并查集 n");printf("輸入并查集的節點個數：");scanf("%d",&N);printf("輸入并查集中連接節點的通道的個數： ");scanf("%d",&M);chus

13、hihua(N,M);printf("創建完畢n");while(d!=0)printf("n 請輸入要執行的功能 n1. 初始化n2. 合并結合n"); printf("3. 找節點所在集合 n4. 并查集中集合的個數n0. 退出nn");scanf("%d",&d);switch(d)case 1:printf("n");printf("輸入并查集的節點個數： ");scanf("%d",&N);printf(" 輸入并查集中

14、連接節點的通道的個數： "); scanf("%d",&M);chushihua(N,M);break;case 2:printf("n");printf("輸入通道連接的兩個個節點： ");scanf("%d%d",&a,&b);mix(a,b);printf("合并成功n");break;case 3:printf("n");while(c!=0)printf(" 請輸入要查找的節點, 輸入 0 退出查找："); scanf("%d",&c);e=Find(