【前端数据结构基础】集合

摘要：前言集合是一种包含不同元素的数据结构。二构造集合数据结构我们将使用实现集合结构，各部分功能使用注释说明。参考资料数据结构与算法描述第章集合由于书上的源代码出现了错误，因此代码根据实际运行结果做了相应修改。

集合是一种包含不同元素的数据结构。集合最重要的两个特性是：首先，集合中的成员是无序的；其次，集合中不允许相同成员存在。

我们必须要了解以下关于集合的定义：

不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。

如果两个集合的成员完全相同，则称两个集合相等。

如果一个集合中所有的成员都属于另外一个集合，则前一集合称为后一集合的子集。

对集合的操作有如下几种：

并集：将两个集合中的成员进行合并，得到一个新集合。

交集：两个集合中共同存在的成员组成一个新的集合。

补集：属于一个集合而不属于另一个集合的成员组成的集合。

我们将使用JavaScript实现集合结构，各部分功能使用注释说明。
存储数据我们使用的是数组。

/**
 * Set() 定义集合类
 */
function Set () {
  this.dataStore = []
  this.add = add
  this.remove = remove
  this.size = size
  this.union = union
  this.intersect = intersect
  this.subset = subset
  this.difference = difference
  this.show = show
  this.contains = contains
}

/**
 * add() 该方法用于为集合类添加值
 * @param {*} data
 */
function add (data) {
  if (this.contains(data)) {
    return false
  } else {
    this.dataStore.push(data)
    return true
  }
}

/**
 * remove() 该方法用于为集合类删除值
 * @param {*} data
 */
function remove (data) {
  let pos = this.dataStore.indexOf(data)
  if (pos > -1) {
    this.dataStore.splice(pos, 1)
    return true
  } else {
    return false
  }
}

/**
 * show() 该方法用于显示集合中的所有元素
 */
function show () {
  return this.dataStore
}

/**
 * size() 该方法用于获取集合的长度
 */
function size () {
  return this.dataStore.length
}

/**
 * union() 该方法用于求两个集合的并集
 * @param {*} set
 */
function union (set) {
  let tempSet = new Set()
  // 将当前集合中的元素加入到临时集合中
  for (let i = 0; i < this.size(); i++) {
    tempSet.add(this.dataStore[i])
  }
  // 判断第二个集合中的元素在临时集合中是否存在，若不存在，则加入该元素
  for (let i = 0; i < set.size(); i++) {
    if (!tempSet.contains(set.dataStore[i])) {
      tempSet.add(set.dataStore[i])
    }
  }
  return tempSet
}

/**
 * intersect() 该方法用于求两集合的交集
 * @param {*} set
 */
function intersect (set) {
  let tempSet = new Set()
  // 遍历set
  for (let i = 0; i < set.size(); i++) {
    // 当该集合中存在此元素，则将该元素插入至tempSet
    if (this.contains(set.dataStore[i])) {
      tempSet.add(set.dataStore[i])
    }
  }
  return tempSet
}

/**
 * subset() 该方法用于判断当前集合是否为set集合的子集
 * @param {*} set
 */
function subset (set) {
  // 当该集合的长度大于set集合的长度，则该集合不可能为set集合的子集
  if (this.size() > set.size()) {
    return false
  }
  for (let i of this.dataStore) {
    if (!set.contains(i)) {
      return false
    }
  }
  return true
}

/**
 * difference() 该方法用于返回属于该集合但不属于set集合的成员
 * @param {*} set
 */
function difference (set) {
  let tempSet = new Set()
  for (let i of this.dataStore) {
    if (!set.contains(i)) {
      tempSet.add(i)
    }
  }
  return tempSet
}

/**
 * contains() 该方法用于判断元素是否存在于集合中
 * @param {*} data
 */
function contains (data) {
  if (this.dataStore.indexOf(data) > -1) {
    return true
  } else {
    return false
  }
}

以上代码，个人认为非常重要的方法就是indexOf()来判断数组中是否存在该元素，通过该方法来判断当前能否向集合中添加元素。

使用JavaScript实现集合数据结构相对来说比较简单。

参考资料：数据结构与算法JavaScript描述 第9章 集合 
由于书上的源代码出现了错误，因此代码根据实际运行结果做了相应修改。