数据结构：集合

半纸渊

发布于 2018-08-30 14:55:00

1.3K0

发布于 2018-08-30 14:55:00

文章被收录于专栏：Code_iOSCode_iOS

总表：《数据结构？》

工程代码 Github: Data_Structures_C_Implemention -- Set

预备知识数据结构：链表

1、集合是什么？

集合，是由一堆无序的、相关联的，且不重复的内存结构【数学中称为元素】组成的组合；

集合：

1、集合在数学中的表示， S = {1, 5 , 4};

2、没有元素的集合称为空集；

3、包含所有可能元素的集合称为全域，如：四位数字密码的集合，全域就是0000 －－ 9999 种可能所有的数据；

４、两个集合的元素完全相同，称这两个集合相等；

5、集合1中所有的元素在集合2中均有【它们不相等】，则集合1 是集合2 的子集；

2、集合的操作集.

集合操作有插入、删除、交集、并集、差集；

交集、并集、差集图示：

解析：

1、集合交集，指两个集合中相同的元素组合成的集合；

2、集合并集，指两个集合所有不相同的元素组成的集合；

3、集合差集，指两个集合除相同元素外剩下元素的集合，分两种情况：Sd1 = S1 - S2; Sd2 = S2 - S1; S1 与 S2 中相同的元素集记为 Si，前者 Sd1 是 S1 与 Si 的交集，后者 Sd2 是 S2 与 Si 的交集；

集合操作集图示：

集合 - 操作.png

3、集合的 C 实现。

这里直接使用单链表来实现集合的所有操作！

typedef List Set;

Set 就是单链表；

实现图：

集合的操作集：

/* Set Create */
Set Set_Create(MatchFunc mat, DestroyFunc des); // 创建
void Set_Init(Set set, MatchFunc mat, DestroyFunc des); // 初始化
void Set_Destroy(Set set); // 销毁

/* Set Operations */
_BOOL Set_Insert(Set set, ElementTypePrt x); // 插入
_BOOL Set_Remove(Set set, ElementTypePrtPrt data); // 删除

_BOOL Set_Union(Set uSet, const Set set1, const Set set2); // 并集
_BOOL Set_Intersection(Set iSet, const Set set1, const Set set2); // 交集
_BOOL Set_Difference(Set dSet, const Set set1, const Set set2); // 差集

_BOOL Set_IsMember(const Set set, const ElementTypePrt data); // 是否包含元素
_BOOL Set_IsSubset(const Set subSet, const Set totalSet); // 是否是集合的子集
_BOOL Set_IsEqual(const Set set1, const Set set2); // 集合是否相等

集合的创建与销毁：

创建，与单链表的唯一不同就是，增加了 MatchFunc 参量，它用于集合元素的匹配；

Set Set_Create(MatchFunc mat, DestroyFunc des) {

    Set set = List_Create(des);
    set->matchFunc = mat;

    return set;

}

初始化，与单链表的唯一不同就是，增加了 MatchFunc 参量，它用于集合元素的匹配；

void Set_Init(Set set, MatchFunc mat, DestroyFunc des) {

    List_Init(set, des);
    set->matchFunc = mat;

}

销毁，与单链表的一致；

void Set_Destroy(Set set) { List_Destroy(set); }

集合的插入与删除：

插入，直接使用单链表的插入方法，只是因为集合中元素本是无序的，所以为了方便直接在链尾处插入新的元素；

_BOOL Set_Insert(Set set, ElementTypePrt x) {

    if ( ! Set_IsEmpty(set) && Set_IsMember(set, x)) {
        printf("ERROR: Duplicates Member !");
        return LINKEDLIST_FALSE;
    }

    return List_Insert(set, List_Tail(set), x);

}

解析，集合中的元素虽说无序但不能重复，所以在插入新元素前要先判断集合是是否已经有该元素，而这个判断由 Set_IsMember(set, x) 函数完成，它的原型是，

_BOOL Set_IsMember(const Set set, const ElementTypePrt data) {

    return (List_Find(set, set->matchFunc, data) == NULL ? LINKEDLIST_FALSE :
                                                           LINKEDLIST_TRUE);

}

它的原理就是，遍历单链表看是否能匹配到当前元素；

删除，与单链表的做法是一样，要先通过要删除的节点，找到前面的节点，再进行删除链表的操作；

_BOOL Set_Remove(Set set, ElementTypePrtPrt data) {

    if (Set_IsEmpty(set)) { printf("ERROR: Empty Set !"); return LINKEDLIST_FALSE;}

    ListNode setRemove = List_FindPrevious(set, set->matchFunc, *data);
    if (setRemove->next == NULL) { return LINKEDLIST_FALSE; }

    return List_Remove(set, setRemove, data);

}

集合的交集：

_BOOL Set_Intersection(Set iSet, const Set set1, const Set set2) {

    if (iSet == NULL || set1 == NULL || set2 == NULL) {
        printf("ERROR: Bad Set !"); return LINKEDLIST_FALSE;
    }

    if (iSet->matchFunc == NULL) { Set_Init(iSet, set1->matchFunc, set1->destroyFunc); }

    ListNode node = NULL;
    ElementTypePrt data;

    for (node = List_Head(set1); node != NULL; node = List_NodeNext(node)) {

        data = List_NodeData(node);
        if (Set_IsMember(set2, data)) {

            if ( ! List_Insert(iSet, List_Tail(iSet), data) ) {
                List_Destroy(iSet); return LINKEDLIST_FALSE;
            }

        }

    }

    return LINKEDLIST_TRUE;

}

解析，交集的意思就是两个集合是否有相同的元素，若有则把它们做成一个新的集合，而它就是两个集合的交集;

交集的图示，

// 对应的核心代码
    for (node = List_Head(set1); node != NULL; node = List_NodeNext(node)) {

        data = List_NodeData(node);
        if (Set_IsMember(set2, data)) {

            if ( ! List_Insert(iSet, List_Tail(iSet), data) ) {
                List_Destroy(iSet); return LINKEDLIST_FALSE;
            }

        }

    }

其实就是一个 For 循环，不断地进行判断；

集合的并集：

_BOOL Set_Union(Set uSet, const Set set1, const Set set2) {
    
    if (uSet == NULL || set1 == NULL || set2 == NULL) {
        printf("ERROR: Bad Set !"); return LINKEDLIST_FALSE;
    }

    if (uSet->matchFunc == NULL) { Set_Init(uSet, set1->matchFunc, set1->destroyFunc); }

    ListNode node = NULL;
    ElementTypePrt data;

    for (node = List_Head(set1); node != NULL; node = List_NodeNext(node)) {

        data = List_NodeData(node);
        if ( ! List_Insert(uSet, List_Tail(uSet), data) ) {
            List_Destroy(uSet); return LINKEDLIST_FALSE;
        }

    }

    for (node = List_Head(set2); node != NULL; node = List_NodeNext(node)) {

        data = List_NodeData(node);
        if (Set_IsMember(uSet, data)) { continue; }

        if ( ! List_Insert(uSet, List_Tail(uSet), data) ) {
            List_Destroy(uSet); return LINKEDLIST_FALSE;
        }

    }

    return LINKEDLIST_TRUE;

}

解析，并集图示，

// 对应的核心代码
    for (node = List_Head(set1); node != NULL; node = List_NodeNext(node)) {

        data = List_NodeData(node);
        if ( ! List_Insert(uSet, List_Tail(uSet), data) ) {
            List_Destroy(uSet); return LINKEDLIST_FALSE;
        }

    }

    for (node = List_Head(set2); node != NULL; node = List_NodeNext(node)) {

        data = List_NodeData(node);
        if (Set_IsMember(uSet, data)) { continue; }

        if ( ! List_Insert(uSet, List_Tail(uSet), data) ) {
            List_Destroy(uSet); return LINKEDLIST_FALSE;
        }

    }

第一个 For 循环是把左边集合的元素全部插入到新的集合中；

第二个 For 循环是把右边集合的元素插入到新的集合中去，但是插入前要先进行判断，看新的集合中是否已经存在了与右边集合相同的元素；

集合的差集：

_BOOL Set_Difference(Set dSet, const Set set1, const Set set2) {
    
    if (dSet == NULL || set1 == NULL || set2 == NULL) {
        printf("ERROR: Bad Set !"); return LINKEDLIST_FALSE;
    }

    if (dSet->matchFunc == NULL) { Set_Init(dSet, set1->matchFunc, set1->destroyFunc); }

    ListNode node = NULL;
    ElementTypePrt data;

    for (node = List_Head(set1); node != NULL; node = List_NodeNext(node)) {

        data = List_NodeData(node);
        if ( ! Set_IsMember(set2, data) ) {

            if (!List_Insert(dSet, List_Tail(dSet), data)) {
                List_Destroy(dSet); return LINKEDLIST_FALSE;
            }

        }

    }

    return LINKEDLIST_TRUE;

}

解析，差集这里要注意是谁差谁的，结果是不一样的，当然对于程序而言，谁差谁根本不重要，不过您要知道而已；

差集图示，

// 对应的核心代码
    for (node = List_Head(set1); node != NULL; node = List_NodeNext(node)) {

        data = List_NodeData(node);
        if ( ! Set_IsMember(set2, data) ) {

            if (!List_Insert(dSet, List_Tail(dSet), data)) {
                List_Destroy(dSet); return LINKEDLIST_FALSE;
            }

        }

    }

集合的子集：

_BOOL Set_IsSubset(const Set subSet, const Set totalSet) {
    
    if (subSet == NULL || totalSet == NULL) {
        printf("ERROR: Bad Set !"); return LINKEDLIST_FALSE;
    }

    if (List_Size(subSet) > List_Size(totalSet)) { return LINKEDLIST_FALSE; }

    ListNode node = NULL;
    ElementTypePrt data;

    for (node = List_Head(subSet); node != NULL; node = List_NodeNext(node)) {

        data = List_NodeData(node);
        if ( ! Set_IsMember(totalSet, data) ) { return LINKEDLIST_FALSE; }

    }

    return LINKEDLIST_TRUE;

}

解析，比如有集合1和集合2，要让集合1是集合2的子集，那么集合1的元素个数要小于或等于集合2，而且集合1中的元素在集合2中都有【即集合1与集合2的交集是空集】；

集合相等：

_BOOL Set_IsEqual(const Set set1, const Set set2) {
    
    if (set1 == NULL || set2 == NULL) {
        printf("ERROR: Bad Set !"); return LINKEDLIST_FALSE;
    }

    if (List_Size(set1) != List_Size(set2)) { return LINKEDLIST_FALSE; }

    return Set_IsSubset(set1, set2);

}

解析，这里就很好理解了，要让集合相等，首先它们的元素个数得相等，再判断它们的元素是否完全相同就可以了【因为子集本身就要判断元素相等性，所以可以直接使用 Set_IsSubset(set1, set2) 来判断】；

参考书籍：

1、《算法精解_C语言描述(中文版)》

写到这里，本文结束！下一篇，《数据结构：哈希表散列表》

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017.09.01 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度