5.3 集合及运算

1. 集合的表示

2. 集合的运算

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

// 在数组S中查找值为X的元素所属的集合，即返回根结点的下标
// MaxSize为全局变量，为数组S的最大长度
int Find( SetType S[], ElementType X)
{
    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 1= Root2)
    {
        S[Root2].Parent = Root1;    // 将x2根结点的父结点指针设置成x1的根结点
    }
}

按照以上代码执行后，可能会导致树的深度增加，从而降低查找效率。

修改根结点Parent的值，将其记录为-(树的深度)