DIV CSS 佈局教程網

JavaScript 資料結構與算法之集合(Set)
編輯:JavaScript基礎知識     

集合(Set)

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

JavaScript 中集合的實現

首先建立一個構造函式:

/**
 * 集合的構造函式
 */
function Set() {
  /**
   * 集合元素的容器,以物件來表示
   * @type {Object}
   */
  var items = {};
}

集合需要具備以下方法:has、add、remove、clear、size、values、union(並集)、intersection(交集)、difference(差集)、subset(子集判斷)。

has 方法

集合中元素不重複,所以在其他操作前,必須用 has 確認集合是否有某個元素:

this.has = function(value) {
  return items.hasOwnProperty(value);
};

add 方法

this.add = function(value) {
  if (!this.has(value)) {
    items[value] = value;
    return true;
  }
  return false;
};

remove 方法

this.remove = function(value) {
  if (this.has(value)) {
    delete items[value];
    return true;
  }
  return false;
};

clear 方法

this.clear = function() {
  this.items = {};
};

size 方法

第一種方法使用 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;
}

values 方法

返回集合轉換的陣列,同樣有兩種實作:

this.values = function() {
  return Object.keys(items);
};
this.valuesLegacy = function() {
  var keys = [];
  for (var key in items) {
    keys.push(key);
  };
  return keys;
};

union 方法(並集)

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;
};

intersection 方法(交集)

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;
};

difference 方法(差集)

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;
};

subset 方法(子集判斷)

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 中的集合

ES6 也提供了 Set,實現一遍之後再去看 ES6 的集合操作,概念會清晰很多。推薦參考阮一峰老師《ECMAScript 6 入門》中對 Set 和 Map 的介紹。

感想

到了這裡,已經掌握了一些基本的資料結構,剩下的都是難啃的骨頭(對我而言):字典、散列表、圖、樹、排序算法。希望這個寒假能跨過這道坎。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved