JS中的算法與數(shù)據(jù)結(jié)構(gòu)——集合(Set)

愉快的假期告一段落,繼續(xù)我們的學(xué)習(xí)~

集合(Set)

同數(shù)學(xué)中所學(xué)的一樣了赵,集合(Set)是由一組無(wú)序但彼此之間又有一定關(guān)系性的成員構(gòu)成树肃,每個(gè)成員在集合中只能出現(xiàn)一次,不同于我們之前說(shuō)的字典娄徊,鏈表之類的闽颇,它是一種包含了不同元素的數(shù)據(jù)結(jié)構(gòu)(集合中的元素稱為成員),從其定義中我們可以看出它具有兩個(gè)很重要的特征:首先寄锐,集合中的成員是無(wú)序的兵多,其次,集合中的成員是不相同的橄仆,即集合中不存在相同的成員剩膘。

實(shí)際上,很多編程語(yǔ)言中盆顾,集合并不是一種數(shù)據(jù)類型怠褐,但是如果你需要?jiǎng)?chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)用來(lái)保存一些獨(dú)一無(wú)二的元素時(shí),集合就變得很有用了您宪,接下來(lái)我們一起來(lái)看看JS中如何實(shí)現(xiàn)一個(gè)集合奈懒。

集合的定義

我們要實(shí)現(xiàn)一個(gè)集合具温,首先要對(duì)其一些定義做了解

  • 不包含任何成員的集合稱為空集,包含一切可能成員的集合稱為全集筐赔。
  • 如果兩個(gè)集合里的成員都完全相同铣猩,則稱兩個(gè)集合相等。
  • 如果一個(gè)集合所有成員都包含于另一個(gè)集合茴丰,則前一集合稱為后一集合的一個(gè)子集达皿。

集合的操作

通常來(lái)說(shuō),集合的基本操作有以下三種:

  • 并集:將兩個(gè)集合中的成員進(jìn)行合并贿肩,得到一個(gè)新的集合
  • 交集:將兩個(gè)集合中共同存在的成員組成的一個(gè)新的集合
  • 補(bǔ)集:屬于一個(gè)集合而不屬于另一個(gè)集合的成員組成的新的集合

集合的實(shí)現(xiàn)

集合(Set)的實(shí)現(xiàn)我們這里基于數(shù)組峦椰,用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù),根據(jù)我們之前學(xué)習(xí)的以及上面提到的一些方法汰规,我們可以將集合的構(gòu)造函數(shù)定義如下(為了區(qū)別ES6的 set 類型汤功,我們這里選擇用 MySet 命名):

//構(gòu)造函數(shù)

function MySet () {
    this.dataStore = [];            // 數(shù)據(jù)存儲(chǔ)
    this.add = add;                 // 添加成員
    this.remove = remove;           // 刪除成員
    this.size = size;               // 集合元素個(gè)數(shù)
    this.union = union;             // 集合求并集
    this.intersect = intersect;     // 集合求交集
    this.subset = subset;           // 判斷一個(gè)集合是否是另一集合的子集
    this.difference = difference;   // 集合求補(bǔ)集
    this.contains = contains;       // 判斷某成員是否屬于該集合
    this.show = show;               // 顯示當(dāng)前集合
}

我們第一個(gè)要實(shí)現(xiàn)的方法就是向集合中添加一個(gè)成員,即 add 方法

add:向集合中添加一個(gè)成員

//添加元素

function add (data) {
    //判斷元素是否存在集合當(dāng)中
    if( this.dataStore.indexOf( data )  < 0 ){
        this.dataStore.push(data);
        return true;
    }else{
        console.warn( 'Can not add ' + data + ', must already be in set');
        return false;
    }
}

我們之前提到溜哮,集合中的元素是獨(dú)一無(wú)二的滔金,因此,我們?cè)趯?shù)據(jù)存儲(chǔ)到數(shù)組之前茂嗓,首先就是要確保該集合不存在該數(shù)據(jù)餐茵,因此,我們先用 indexOf 方法檢查新加入的元素是否存在述吸,如果找到了就返回該成員在數(shù)組中的位置忿族;否則,就返回 -1 蝌矛,那么對(duì)應(yīng)的 add 方法就可以定義返回布爾值道批,添加成功我們返回 true , 否則返回 false 入撒,這樣就可以明確告訴我們是否正確的插入了一個(gè)元素隆豹。

remove:刪除集合中某個(gè)成員

//刪除元素

function remove (data) {
    //判斷元素是否存在集合當(dāng)中
    var pos = this.dataStore.indexOf(data);
    if( pos > -1 ){
        this.dataStore.splice(pos,1);
        return true;
    }else{
        console.warn( data + ' is not in set');
        return false;
    }
}

這里,我們順理成章的實(shí)現(xiàn)了刪除方法衅金,它跟 add 方法很類似噪伊,首先要檢查待刪除元素是否存在于數(shù)組中,如果存在氮唯,我們調(diào)用數(shù)組的 splice() 方法刪除該元素并返回 true ,否則姨伟,直接返回 false 惩琉,表示集合中不存在該元素。

現(xiàn)在夺荒,我們可以完成集合的添加和刪除瞒渠,要測(cè)試這些方法之前良蒸,我們首先得定義 show 方法,該方法用來(lái)顯示集合中的成員伍玖,該方法的實(shí)現(xiàn)很簡(jiǎn)答嫩痰,只需返回我們定義的數(shù)組即可:

show:顯示集合中的成員

// 顯示集合成員

function show(){
    console.log(this.dataStore);
    return this.dataStore;
}

接著,我們這會(huì)來(lái)測(cè)試一下:

var fruits = new MySet();

// 添加成員
fruits.add('Apple');
fruits.add('Banana');
fruits.add('Pear');
fruits.show();              // ["Apple", "Banana", "Pear"]

// 添加重復(fù)成員
fruits.add('Apple');        // Can not add Apple, must already be in set

// 刪除成員
fruits.remove('Banana');    
fruits.show();              // ["Apple", "Pear"]

// 刪除不存在的成員
fruits.remove('Banana');    // Banana is not in set

嗯窍箍,一切正常串纺,我們可以來(lái)實(shí)現(xiàn)集合的一些高級(jí)操作了,我們先來(lái)看看 union (并集)的實(shí)現(xiàn)椰棘。

union:求集合并集

求集合的并集纺棺,就是要將兩個(gè)集合合并成一個(gè),并除去重復(fù)的元素邪狞,我們實(shí)現(xiàn)思路就是將第一個(gè)集合成員放到一個(gè)臨時(shí)集合中祷蝌,判斷第二個(gè)集合的成員是否也屬于第一個(gè)集合,如果為真帆卓,代表為重復(fù)元素巨朦,我們直接跳過(guò)該成員,否則將該成員加入臨時(shí)集合剑令,最后返回該集合即可罪郊;

那么,問(wèn)題來(lái)了尚洽,我們要如何判斷一個(gè)成員是否存在于該集合中悔橄?因此,我們需要一個(gè)輔助方法 contains()腺毫,它的實(shí)現(xiàn)也非常簡(jiǎn)單癣疟,直接用 indexOf 判斷即可

//判斷元素是否屬于該集合

function contains (data) {
    if( this.dataStore.indexOf(data) > -1 ){
        return true;
    }else{
        return false;
    }
}

現(xiàn)在,我們可以定義 union 方法了

//求集合的并集

function union ( set ) {
    var tempSet = new MySet();
    for( var i = 0 ; i < this.dataStore.length ; i++ ){
        tempSet.add(this.dataStore[i]);
    }
    for( var i = 0 ; i< set.dataStore.length ; i++ ){
        if( !tempSet.contains(set.dataStore[i])){
            tempSet.dataStore.push(set.dataStore[i]);
        }
    }
    return tempSet;
}

這樣潮酒,我們就可以就集合的并集了睛挚,

var fruits1 = new MySet();
fruits1.add('Apple');
fruits1.add('Banana');
fruits1.add('Pear');

var fruits2 = new MySet();
fruits2.add('Grape');
fruits2.add('Banana');
fruits2.add('Pear');
fruits2.add('Orange');

var union = fruits1.union( fruits2 );
union.show();                           // ["Apple", "Banana", "Pear", "Grape", "Orange"]

成功了!我們可以來(lái)看看求集合的交集了急黎。

intersect:求集合的交集

有了上面求并集的思路扎狱,那么交集的定義來(lái)說(shuō)也相對(duì)簡(jiǎn)單,思路就是發(fā)現(xiàn)第一個(gè)集合的成員也屬于第二個(gè)集合時(shí)勃教,就將該成員加入到新的集合淤击,最后返回新的集合即可;

//求集合的交集

function intersect (set) {
    var tempSet = new MySet();
    for(var i = 0 ; i < this.dataStore.length ; i++ ){
        if( set.contains(this.dataStore[i])){
            tempSet.add(this.dataStore[i]);
        }
    }
    return tempSet;
}

我們還是利用上面的兩個(gè)集合接著求其交集:

var intersect = fruits1.intersect( fruits2 );
intersect.show();                               // ["Banana", "Pear"]

下一個(gè)定義的操作是 subset 故源;

subset:判斷集合是否是另一集合的子集

該方法首先要確定 該集合的長(zhǎng)度是否小于待比較的集合污抬。如果該集合比待比較集合還要大,那么肯定不是待比較集合的一個(gè)子集。只要當(dāng)印机,待比較集合比較大時(shí)矢腻,才去判斷集合類的成員是否都屬于待比較集合,如果有一個(gè)不是射赛,直接返回 false 多柑, 只有當(dāng)所有元素都屬于待比較集合的時(shí)候,我們才能說(shuō)該集合是待比較集合的一個(gè)子集楣责,該方法才會(huì)返回 true , 為了方便查看竣灌,我加入了console打印腐魂;

//子集判斷

function subset (set) {
    if( this.size() > set.size() ){
        console.log('not a subset');
        return false;
    }else{
        for ( var i = 0 ; i < this.dataStore.length ; i++ ){
            if( !set.contains(this.dataStore[i])){
                console.log('not a subset');
                return false;
            }
        }
    }
    console.log(' a subset');
    return true;
}

我們看到上面用到了 size 方法帐偎,它的定義如下:

//返回集合長(zhǎng)度

function size () {
    return this.dataStore.length;
}

我們保留上面的 fruits1 和 fruits2 , 新建一個(gè) fruits3 來(lái)演示 subset 方法

var fruits3  = new MySet();
fruits3.add('Apple');
fruits3.add('Banana');
fruits3.add('Pear');
fruits3.add('Grape');
fruits3.add('Orange');

//子集判斷

fruits1.subset( fruits2 );      // not a subset
fruits2.subset( fruits2 );      // a subset
fruits1.subset( fruits3 );      // a subset

看起來(lái)一切都很順利蛔屹,我們只剩最后一個(gè) difference 方法削樊,該方法返回一個(gè)新集合,該集合是由屬于第一個(gè)集合而不屬于第二個(gè)集合的成員組成的兔毒。

difference:補(bǔ)集

有了交集的思路漫贞,補(bǔ)集的實(shí)現(xiàn)就顯得很自然了。

//補(bǔ)集

function difference (set) {
    var tempSet = new  MySet();
    for( var i = 0 ; i < this.dataStore.length ; i ++ ){
        if( !set.contains(this.dataStore[i])){
            tempSet.dataStore.push( this.dataStore[i] );
        }
    }
    return tempSet;
}

我們測(cè)試一下:

fruits1.difference(fruits2).show();     // ['Apple']
fruits1.difference(fruits3).show();     // []
fruits2.difference(fruits1).show();     // ["Grape", "Orange"]

ok育叁,到現(xiàn)在迅脐,我們完成了一個(gè)完整的 set 集合,是不是很棒豪嗽!

本篇介紹的集合和 ES6 的集合略微有點(diǎn)差別谴蔑,ES6 提供的 Set 數(shù)據(jù)結(jié)構(gòu),有很多現(xiàn)成的方法可以直接調(diào)用龟梦,很是方法隐锭,不是很了解的小伙伴可以參考我之前的一篇博文,關(guān)于ES6中Symbol 计贰、Set 和 Map 一文钦睡,相信會(huì)有不錯(cuò)的收獲~

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市躁倒,隨后出現(xiàn)的幾起案子荞怒,更是在濱河造成了極大的恐慌,老刑警劉巖秧秉,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件褐桌,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡福贞,警方通過(guò)查閱死者的電腦和手機(jī)撩嚼,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)挖帘,“玉大人完丽,你說(shuō)我怎么就攤上這事∧匆ǎ” “怎么了逻族?”我有些...
    開(kāi)封第一講書人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)骄崩。 經(jīng)常有香客問(wèn)我聘鳞,道長(zhǎng),這世上最難降的妖魔是什么要拂? 我笑而不...
    開(kāi)封第一講書人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任抠璃,我火速辦了婚禮,結(jié)果婚禮上脱惰,老公的妹妹穿的比我還像新娘搏嗡。我一直安慰自己,他們只是感情好拉一,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布采盒。 她就那樣靜靜地躺著,像睡著了一般蔚润。 火紅的嫁衣襯著肌膚如雪磅氨。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書人閱讀 52,736評(píng)論 1 312
  • 那天嫡纠,我揣著相機(jī)與錄音烦租,去河邊找鬼。 笑死除盏,一個(gè)胖子當(dāng)著我的面吹牛叉橱,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播痴颊,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼赏迟,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了蠢棱?” 一聲冷哼從身側(cè)響起锌杀,我...
    開(kāi)封第一講書人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎泻仙,沒(méi)想到半個(gè)月后糕再,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡玉转,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年突想,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡猾担,死狀恐怖袭灯,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情绑嘹,我是刑警寧澤稽荧,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站工腋,受9級(jí)特大地震影響姨丈,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜擅腰,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一蟋恬、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧趁冈,春花似錦歼争、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至呀邢,卻和暖如春洒沦,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背价淌。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工申眼, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人蝉衣。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓括尸,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親病毡。 傳聞我的和親對(duì)象是個(gè)殘疾皇子濒翻,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容