數(shù)據(jù)結(jié)構(gòu)：集合

本文內(nèi)容：
1、集合是什么？
2、集合的操作集。
3、集合的 C 實(shí)現(xiàn)。

總表：《數(shù)據(jù)結(jié)構(gòu)？》

工程代碼 Github: Data_Structures_C_Implemention -- Set

預(yù)備知識(shí) 數(shù)據(jù)結(jié)構(gòu)：鏈表

1、集合是什么？

集合，是由一堆無序的、相關(guān)聯(lián)的，且不重復(fù)的內(nèi)存結(jié)構(gòu)【數(shù)學(xué)中稱為元素】組成的組合；

集合：
1、集合在數(shù)學(xué)中的表示， S = {1, 5 , 4};
2、沒有元素的集合稱為空集；
3、包含所有可能元素的集合稱為全域，如：四位數(shù)字密碼的集合，全域就是[0000 －－ 9999] (10 * 10 * 10 * 10) 種可能所有的數(shù)據(jù)；
４、兩個(gè)集合的元素完全相同，稱這兩個(gè)集合相等；
5、集合1中所有的元素在集合2中均有【它們不相等】，則集合1 是集合2 的子集；

2、集合的操作集.

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

交集、并集、差集圖示：

解析：
1、集合交集，指兩個(gè)集合中相同的元素組合成的集合；
2、集合并集，指兩個(gè)集合所有不相同的元素組成的集合；
3、集合差集，指兩個(gè) 集合除相同元素外剩下元素的集合，分兩種情況：Sd1 = S1 - S2; Sd2 = S2 - S1; S1 與 S2 中相同的元素集記為 Si，前者 Sd1 是 S1 與 Si 的交集，后者 Sd2 是 S2 與 Si 的交集；

集合操作集圖示：
集合 - 操作.png

3、集合的 C 實(shí)現(xiàn)。

這里直接使用單鏈表來實(shí)現(xiàn)集合的所有操作！

typedef List Set;
Set 就是單鏈表；

實(shí)現(xiàn)圖：

集合的操作集：

/* Set Create */
Set Set_Create(MatchFunc mat, DestroyFunc des); // 創(chuàng)建
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); // 集合是否相等

集合的創(chuàng)建與銷毀：

創(chuàng)建，與單鏈表的唯一不同就是，增加了 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); }

集合的插入與刪除：

插入，直接使用單鏈表的插入方法，只是因?yàn)榧现性乇臼菬o序的，所以為了方便直接在鏈尾處插入新的元素；

_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);

}

解析，集合中的元素雖說無序但不能重復(fù)，所以在插入新元素前要先判斷集合是是否已經(jīng)有該元素，而這個(gè)判斷由 Set_IsMember(set, x) 函數(shù)完成，它的原型是，

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

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

}

它的原理就是，遍歷單鏈表看是否能匹配到當(dāng)前元素；

刪除，與單鏈表的做法是一樣，要先通過要?jiǎng)h除的節(jié)點(diǎn)，找到前面的節(jié)點(diǎn)，再進(jìn)行刪除鏈表的操作；

_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;

}

解析，交集的意思就是兩個(gè)集合是否有相同的元素，若有則把它們做成一個(gè)新的集合，而它就是兩個(gè)集合的交集;

交集的圖示，
// 對(duì)應(yīng)的核心代碼
    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;
            }

        }

    }

其實(shí)就是一個(gè) For 循環(huán)，不斷地進(jìn)行判斷；

  • 集合的并集：
_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;

}

解析，并集圖示，
// 對(duì)應(yīng)的核心代碼
    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;
        }

    }

第一個(gè) For 循環(huán)是把左邊集合的元素全部插入到新的集合中；
第二個(gè) For 循環(huán)是把右邊集合的元素插入到新的集合中去，但是插入前要先進(jìn)行判斷，看新的集合中是否已經(jīng)存在了與右邊集合相同的元素；

  • 集合的差集：
_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;

}

解析，差集這里要注意是誰差誰的，結(jié)果是不一樣的，當(dāng)然對(duì)于程序而言，誰差誰根本不重要，不過您要知道而已；

差集圖示，
// 對(duì)應(yīng)的核心代碼
    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的元素個(gè)數(shù)要小于或等于集合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);

}

解析，這里就很好理解了，要讓集合相等，首先它們的元素個(gè)數(shù)得相等，再判斷它們的元素是否完全相同就可以了【因?yàn)樽蛹旧砭鸵袛嘣叵嗟刃裕钥梢灾苯邮褂?Set_IsSubset(set1, set2) 來判斷】；

參考書籍：
1、《算法精解_C語言描述(中文版)》

寫到這里，本文結(jié)束！下一篇，《數(shù)據(jù)結(jié)構(gòu)：哈希表 [散列表] 》

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容