数据结构：集合

作者: 半纸渊 | 来源:发表于2017-09-01 00:04 被阅读257次

复习
【List、Set、数据结构、Collections】
2020-09-05--Java--day03【数据结构,Lis
# day03 【List、Set、数据结构、Collectio
List、Set、数据结构、Collections
Java基础day14
3.List、Set、数据结构、Collections
redis数据结构(四)：整数集合 intset
redis数据结构，底层编码
数据结构（一）：结构概念与算法概念及时间复杂度

本文内容：
1、集合是什么？
2、集合的操作集。
3、集合的 C 实现。

工程代码 Github: Data_Structures_C_Implemention -- Set

1、集合是什么？

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

集合：
1、集合在数学中的表示， S = {1, 5 , 4};
2、没有元素的集合称为空集；
3、包含所有可能元素的集合称为全域，如：四位数字密码的集合，全域就是[0000 －－ 9999] (10 * 10 * 10 * 10) 种可能所有的数据；
４、两个集合的元素完全相同，称这两个集合相等；
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语言描述(中文版)》

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

复习
数据结构数据结构集合常见数据结构：集合，链表，队列，数组，栈，映射java中：List列表，Set集合，Map...
【List、Set、数据结构、Collections】
【List、Set、数据结构、Collections】主要内容数据结构 List集合 Set集合 Collec...
2020-09-05--Java--day03【数据结构,Lis
主要内容数据结构 List集合 Set集合 Collections工具类一.数据结构 1.1 数据结构有什么用...
# day03 【List、Set、数据结构、Collectio
day03 【List、Set、数据结构、Collections】主要内容数据结构 List集合 Set集合 ...
List、Set、数据结构、Collections
主要内容数据结构 List集合 Set集合 Collections 第一章数据结构 2.1 数据结构有什么用？...
Java基础day14
主要内容数据结构 List集合 Set集合 Collections 第一章数据结构 2.1 数据结构有什么用？...
3.List、Set、数据结构、Collections
主要内容数据结构 List集合 Set集合 Collections 第一章数据结构 2.1 数据结构有什么用？...
redis数据结构(四)：整数集合 intset
数据结构整数集合是redis为了保存整数值的集合而抽象出来的数据结构。intset数据结构看这意思，也是把数组...
redis数据结构，底层编码
redis的数据结构string，hash，list，set（集合），zset（有序集合）五种数据结构，但这个只...
数据结构（一）：结构概念与算法概念及时间复杂度
数据结构概念数据结构分为：逻辑结构、物理结构逻辑结构集合结构：集合结构中的数据元素除了同属于一个集合外，它们...