用 JavaScript 學習資料結構和演算法:集合(Set)篇

什麼是集合(Set)?

集合是一個源自於數學理論中擁有不同元素的集合:

N = {0, 1, 2, 3, 4, 5, 6, ...}

空集合:{}

其特性在於它是由一組無序且不重複的項目組成。你也可以想成是一個沒有重複元素和無順序的陣列。在這篇文章我們會介紹如何實作集合資料結構並使用 交集、聯集、差集等集合操作方式。

集合初體驗

事實上,在 ES6 中就有原生的 Set,在這邊我們試著使用 JavaScript 物件模仿 ES6 的 Set 設計集合資料結構(使用物件好處是物件 key 是唯一)。

The Set object lets you store unique values of any type, whether primitive values or object references.

  1. 建立集合類別和方法

    function Set() {
    var items = {};
    this.add(value) {};
    this.remove(value) {};
    this.has(value) {};
    this.clear() {};
    this.size() {};
    this.values() {};
    }
    
    • has(value):判斷是否元素在集合中,若有回傳 true,反之傳回 false
    this.has = function(value) {
    return items.hasOwnProperty(value);
    // 由於我們是使用 JavaScript 物件實作所以也可以使用 value in items
    }
    
    • add(value):新增元素到集合
    this.add = function(value) {
    if(!this.has(value)) {
    items[value] = value;
    return true;
    }
    return false;
    }
    
    • remove(value):刪除元素
    this.remove = function(value) {
    if(this.has(value)) {
    delete items[value];
    return true;
    }
    return false;
    };
    
    • clear():移除集合所有元素
    this.clear = function() {
    items = {};
    }
    
    • size():回傳集合元素數量
    1. 使用類似於 Linked List 的 length 變數計算法,當新增、刪除元素時順便增減長度
    this.size = function() {
    return length;
    }
    
    1. 使用 JavaScript 內建 Object 類別的內建函數 keys
    this.size = function() {
    return Object.keys(items).length;
    }
    
    1. 手動迭代判斷是否存在集合中並累加個數
    this.size = function() {
    let count = 0;
    // 特別注意在 JavaScript 中 for in 會一起把繼承於 Object 類別和物件自身的所有相關非相關資料結構的屬性一起迭代出來
    for(let prop in items) {
     // 判斷是否屬於 items 的屬性
     if(items.hasOwnProperty(prop)) {
      ++count;
     }
     return count;
    }
    }
    
    • values():回傳集合所有值,使用 JavaScript 內建 Object 類別的內建函數 keys 以陣列形式回傳
    this.values = function() {
    return Object.keys(items);
    }
    

    另外一種瀏覽器相容性較高的寫法

    this.value = function() {
    let keys = [];
    for(let key in items) {
    keys.push(key);
    }
    return keys;
    }
    
  2. 使用集合類別

    const set = new Set();
    set.add(12);
    console.log(set.values());
    console.log(set.has(12));
    console.log(set.size());
    set.add(12);
    set.add(7);
    set.remove(12);
    set.add(1);
    console.log(set.has(12));
    console.log(set.values());
    console.log(set.size());
    

集合操作

用 JavaScript 學習資料結構和演算法:集合(Set)篇

參考數學上的集合概念,我們可以針對集合進行以下操作:

  1. 聯集
    對於給定兩集合,回傳一個包含兩個集合中所有元素的新集合

    this.union = function(otherSet) {
    // 首先建立代表聯集的新集合
    let unionSet = new Set();
    let values = this.values();
    for(var i = 0; i < values.length; i++) {
    unionSet.add(values[i]);
    }
    values = otherSet.values();
    for(let j = 0; j < values.length; j++) {
    unionSet.add(values[i]);
    }
    return unionSet;
    }
    

    在 console 測試:

    let setA = new Set();
    setA.add(1);
    setA.add(4);
    setA.add(2);
    
    let setB = new Set();
    setB.add(1);
    setB.add(4);
    setB.add(2);
    setB.add(7);
    
    let unionSet = setA.unique(setB);
    console.log(unionSet);
    
  2. 交集
    對於給定兩集合,回傳一個包含兩個集合中共有元素的新集合

    this.intersection = function(otherSet) {
    let intersectionSet = new Set();
    let values = this.values();
    for(let i = 0; i < values.length; i++) {
    if(otherSet.has(values[i])) {
     intersectionSet.add(values[i]);
    }
    }
    return intersectionSet;
    }
    

    在 console 測試:

    let setA = new Set();
    setA.add(1);
    setA.add(4);
    setA.add(2);
    
    let setB = new Set();
    setB.add(1);
    setB.add(4);
    setB.add(2);
    setB.add(7);
    
    let intersectionSet = setA.intersection(setB);
    console.log(intersectionSet);
    
  3. 差集
    對於給定兩集合,回傳一個包含所有存在第一個集合但不存在於第二集合的元素集合

    this.difference = function(otherSet) {
    let differenceSet = new Set();
    let values = this.values();
    for(let i = 0; i < values; i++) {
    if(!otherSet.has(values[i])) {
     differenceSet.add(values[i]);
    }
    }
    return differenceSet;
    }
    

    在 console 測試:

    let setA = new Set();
    setA.add(1);
    setA.add(4);
    setA.add(2);
    
    let setB = new Set();
    setB.add(1);
    setB.add(4);
    setB.add(2);
    setB.add(7);
    
    let differenceSet = setA.difference(setB);
    console.log(differenceSet);
    
  4. 子集
    驗證給定集合是否為另一個集合的子集

    this.subSet = function(otherSet) {
    if(this.size() > otherSet.size()) {
    return false;
    } else {
    let values = this.values();
    for(let i = 0; i < values.length; i++) {
     if(!otherSet.has(values[i])) {
      return false;
     }
     return true;
    }
    }
    }
    

    在 console 測試:

    let setA = new Set();
    setA.add(1);
    setA.add(4);
    setA.add(2);
    
    let setB = new Set();
    setB.add(1);
    setB.add(4);
    setB.add(2);
    setB.add(7);
    
    let subSet = setA.subSet(setB);
    console.log(subSet);
    

總結

在這篇文章中我們學會了:

  1. 什麼是集合(Set)?
  2. 建立集合類別和方法
  3. 集合操作(聯集、交集、差集、子集)

延伸閱讀

  1. MDN Set

(image via applewikipedia

關於作者:
@kdchang 文藝型開發者,夢想是做出人們想用的產品和辦一所心目中理想的學校。A Starter & Maker. JavaScript, Python & Arduino/Android lover.:)


#javascript #ECMAScript2015 #ES6 #data structure #algorithm #Dictionary #Hash Table #資料結構 #演算法 #陣列 #雜湊表 #字典 #佇列 #Queue #set #集合









Related Posts

JavaScript 預編譯

JavaScript 預編譯

自駕車 Sensor Fusion in Visual Perception 簡介

自駕車 Sensor Fusion in Visual Perception 簡介

JavaScript 程式執行原理:Closure

JavaScript 程式執行原理:Closure




Newsletter




Comments