博客

集合的表示及查找

• 集合运算：交、并、补、差，判定一个元素是否属于某一集合。
• 并差集：集合并、差某元素属于什么集合
• 
  并查集中集合存储如何实现：
  
  
  （1）用树结构表示集合，树的每个节点代表一个集合元素。
  
  （2）采用数组存储形式：
• 集合的查找：

typedef struct TreeNode* HuffmanTree;

struct TreeNode{
    int weight;
    HuffmanTree left, right;
};

HuffmanTree Huffman( MinHeap H )
{
    int i;
    HuffmanTree T;
    BuildMinHeap(H);
    for( i=1; i<H->size; i++)
    {
    T = malloc(sizeof(struct TreeNode));
    T->left = DeleteMin(H);
    T->right = DeleteMin(H);
    T->weight = T->left->weight + T->right->weight;
    Insert(H, T);
    }
    T = DeleteMin(H);
    return T;
}

集合的并运算

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