【数据结构】集合及运算

￡神魔★判官ぃ 2024-04-17 05:53 83阅读 0赞

### 集合的表示 ###

集合运算：交、并、补、差，判定一个元素是否属于某一集合  
**并查集**：集合**并、查**某元素属于什么集合  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

> 并查集问题中集合存储如何实现？

可以用树结构表示集合，树的每个结点代表一个集合元素  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

> 采用数组存储形式  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]

### 集合运算 ###

#### （1）查找某个元素所在的集合（用根结点表示） ####

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中的下标 */
    }

#### （2）集合的并运算 ####

分别找到X1和X2两个元素所在集合树的**根结点**  
如果它们不同根，则将其中**一个根结点的父结点指针设置成另一个根结点**的数组下标。

void Union( SetType S[ ], ElementType X1, ElementType X2 )
    {
    	int Root1, Root2;
    	Root1 = Find(S, X1);
     	Root2 = Find(S, X2);
     	if（ Root1 != Root2 ）S[Root2].Parent = Root1;
    }

为了改善合并以后的查找性能，可以采用小的集合合并到相对大的集合中。（修改Union函数）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]

#define MAXN 1000                  /* 集合最大元素个数 */
    typedef int ElementType;           /* 默认元素可以用非负整数表示 */
    typedef int SetName;               /* 默认用根结点的下标作为集合名称 */
    typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */
     
    void Union( SetType S, SetName Root1, SetName Root2 )
    { /* 这里默认Root1和Root2是不同集合的根结点 */
        /* 保证小集合并入大集合 */
        if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
            S[Root2] += S[Root1];     /* 集合1并入集合2  */
            S[Root1] = Root2;
        }
        else {                         /* 如果集合1比较大 */
            S[Root1] += S[Root2];     /* 集合2并入集合1  */
            S[Root2] = Root1;
        }
    }
     
    SetName Find( SetType S, ElementType X )
    { /* 默认集合元素全部初始化为-1 */
        if ( S[X] < 0 ) /* 找到集合的根 */
            return X;
        else
            return S[X] = Find( S, S[X] ); /* 路径压缩 */
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/b59d8259859741e6a0a8cc4a8e794fcf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/07b6c0e4363d4ed1ae6ee27b9710577b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/a73a853f809f48a78cc102b174d8085a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/9740b24795424e2587aba91051725263.png