数据结构与算法-集合

几乎每种编程语言中，都有集合结构。集合比较常见的实现方式是哈希表，这里使用 JavaScript 的 Object 进行封装。

认识集合

集合通常是由一组无序的、不能重复的元素构成。

数学中常指的集合中的元素是可以重复的，但是计算机中集合的元素不能重复。

• 集合可以看成是一种特殊的数组，特殊之处在于里面的元素没有顺序，也不能重复。

• 没有顺序意味着不能通过下标值进行访问，不能重复意味着相同的对象在集合中只会存在一份。

ES6中包含了Set类，其实我们可以不封装，直接使用它，但是为了明确集合的内部实现机制，这里还是自己来封装一下这个Set类。

集合

常见操作

• add(value) 向集合添加一个新的项。
• remove(value) 从集合移除一个值。
• has(value) 如果值在集合中，返回 true，否则返回false。
• clear() 移除集合中的所有项。
• size() 返回集合所包含元素的数量。与数组的 length 属性类似。
• values() 返回一个包含集合中所有值的数组。

完整封装

/**
 * 集合 基于Object
 */
module.exports = class Set {
  constructor () {
    this.items = {}
  }

  // 向集合添加一个新的项
  add (value) {
    if (this.has(value)) return false

    this.items[value] = value
    return true
  }

  remove (value) {
    if (!this.has(value)) return false

    delete this.items[value]
    return true
  }

  // 判断集合中是否存在value值，存在返回 true，否则返回 false
  has (value) {
    return this.items.hasOwnProperty(value)
  }

  // 清空集合中所有的元素
  clear () {
    this.items = {}
  }

  // 获取集合的大小
  size () {
    return Object.keys(this.items).length
  }

  // 获取集合中所有的值
  values () {
    return Object.keys(this.items)
  }

  // 求两个集合的合集
  union (otherSet) {
    const unionSet = new Set()

    // 将当前集合 this 的所有 value，添加到新集合 unionSet 中
    for (const value of this.values()) {
      unionSet.add(value)
    }

    // 将 otherSet 集合的所有 value，添加到新集合 unionSet 中
    for (const value of otherSet.values()) {
      unionSet.add(value)
    }

    return unionSet
  }

  // 求两个集合的交集
  intersection (otherSet) {
    const intersectionSet = new Set()

    // 从当前集合中取出每一个 value，判断是否在 otherSet 集合中存在
    for (const value of this.values()) {
      if (otherSet.has(value)) {
        intersectionSet.add(value)
      }
    }

    return intersectionSet
  }

  // this 与 otherSet 的差集
  difference (otherSet) {
    const differenceSet = new Set()

    // 从当前集合中取出每一个 value，判断是否在 otherSet 集合中存在，
    // 不存在的即为this 与 otherSet 的差集差集
    for (const value of this.values()) {
      if (!otherSet.has(value)) {
        differenceSet.add(value)
      }
    }

    return differenceSet
  }

  // this 是否是 otherSet 的子集
  subset (otherSet) {
    const subSet = new Set()
    // 从当前集合中取出每一个 value，判断是否在 otherSet 集合中存在，有不存在的返回 false
    // 即 this 不是 otherSet 的子集
    for (const value of this.values()) {
      if (!otherSet.has(value)) {
        return false
      }
    }

    return true
  }
}

测试

const Set = require('../../lib/Set')

const set = new Set()

// add
console.log('add', set.add('abc')) // add true
console.log('add', set.add('abc')) // add false
console.log('add', set.add('123')) // add true
console.log('add', set.add('zxc')) // add true
console.log('Set', set) // Set Set { items: { '123': '123', abc: 'abc', zxc: 'zxc' } }

// has
console.log('has', set.has('123')) // has true
console.log('has', set.has('456')) // has false

// remove
console.log('remove', set.remove('abc')) // remove true
console.log('Set', set) // Set Set { items: { '123': '123', zxc: 'zxc' } }

// size
console.log('size', set.size()) // size 2

// values
console.log('values', set.values()) // values [ '123', 'zxc' ]

// clear
console.log('clear', set.clear()) // clear undefined
console.log('values', set.values()) // values []

const setA = new Set();
setA.add('111')
setA.add('222')
setA.add('333')

const setB = new Set();
setB.add('111')
setB.add('222')
setB.add('aaa')
setB.add('ccc')

// union
console.log('SetA和SetB的合集', setA.union(setB).values()) // SetA和SetB的合集 [ '111', '222', '333', 'aaa', 'ccc' ]

// intersection
console.log('SetA和SetB的交集',  setA.intersection(setB).values()) // SetA和SetB的交集 [ '111', '222' ]

// difference
console.log('SetA对SetB的差集', setA.difference(setB).values()) // SetA对SetB的差集 [ '333' ]

// subset
console.log('SetA是否是SetB的子集', setA.subset(setB)) // SetA是否是SetB的子集 false