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

SegmentFault 發(fā)布于2019-08-23 12:15 / 1058人閱讀

摘要：集合是一種包含不同元素的數(shù)據(jù)結(jié)構(gòu)集合中的元素稱為成員集合的兩個(gè)最重要的特性是首先集合中的成員是無序的其次集合中不允許相同成員存在集合在計(jì)算機(jī)科學(xué)中扮演了非常重要的角色然而在很多編程語言中并不把集合當(dāng)成一種數(shù)據(jù)類型當(dāng)你想要?jiǎng)?chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)用來

集合(set)是一種包含不同元素的數(shù)據(jù)結(jié)構(gòu). 集合中的元素稱為成員. 集合的兩個(gè)最重要的特性是: 首先, 集合中的成員是無序的; 其次, 集合中不允許相同成員存在. 集合在計(jì)算機(jī)科學(xué)中扮演了非常重要的角色, 然而在很多編程語言中, 并不把集合當(dāng)成一種數(shù)據(jù)類型. 當(dāng)你想要?jiǎng)?chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu), 用來保存一些獨(dú)一無二的元素時(shí), 比如一段文本中用到的單詞, 集合就變得非常有用. 
在ES6中已加入集合Set

集合的定義、操作和屬性

集合是由一組無序但彼此之間又有一定相關(guān)性的成員構(gòu)成的, 每個(gè)成員在集合中只能出現(xiàn)一次.

集合的定義

下面是一些使用集合必須了解的定義.

不包含任何成員的集合稱為 空集_, _全集 則是包含一切可能成員的集合.

如果兩個(gè)集合的成員完全相同, 則稱兩個(gè)集合相等.

如果一個(gè)集合中所有的成員都屬于另外一個(gè)集合, 則前一集合稱為后一集合的子集.

對(duì)集合的操作

對(duì)集合的基本操作有下面幾種:

并集 : 將兩個(gè)集合中的成員進(jìn)行合并, 得到一個(gè)新的集合.

交集 : 兩個(gè)集合中共同存在的成員組成一個(gè)新的集合.

補(bǔ)集 : 屬于一個(gè)集合而不屬于另一個(gè)集合的成員組成的集合.

Set類的實(shí)現(xiàn)

Set類的實(shí)現(xiàn)基于數(shù)組, 數(shù)組用來存儲(chǔ)數(shù)據(jù).

window.log = console.log.bind(console)

class Set {
    constructor() {
        this._dataStore = [];
    }
    add(data) {
        if(!this._dataStore.includes(data)) {
            this._dataStore.push(data);
            return true;
        };
        return false;
    }
    remove(data) {
        const pos = this._dataStore.indexOf(data);
        if(pos > -1) {
            this._dataStore.splice(pos, 1);
            return true;
        };
        return false;
    }
    show() {
        return this._dataStore;
    }
};

add()方法: 因?yàn)榧现胁荒馨嗤脑? 所以, 使用add()方法將數(shù)據(jù)存儲(chǔ)到數(shù)組前, 先要確保數(shù)組中不存在該數(shù)據(jù). 我們使用indexof()檢查新加入的元素在數(shù)組是否存在. 如果找到, 該方法返回該元素在數(shù)組中的位置; 如果沒找到, 該方法返回-1. 如果數(shù)組中還未包含該元素, add()方法將新加入的元素保存在數(shù)組中并返回true; 反之返回false. 將add()方法的返回值定義為布爾類型, 可以明確告訴我們是否將一個(gè)元素成功加入到了集合中. 這里使用ES6中的includes()也是可以的.

remove()方法和add()方法的工作原理類似. 首先檢查待刪除元素是否在數(shù)組中, 如何在, 則使用數(shù)組的splice()方法刪除該元素并返回true; 反之返回false, 表示集合中不存在這樣的一個(gè)元素.

show()顯示集合中的成員.
測(cè)試程序:

const s = new Set();
s.add("a");
s.add("b");
s.add("c");
s.add("d");
s.add("e");
s.add("f");
log(s.show());
if(s.add("f")) {
    log("f: 添加成功")
} else {
    log("已存在f, 添加失敗")
}

輸出:

(6)?["a", "b", "c", "d", "e", "f"]
已存在f, 添加失敗

更多集合操作

定義union()、subset()和difference()方法會(huì)更有意思. union()方法執(zhí)行并集操作, 將兩個(gè)集合合并成一個(gè). 該方法首先將第一個(gè)集合里的成員悉數(shù)加入一個(gè)臨時(shí)集合, 然后檢查第二個(gè)集合中的成員, 看它們是否也同時(shí)屬于第一個(gè)集合. 如果屬于, 則跳過該成員, 否則就將該成員加入臨時(shí)集合.

在定義union()方法前, 先定一個(gè)輔助方法contains(), 該方法檢查一個(gè)成員是否屬于該集合.

contains(data) {
    return this._dataStore.includes(data);
}
// 并集
union(set) {
    const tempSet = new Set();
    this._dataStore.forEach(i => {
        tempSet.add(i);
    });
    set._dataStore.forEach(i => {
        if(!tempSet.contains(i)) {
            tempSet._dataStore.push(i)
        }
    });

    return tempSet;
}

執(zhí)行程序:

const s = new Set();
s.add("a");
s.add("b");
s.add("c");
s.add("d");
s.add("e");
s.add("f");
log(s.show());

const s1 = new Set();
s1.add("a");
s1.add("f");
s1.add("g");

let res = new Set();
res = s.union(s1);
log(res.show());

//輸出:
// (6)?["a", "b", "c", "d", "e", "f"]
// (7)?["a", "b", "c", "d", "e", "f", "g"]

使用intersect()方法求兩個(gè)集合的交集. 該方法定義起來相對(duì)簡(jiǎn)單. 每當(dāng)發(fā)現(xiàn)第一個(gè)集合的成員也屬于第二個(gè)集合時(shí), 便將該成員加入一個(gè)心機(jī)和, 這個(gè)心機(jī)和即為方法的返回值.

// 交集
intersect(set) {
    const tempSet = new Set();
    this._dataStore.forEach(i => {
        if(set.contains(i)) {
            tempSet.add(i)
        };
    });

    return tempSet;
}

下一個(gè)要定義的操作是subset()判斷子集. subset()方法首先要確定該集合的長(zhǎng)度是否小于帶比較集合.
如果該集合比帶比較集合還要大, 那么該集合肯定不會(huì)是待比較集合的一個(gè)子集.
當(dāng)集合的長(zhǎng)度小于待比較集合時(shí), 再判斷該集合內(nèi)的成員是否都屬于待比較集合. 如果有任意一個(gè)成員不屬于待比較集合, 則返回false, 程序終止. 如果一直比較完該集合的最后一個(gè)元素, 所有元素都屬于待比較集合, 那么該集合就是待比較集合的一個(gè)子集, 該方法返回true.
在判斷每個(gè)元素是否屬于待比較集合前, 該方法先使用size()方法對(duì)比兩個(gè)集合的大小.

size() {
    return this._dataStore.length;
}
subSet(set) {
    if(this.size() > set.size()) {
        return false;
    };
    for(let i = 0; i < this._dataStore.length; i++) {
        if(!set.contains(this._dataStore[i])) {
            return false;
        };
    };
    return true;
}

最后一個(gè)操作是difference()補(bǔ)集, 該方法返回一個(gè)新集合, 該集合包含的是那些屬于第一個(gè)集合但不屬于第二個(gè)集合的成員.

difference(set) {
    const tempSet = new Set();
    this._dataStore.forEach(i => {
        if(!set.contains(i)) {
            tempSet.add(i);
        };
    });

    return tempSet;
}

GPU云服務(wù)器云服務(wù)器數(shù)據(jù)集合 java集合結(jié)構(gòu) js 集合數(shù)據(jù)結(jié)構(gòu) js存儲(chǔ)集合數(shù)據(jù)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/98182.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

SegmentFault

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

為什么建議向你的同事屏蔽朋友圈？

閱讀 2938·2021-10-14 09:43
浙商證券：維持深信服“買入”評(píng)級(jí) 打造數(shù)字世界“便利店” 驅(qū)動(dòng)云計(jì)算業(yè)務(wù)高成長(zhǎng)_云資訊

閱讀 2883·2021-10-14 09:42
登陸郵箱主機(jī)名什么意思-蘋果qq郵箱收件服務(wù)器主機(jī)名填什么？

閱讀 4663·2021-09-22 15:56
【Hello CSS】第二章-CSS的邏輯屬性與盒子模型

閱讀 2371·2019-08-30 10:49
jQuery實(shí)現(xiàn)記住帳號(hào)密碼功能

閱讀 1594·2019-08-26 13:34
Node.js安裝及環(huán)境配置之Linux篇

閱讀 2385·2019-08-26 10:35
2019.04.04 防抖和節(jié)流

閱讀 605·2019-08-23 17:57
NodeJS實(shí)現(xiàn)簡(jiǎn)易區(qū)塊鏈

閱讀 2029·2019-08-23 17:15

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

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

相關(guān)文章

**學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（三）：集合**

**【前端數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】集合**

Java? 教程（集合介紹）

**JavaScript的數(shù)據(jù)結(jié)構(gòu)與算法（五） —— 集合**

**學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(三)——集合**

發(fā)表評(píng)論

0條評(píng)論

SegmentFault

男|高級(jí)講師

TA的文章

為什么建議向你的同事屏蔽朋友圈？

浙商證券：維持深信服“買入”評(píng)級(jí) 打造數(shù)字世界“便利店” 驅(qū)動(dòng)云計(jì)算業(yè)務(wù)高成長(zhǎng)_云資訊

登陸郵箱主機(jī)名什么意思-蘋果qq郵箱收件服務(wù)器主機(jī)名填什么？

【Hello CSS】第二章-CSS的邏輯屬性與盒子模型

jQuery實(shí)現(xiàn)記住帳號(hào)密碼功能

Node.js安裝及環(huán)境配置之Linux篇

2019.04.04 防抖和節(jié)流

NodeJS實(shí)現(xiàn)簡(jiǎn)易區(qū)塊鏈

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

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

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！