JS中的算法與數(shù)據(jù)結(jié)構(gòu)之集合(Set)實(shí)例詳解

更新時(shí)間：2019年08月20日 10:56:03 作者：Cryptic

這篇文章主要介紹了JS中的算法與數(shù)據(jù)結(jié)構(gòu)之集合(Set),結(jié)合實(shí)例形式詳細(xì)分析了javascript中集合的概念、原理、定義及相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了JS中的算法與數(shù)據(jù)結(jié)構(gòu)之集合(Set)。分享給大家供大家參考，具體如下：

集合(Set)

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

實(shí)際上，很多編程語(yǔ)言中，集合并不是一種數(shù)據(jù)類(lèi)型，但是如果你需要?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ì)其一些定義做了解

不包含任何成員的集合稱(chēng)為空集，包含一切可能成員的集合稱(chēng)為全集。
如果兩個(gè)集合里的成員都完全相同，則稱(chēng)兩個(gè)集合相等。
如果一個(gè)集合所有成員都包含于另一個(gè)集合，則前一集合稱(chēng)為后一集合的一個(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 類(lèi)型，我們這里選擇用 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 方法很類(lèi)似，首先要檢查待刪除元素是否存在于數(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í)，才去判斷集合類(lèi)的成員是否都屬于待比較集合，如果有一個(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ò)的收獲~

感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun測(cè)試上述代碼運(yùn)行效果。

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: