专栏首页Code_iOS数据结构:集合

数据结构:集合

总表:《数据结构?》

工程代码 Github: Data_Structures_C_Implemention -- Set


预备知识 数据结构:链表

1、集合是什么?

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

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

写到这里,本文结束!下一篇,《数据结构:哈希表 [散列表] 》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一张图理清《梅花易数》梗概

    学《易经》的目的不一定是为了卜卦,但是了解卜卦绝对能够让你更好地了解易学。今天用一张思维导图对《梅花易数》的主要内容进行概括,希望能够给学友们提供帮助。

    一石匠人
  • SQL中GROUP BY用法示例

    GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

    Awesome_Tang
  • 声音功能让儿童编程更有创造性

    导读:Scratch中声音功能非常强大,除了常规的音效,你甚至可以模拟各种乐器的各个发音、设置节拍、休止……如果你愿意,甚至可以用它创作一个交响乐。我们可以引导...

    一石匠人
  • 我不是算命先生,却对占卜有了疑惑——如何论证“占卜前提”的正确与否

    事出有因,我对《周易》感兴趣了很多年。只是觉得特别有趣,断断续续学习了一些皮毛。这几天又偶然接触到了《梅花易数》,觉得很是精彩,将五行八卦天干地支都串联了起来。...

    一石匠人
  • 【系统设置】CentOS 修改机器名

    ken.io
  • 儿童创造力教育与编程教育的碰撞——MIT雷斯尼克教授最新理论梗概

    儿童编程教育已经在我国各一线二线城市疯狂出现,颇有“烂大街”的趋势。我们不禁要问很多很多问题:

    一石匠人
  • 复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

    从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

    haifeiWu
  • 《动物魔法学校》儿童学编程Scratch之“外观”部分

    导读:本文通过一个案例《动物魔法学校》来学习Scratch语言的“外观”部分。之后通过一系列其他功能的综合运用对作品功能进行了扩展。

    一石匠人
  • 天干地支五行八卦的对应关系

    一石匠人
  • 什么样的人生才是有意义的人生——没有标准的标准答案

    【导读】其实我们可以跳出这个小圈圈去更加科客观地看一下这个世界。在夜晚的时候我们仰望天空,浩瀚的宇宙中整个地球只是一粒浮尘,何况地球上一个小小的人类?在漫长的历...

    一石匠人

扫码关注云+社区

领取腾讯云代金券