数据结构之集合

学习github地址

构建数据集合

集合是由一组无序且唯一（即不能重复）的项组成的。该数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中

可以把集合想象成一个既没有重复元素，也没有顺序概念的数组

创建集合类

将基于 ES6 的 Set 类来实现我们自己的 Set 类。我们也会实现一些原生 ES6 没有提供的集合运算，例如并集、交集和差集。

1. 要声明一些集合可用的方法, 模拟与 ECMAScript 2015 实现相同的 Set 类
   • add(element):向集合添加一个新元素
   • delete(element):从集合移除一个元素
   • has(element): 如果元素在集合中, 返回 true, 否则返回 false
   • clear():移除集合中的所有元素
   • size():返回集合所包含元素的数量.
   • values():返回一个包含集合中所有值的数组

class Set {
  constructor() {
    this.items = {};
  }

  add(element) {
    if (!this.has(element)) {
      // 添加一个 element 的时候，把它同时作为键和值保存
      this.items[element] = element;
      return true;
    }
    return false;
  }

  has(element) {
    // 该方法返回一个表明对象是否具有特定属性的布尔值
    return Object.prototype.hasOwnProperty.call(this.items, element);
  }

  delete(element) {
    if (this.has(element)) {
      delete this.items[element];
      return true;
    }
    return false;
  }

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

  size() {
    return Object.keys(this.items).length;
  }

  sizeLegacy() {
    let count = 0;
    for (let key in this.items) {
      if (this.items.hasOwnProperty(key)) {
        count++;
      }
      return count;
    }
  }

  values() {
    return Object.values(this.items);
  }

  valuesLegacy() {
    let values = [];
    for (let key in this.items) {
      if (this.items.hasOwnProperty(key)) {
        values.push(key);
      }
    }
    return values;
  }
}

2. 集合运算

   集合是数学中基础的概念，在计算机领域也非常重要

   • 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
   • 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
   • 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集
     合的元素的新集合。
   • 子集：验证一个给定集合是否是另一集合的子集。

class Set {
  constructor() {
    this.items = {};
  }

  add(element) {
    if (!this.has(element)) {
      // 添加一个 element 的时候，把它同时作为键和值保存
      this.items[element] = element;
      return true;
    }
    return false;
  }

  has(element) {
    // 该方法返回一个表明对象是否具有特定属性的布尔值
    return Object.prototype.hasOwnProperty.call(this.items, element);
  }

  delete(element) {
    if (this.has(element)) {
      delete this.items[element];
      return true;
    }
    return false;
  }

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

  size() {
    return Object.keys(this.items).length;
  }

  sizeLegacy() {
    let count = 0;
    for (let key in this.items) {
      if (this.items.hasOwnProperty(key)) {
        count++;
      }
      return count;
    }
  }

  values() {
    return Object.values(this.items);
  }

  valuesLegacy() {
    let values = [];
    for (let key in this.items) {
      if (this.items.hasOwnProperty(key)) {
        values.push(key);
      }
    }
    return values;
  }

  // 并集
  // 没有副作用的方法和函数被称为纯函数
  union(otherSet) {
    const unionSet = new Set();
    this.values().forEach((value) => unionSet.add(value));
    otherSet.values().forEach((value) => unionSet.add(value));
    return unionSet;
  }

  // 交集: 是 x（元素）存在于 A 中，且 x 存在于 B 中
  intersection(otherSet) {
    // 创建一个新的 Set 实例
    const intersectionSet = new Set();
    const values = this.values();
    const otherValues = otherSet.values();
    let biggerSet = values;
    let smallerSet = otherValues;
    // 比较两个集合的元素个数，如果另一个集合元素个数多于当前集合的话，我们就交换 biggerSet 和 smallerSet 的值
    if (otherValues.length - values.length > 0) {
      biggerSet = otherValues;
      smallerSet = values;
    }

    // 迭代较小集合
    smallerSet.forEach((value) => {
      if (biggerSet.includes(value)) {
        intersectionSet.add(value);
      }
    });

    return intersectionSet;
  }

  // 差集: 是 x（元素）存在于 A 中，且 x 不存在于 B 中
  difference(otherSet) {
    const differenceSet = new Set();
    this.values().forEach((value) => {
      // 得到所有存在于集合 A 但不存在于集合 B 的元素
      if (!otherSet.has(value)) {
        differenceSet.add(value);
      }
    });

    return differenceSet;
  }

  // 子集: 集合 A 中的每一个 x（元素），也需要存在于集合 B 中
  isSubsetOf(otherSet) {
    if (this.size() > otherSet.size()) return false;

    let isSubset = true;

    this.values().every((value) => {
      if (!otherSet.has(value)) {
        isSubset = false;
        return false;
      }

      return true;
    });

    return isSubset;
  }
}

ES6 的 Set 类 与我们写的 Set 类的区别

• ES6 的 Set 的 values 方法返回 Iterator, 而不是值构成的数组
• 我们实现的 size 方法返回 set 中存储的值的个数，而 ES6 的 Set 则有一个 size 属性

ES6 的 Set 没有实现交集, 差集, 并集, 自己等数学运算, 我们来模拟一下

// 并集
new Set([...setA, ...setB]);

// 交集
new Set([...setA].filter((x) => setB.has(x)));

// 差集
new Set([...setA].filter((x) => !setB.has(x)));