集合(Set)
說起集合，就想起剛進高中時，數學第一課講的就是集合。因此在學習集合這種數據結構時，倍感親切。
集合的基本性質有一條: 集合中元素是不重復的。因為這種性質，所以我們選用了對象來作為集合的容器，而非數組。
雖然數組也能做到所有不重復，但終究過於繁瑣，不如集合。
集合的操作
集合的基本操作有交集、並集、差集等。這兒我們介紹JavaScipt集合中交集、並集、差集的實現。
JavaScipt中集合的實現
首先，創建一個構造函數。
/**
* 集合的構造函數
*/
function Set方法 {
/**
* 集合元素的容器，以對象來表示
* @type {Object}
*/
var items = {};
}
集合需要有如下方法:
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數據結構
感想
到了這兒，已經掌握了一些基本的數據結構。剩下的都是難啃的骨頭了(對我而言)。
字典的散列表、圖、樹、排序算法。算是四大金剛，所以近期關於數據結構與算法系列的文章，可能會更新的很慢。對我來說，也算是一個坎。希望這個寒假，能跨過這個坎。