JavaScript資料結構與演算法集合(Set)_基礎知識

集合(Set)

說起集合，就想起剛進高中時，數學第一課講的就是集合。因此在學習集合這種資料結構時，倍感親切。
集合的基本性質有一條: 集合中元素是不重複的。因為這種性質，所以我們選用了物件來作為集合的容器，而非陣列。
雖然數組也能做到所有不重複，但終究過於繁瑣，不如集合。

集合的運算

集合的基本操作有交集、並集、差集等。這兒我們介紹JavaScipt集合中交集、並集、差集的實作。

JavaScipt中集合的實作

首先，建立一個建構函式。

/**
 * 集合的构造函数
 */
function Set方法 {
 /**
  * 集合元素的容器，以对象来表示
  * @type {Object}
  */
 var items = {};
}

集合需要有以下方法:

1. has(value): 偵測集合內是否有某個元素
2. add(value): 在集合內加入某個元素
3. remove(value): 移除集合中某個元素
4. clear(value): 清空集合
5. size(): 傳回集合長度
6. values(): 傳回集合轉換的陣列
7. union(otherSet): 傳回兩個集合的並集
8. intersection(otherSet): 傳回兩個集合的交集
9. difference(otherSet): 傳回兩個集合的差集
10. subset(otherSet): 判斷該集合是否為傳入集合的子集

has方法:

說明:集合中元素是不重複的。所以在其它任何操作前，必須用has方法確認集合是否有某個元素。這兒使用了hasOwnProperty方法來檢測。
實作:

/**
 * 检测集合内是否有某个元素
 * @param {Any} value  要检测的元素
 * @return {Boolean}    如果有，返回true
 */
this.has = function(value) {
 // hasOwnProperty的问题在于
 // 它是一个方法，所以可能会被覆写
 return items.hasOwnProperty(value)
};

add方法:

說明: 在集合內加入某個元素。
實作:

/**
 * 给集合内添加某个元素
 * @param {Any} value 要被添加的元素
 * @return {Boolean}    添加成功返回True。
 */
this.add = function(value) {
 //先检测元素是否存在。
 if (!this.has(value)) {
  items[value] = value;
  return true;
 }
 //如果元素已存在则返回false
 return false;
};

remove方法:

說明: 移除集合中某個元素
實作:

/**
 * 移除集合中某个元素
 * @param {Any} value 要移除的元素
 * @return {Boolean}    移除成功返回True。
 */
this.remove = function(value) {
 //先检测元素是否存在。
 if (this.has(value)) {
  delete items[value];
  return true;
 }
 //如果元素不存在，则删除失败返回false
 return false;
};

clear方法:
說明: 清空集合
實作:

/**
 * 清空集合
 */
this.clear = function() {
 this.items = {};
};

size方法

說明: 傳回集合長度，這裡有兩種方法。第一種方法使用了Object.keys這個Api，但只支援IE9以上。第二種則適用於所有瀏覽器。
實作:

/**
 * 返回集合长度，只可用于IE9及以上
 * @return {Number} 集合长度
 */
this.size = function() {
 // Object.keys方法能将对象转化为数组
 // 只可用于IE9及以上，但很方便
 return Object.keys(items).length;
}

/**
 * 返回集合长度，可用于所有浏览器
 * @return {Number} 集合长度
 */
this.sizeLegacy = function() {
 var count = 0;
 for (var prop in items) {
  if (items.hasOwnProperty(prop)) {
   ++count;
  }
 }
 return count;
}

values方法

說明: 傳回集合轉換的數組，這兒也有兩種方法。理由同上。使用了Object.keys，只能支援IE9及以上。
實作:

/**
 * 返回集合转换的数组，只可用于IE9及以上
 * @return {Array} 转换后的数组
 */
this.values = function() {
 return Object.keys(items);
};

/**
 * 返回集合转换的数组，可用于所有浏览器
 * @return {Array} 转换后的数组
 */
this.valuesLegacy = function() {
 var keys = [];
 for (var key in items) {
  keys.push(key)
 };
 return keys;
};

union方法

說明: 傳回兩個集合的並集
實作:

/**
 * 返回两个集合的并集
 * @param {Set} otherSet 要进行并集操作的集合
 * @return {Set}     两个集合的并集
 */
this.union = function(otherSet) {
 //初始化一个新集合，用于表示并集。
 var unionSet = new Set();
 //将当前集合转换为数组，并依次添加进unionSet
 var values = this.values();
 for (var i = 0; i < values.length; i++) {
  unionSet.add(values[i]);
 }

 //将其它集合转换为数组，依次添加进unionSet。
 //循环中的add方法保证了不会有重复元素的出现
 values = otherSet.values();
 for (var i = 0; i < values.length; i++) {
  unionSet.add(values[i]);
 }

 return unionSet;
};

intersection方法

說明: 傳回兩個集合的交集
實作:

/**
 * 返回两个集合的交集
 * @param {Set} otherSet 要进行交集操作的集合
 * @return {Set}     两个集合的交集
 */
this.intersection = function(otherSet) {
 //初始化一个新集合，用于表示交集。
 var interSectionSet = new Set();
 //将当前集合转换为数组
 var values = this.values();
 //遍历数组，如果另外一个集合也有该元素，则interSectionSet加入该元素。
 for (var i = 0; i < values.length; i++) {

  if (otherSet.has(values[i])) {
   interSectionSet.add(values[i])
  }
 }

 return interSectionSet;
};

difference方法

說明: 傳回兩個集合的差集
實作:

/**
 * 返回两个集合的差集
 * @param {Set} otherSet 要进行差集操作的集合
 * @return {Set}     两个集合的差集
 */
this.difference = function(otherSet) {
 //初始化一个新集合，用于表示差集。
 var differenceSet = new Set();
 //将当前集合转换为数组
 var values = this.values();
 //遍历数组，如果另外一个集合没有该元素，则differenceSet加入该元素。
 for (var i = 0; i < values.length; i++) {

  if (!otherSet.has(values[i])) {
   differenceSet.add(values[i])
  }
 }

 return differenceSet;
};

subset方法

說明: 判斷該集合是否為傳入集合的子集。這段程式碼在我自己寫完後與書上一比對，覺得自己超級low。我寫的要遍歷數組三次，書上的只需要一次，演算法複雜度遠低於我的。
實作:

/**
 * 判断该集合是否为传入集合的子集
 * @param {Set} otherSet 传入的集合
 * @return {Boolean}   是则返回True
 */
this.subset = function(otherSet) {
 // 第一个判定,如果该集合长度大于otherSet的长度
 // 则直接返回false
 if (this.size() > otherSet.size()) {
  return false;
 } else {
  // 将当前集合转换为数组
  var values = this.values();

  for (var i = 0; i < values.length; i++) {

   if (!otherSet.has(values[i])) {
    // 第二个判定。只要有一个元素不在otherSet中
    // 那么则可以直接判定不是子集，返回false
    return false;
   }
  }

  return true;
 }
};

ES6中的集合

ES6也提供了集合，但之前看ES6的集合操作一直迷迷糊糊的。實現一遍後再去看，感覺概念清晰了許多。
具體的我掌握的不是很好，還在學習中，就不寫出來啦~推薦看阮一峰老師的《ECMAScript 6入門》中對ES6 Set的介紹。
《ECMAScript 6入門》– Set與Map資料結構

感想

到了這兒，已經掌握了一些基本的資料結構。剩下的都是難啃的骨頭了(對我而言)。

字典的散列表、圖、樹、排序演算法。算是四大金剛，所以近期關於資料結構與演算法系列的文章，可能會更新的很慢。對我來說，也算是個坎。希望這個寒假，能跨過這個坎。