数据结构——集合

一、集合结构

集合中比较常见的实现方式就是哈希表，集合通常是由一组无序的，不能重复的元素构成

集合可以看作一个特殊的数组，没有顺序意味着不能通过下标进行访问，不能重复说明相同的对象集合中只能存在一份

二、集合中常见的方法

add(value)：向集合添加一个新的项。

remove(value)：从集合移除一个值。

has(value)：如果值在集合中，返回true，否则返回false。

clear()：移除集合中的所有项。

size()：返回集合所包含元素的数量。与数组的length属性类似。

values()：返回一个包含集合中所有值的数组。

三、集合的封装

// 封装一个集合类
function Set() {
  // 属性
  this.items = {}
  // add方法
  Set.prototype.add = function (value) {
    // 如果集合中已经存在该元素，拒绝添加
    if (this.has(value)) return false
    this.items[value] = value
    return true
  }
  // has方法
  Set.prototype.has = function (value) {
    return this.items.hasOwnProperty(value)
  }
  // remove方法
  Set.prototype.remove = function (value) {
    // 判断集合中是否包含该元素
    if (!this.has(value)) return false
    delete this.items[value]
    return true
  }

  // clear方法
  Set.prototype.clear = function () {
    this.items = {}
  }
  // size方法
  Set.prototype.size = function () {
    return Object.keys(this.items).length
  }

  // values方法，获取集合中所有的值，返回数组
  Set.prototype.values = function () {
    return Object.keys(this.items)
  }
}

let set = new Set()
console.log(set.add('a'))   // true
console.log(set.add('a'))   // false
console.log(set.add('b'))   // true
console.log(set.add('c'))   // true

console.log(set.remove('c'))  // true
console.log(set.values())     // [ 'a', 'b' ]
console.log(set.remove('c'))  // false

console.log(set.has('c'))   // false

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

set.clear()
console.log(set.size())   // 0

四、集合间的操作

• 并集：返回包含两个集合所有元素的新集合
• 交集：返回包含两个集合共有元素的新集合
• 差集：返回包含第一个集合不包含第二个集合的所有元素的集合
• 子集：一个集合所有元素包含在另一个集合中

代码实现

  // 集合并集操作
  Set.prototype.union = function (otherSet) {
    // 创建一个新的集合
    let unionSet = new Set()
    // 将A集合所有的元素放入新集合中
    let values = this.values()
    for (let i = 0; i < values.length; i++) {
      unionSet.add(values[i])
    }
    // 将B集合中的元素放入新集合中（A中不存在的）
    values = otherSet.values()
    for (let i = 0; i < values.length; i++) {
      unionSet.add(values[i])
    }
    return unionSet
  }

  // 集合交集操作
  Set.prototype.intersection = function (otherSet) {
    // 新建一个空集合
    let intersectionSet = new Set()
    // 逐个取出集合A中的元素，判断B中是否存在
    let values = this.values()
    for (let i = 0; i < values.length; i++) {
      let item = values[i]
      if (otherSet.has(item)) {// 存在则加入新集合
        intersectionSet.add(item)
      }
    }
    return intersectionSet
  }

  // 集合差集操作
  Set.prototype.difference = function (otherSet) {
    // 新建一个空集合
    let differenceSet = new Set()
    // 逐个取出集合A中的元素，判断B中是否存在
    let values = this.values()
    for (let i = 0; i < values.length; i++) {
      let item = values[i]
      if (!otherSet.has(item)) {// 不存在则加入新集合
        differenceSet.add(item)
      }
    }
    return differenceSet
  }

  // 集合的子集判断
  Set.prototype.subSet = function (otherSet) {
    let values = this.values()
    for (let i = 0; i < values.length; i++) {
      if (!otherSet.has(values[i])) return false
    }
    return true
  }

结果验证

let setA = new Set()
setA.add('A')
setA.add('B')
setA.add('C')
let setB = new Set()
setB.add('C')
setB.add('D')
setB.add('E')

// 集合的并集操作
let unionSet = setA.union(setB)
console.log(unionSet.values())    // [ 'A', 'B', 'C', 'D', 'E' ]
// 集合的交集操作
let intersectionSet = setA.intersection(setB)
console.log(intersectionSet.values())   // [ 'C' ]
// 集合的差集操作
let differenceSet = setA.difference(setB)
console.log(differenceSet.values())   // [ 'A', 'B' ]
// 子集的判断
console.log(setA.subSet(setB))   // false
setA.remove('A')
setA.remove('B')
console.log(setA.subSet(setB))    // true