小白專場-FileTransfer-c語言實現

  • 2019 年 10 月 3 日
  • 筆記

目錄

更新、更全的《數據結構與演算法》的更新網站，更有python、go、人工智慧教學等著你：https://www.cnblogs.com/nickchen121/p/11407287.html

一、集合的簡化表示

在上一節 集合及運算中，我們對集合使用二叉樹表示，如下圖所示：

為了使用二叉樹，我們在上一節中使用以下程式碼，構造二叉樹：

/* c語言實現 */    typedef struct{    ElementType Data;    int Parent;  } SetType;      int Find(SetType S[], ElementType X)  {    // 在數組S中查找值為X的元素所屬的集合    // MaxSize是全局變數，為數組S的最大長度    int i;    for (i = 0; i < MaxSize && S[i].Data != X; i++);    if (i >= MaxSize) return -1; // 未找到X，返回-1    for (; S[i].Parent >= 0; i = S[i].Parent);    return i; // 找到X所屬集合，返回樹根結點在數組S中的下標  }

使用二叉樹構造集合，Find操作在差的情況下時間複雜度可能為(O(n^2))

因此對於任何有限集合的（N個）元素都可以被一一映射為整數 0~N-1。即對於集合 {2, 5, 4, 3} 和 {6, 0, 1} 我們可以使用如下圖所示的數組表示：

對於上述的數組，我們可以使用如下程式碼構造：

/* c語言實現 */    typedef int ElementType;  // 默認元素可以用非負整數表示  typedef int SetName; //默認用根結點的下標作為集合名稱  typedef ElementType SetType[MaxSize];    SetName Find(SetType S, ElementType X)  {    // 默認集合元素全部初始化為-1    for (; S[X] >= 0; X = S[X]);    return X;  }    void Union(SetType S, SetName Root1, SetName Root2)  {    // 這裡默認Root1和Root2是不同集合的根節點    S[Root2] = Root1;  }

二、題意理解

根據輸入樣例，以此來判斷電腦之間有多少個組成，如下圖所示

上圖動態變化如下圖所示：

下圖為五台電腦之間形成全連接狀態，因此看成一個整體：

三、程式框架搭建

/* c語言實現 */    int main()  {    初始化集合;    do {      讀入一條指令;      處理指令;    } while (沒結束);    return 0;  }      int main()  {    SetType S;    int n;    char in;    scanf("%dn", &n);    Initialization(S, n);    do {      scanf("%c", &in);      switch (in) {        case 'I': Input_connection(S); break; // Union(Find)        case 'C': Check_connection(S); break; // Find        case 'S': Check_network(S, n); break; // 數集合的根，判斷電腦網路的組成個數      }    } while (in != 'S');    return 0;  }

3.1 Input_connection

/* c語言實現 */    void Input_connection(SetType S)  {    ElementType u, v;    SetName Root1, Root2;    scanf("%d %dn", &u, &v);    Root1 = Find(S, u-1);    Root2 = Find(S, v-1);    if (Root1 != Root2)      Union(S, Root1, Root2);  }

3.2 Check_connection

/* c語言實現 */    void Check_connection(SetType S)  {    ElementType u, v;    scnaf("%d %dn", &u, &v);    Root1 = Find(S, u-1);    Root2 = Find(S, v-1);    if (Root1 == Root2)      printf("yesn");    else printf("non");  }

3.3 Check_network

/* c語言實現 */    void Check_network(SetType S, int n)  {    int i, counter = 0;    for (i = 0; i < n; i++){      if (S[i] < 0) counter++;    }    if (counter == 1)      printf("The network is connected.n");    else      printf("There are %d components.n", counter);  }

四、pta測試

/* c語言實現 */    typedef int ElementType;  // 默認元素可以用非負整數表示  typedef int SetName; //默認用根結點的下標作為集合名稱  typedef ElementType SetType[MaxSize];    SetName Find(SetType S, ElementType X)  {    // 默認集合元素全部初始化為-1    for (; S[X] >= 0; X = S[X]);    return X;  }    void Union(SetType S, SetName Root1, SetName Root2)  {    // 這裡默認Root1和Root2是不同集合的根節點    S[Root2] = Root1;  }

對於上述的程式碼，如果我們放入pta中測試，會發現測試點6運行超時，如下圖所示：

因此，我們會考慮是不是因為出現了某種情況，導致Root2為根結點的樹過大了，因此我們修改程式碼為：

/* c語言實現 */    typedef int ElementType;  // 默認元素可以用非負整數表示  typedef int SetName; //默認用根結點的下標作為集合名稱  typedef ElementType SetType[MaxSize];    SetName Find(SetType S, ElementType X)  {    // 默認集合元素全部初始化為-1    for (; S[X] >= 0; X = S[X]);    return X;  }    void Union(SetType S, SetName Root1, SetName Root2)  {    // 這裡默認Root1和Root2是不同集合的根節點    // S[Root2] = Root1;    S[Root1] = Root2;  }

發現更換程式碼後，測試點5卻運行超時了，為了解決上述問題，我們可以使用下面將要講到了按秩歸併的思想修改程式碼。

五、按秩歸併

為什麼需要按秩歸併呢？因為我們使用pta測試程式，發現程式碼總是超時，因此我們可以考慮是否出現這種情況——我們再不斷地往一顆樹上累加子樹，如下圖所示：

/* c語言實現 */    Union(Find(2), Find(1));  Union(Find(3), Find(1));  ……;  Union(Find(n), Find(1));

從上圖可以看出，此過程的時間複雜度為：(T(n) = O(n^2))

除了上述這種情況，會導致樹的高度越來越高，如果我們把高樹貼在矮樹上，那麼樹高也會快速增長，因此我們應該考慮把矮樹貼在高數上。

對於上述問題的解決，我們給出以下兩個解決方法，這兩種方法統稱為按秩歸併。

5.1 方法一：樹高替代

為了解決上述問題，我們可以把根結點從-1替代為-樹高，程式碼如下：

/* c語言實現 */    if ( Root2高度 > Root1高度 )      S[Root1] = Root2;  else {    if ( 兩者等高 ) 樹高++;    S[Root2] = Root1;  }      if ( S[Root2] < S[Root1] )      S[Root1] = Root2;  else {    if ( S[Root1]==S[Root2] ) S[Root1]--;    S[Root2] = Root1;  }

5.2 方法二：規模替代

為了解決上述問題，我們也可以把根結點從**-1替代為-元素個數（把小樹貼到大樹上），程式碼如下：

/* c語言實現 */    void Union( SetType S, SetName Root1, SetName Root2 )  {    if ( S[Root2]<S[Root1] ){    S[Root2] += S[Root1];    S[Root1] = Root2;    } else {      S[Root1] += S[Root2];      S[Root2] = Root1;    }  }

六、路徑壓縮

對於上述程式碼超時的問題，我們也可以使用路徑壓縮的方法優化代，即壓縮給定元素到集合根元素路徑中的所有元素，詳細情況如下圖所示：

上圖程式碼可表示為：

/* c語言實現 */    SetName Find(SetType S, ElementType X)  {    // 找到集合的根    if (S[X] < 0)      return X;    else      return S[X] = Find(S, S[X]);  }

總之上述程式碼幹了這三件事：

  1. 先找到根；
  2. 把根變成X的父結點；
  3. 再返回根

因此，路徑壓縮第一次執行的時間比較長，但是如果頻繁使用查找命令，第一次將路徑壓縮，大大減小樹的高度，後續查找速度將大大增加

6.1 路徑壓縮時間複雜度計算

由於pta並沒有嚴格控制時間限制，使用java這種語言，不使用路徑壓縮，問題不大，我寫這個也只是為了回顧演算法，來放鬆放鬆，不是為了折騰自己，因此。

給你一個眼神自己體會，給你一個網址親自體會https://www.icourse163.org/learn/ZJU-93001?tid=1206471203#/learn/content?type=detail&id=1211167097&sm=1，我是懶得研究下圖所示了。

Tags:

VirMach 便宜 VPS