說起集合,就想起剛進高中時,數學第一課講的就是集合,因此學習集合這種資料結構時倍感親切。集合有一條基本性質:集合中的元素是不重複的。正因為這種性質,我們選用物件而非陣列作為集合的容器——雖然陣列也能做到元素不重複,但終究過於繁瑣。
首先建立一個構造函式:
/**
* 集合的構造函式
*/
function Set() {
/**
* 集合元素的容器,以物件來表示
* @type {Object}
*/
var items = {};
}
集合需要具備以下方法:has、add、remove、clear、size、values、union(並集)、intersection(交集)、difference(差集)、subset(子集判斷)。
集合中元素不重複,所以在其他操作前,必須用 has 確認集合是否有某個元素:
this.has = function(value) {
return items.hasOwnProperty(value);
};
this.add = function(value) {
if (!this.has(value)) {
items[value] = value;
return true;
}
return false;
};
this.remove = function(value) {
if (this.has(value)) {
delete items[value];
return true;
}
return false;
};
this.clear = function() {
this.items = {};
};
第一種方法使用 Object.keys(僅支援 IE9 及以上),第二種則適用於所有瀏覽器:
this.size = function() {
return Object.keys(items).length;
}
this.sizeLegacy = function() {
var count = 0;
for (var prop in items) {
if (items.hasOwnProperty(prop)) { ++count; }
}
return count;
}
返回集合轉換的陣列,同樣有兩種實作:
this.values = function() {
return Object.keys(items);
};
this.valuesLegacy = function() {
var keys = [];
for (var key in items) {
keys.push(key);
};
return keys;
};
this.union = function(otherSet) {
var unionSet = new Set();
var values = this.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
values = otherSet.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]); // add 保證不會出現重複元素
}
return unionSet;
};
this.intersection = function(otherSet) {
var interSectionSet = new Set();
var values = this.values();
for (var i = 0; i < values.length; i++) {
if (otherSet.has(values[i])) {
interSectionSet.add(values[i]);
}
}
return interSectionSet;
};
this.difference = function(otherSet) {
var differenceSet = new Set();
var values = this.values();
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
differenceSet.add(values[i]);
}
}
return differenceSet;
};
this.subset = function(otherSet) {
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])) {
return false; // 只要有一個元素不在 otherSet 中,就不是子集
}
}
return true;
}
};
ES6 也提供了 Set,實現一遍之後再去看 ES6 的集合操作,概念會清晰很多。推薦參考阮一峰老師《ECMAScript 6 入門》中對 Set 和 Map 的介紹。
到了這裡,已經掌握了一些基本的資料結構,剩下的都是難啃的骨頭(對我而言):字典、散列表、圖、樹、排序算法。希望這個寒假能跨過這道坎。