JavaScript数据结构与算法（六）——集合

集合（set）是一种包含不同元素的数据结构。集合中的元素称为成员。

JavaScript中的集合与数学中的集合在很多地方上是相似的，例如，他们都拥有如下特性：

集合中的成员是无序的（无序性）
集合中不允许相同成员存在（互异性）

基本定义

与数学中的集合类似，他们都可以分为如下几类：

空集：不包含任何元素（成员）的集合称为空集
子集：如果一个集合中所有的成员都属于另外一个集合，则称那个集合为另一个集合的子集
相等：如果两个集合的成员完全相同，则称两个集合相等
全集：包含一切可能元素的集合

基本操作

这些基本操作也是在数学集合中出现的几个概念

并集：将两个集合中的成员进行合并，得到一个新集合
交集：两个集合中共同存在的成员组成一个新的集合
补集：属于一个集合而不属于另一个集合的成员组成的集合

实现一个集合

现在我们来实现一个JS集合，我们之前实现的很多种数据类型都是基于数组的，集合也不例外

function set() {
  this.dataStore = [];
}

接着我们实现一些基本方法：

add() 方法

add()方法用来向集合中加入元素（成员），因为集合的“互异性”，所以我们必须要检查一下集合中是否已经存在有要加入的元素：

function add(data) {
  if (this.dataStore.indexOf(data) < 0) {
    this.dataStore.push(data);
      return true;
    }
  else {
    return false;
  }
}

remove()方法

remove()方法和add()方法的工作原理类似。首先检查待删元素是否在数组中，如果在，则使用数组的splice()方法删除该元素并返回true；否则，返回false ，表示集合中并不
存在这样一个元素。下面是remove()方法的定义

function remove(data) {
  var pos = this.dataStore.indexOf(data);
  if (pos > -1) {
    this.dataStore.splice(pos,1);
    return true;
  }
  else {
    return false;
  }
}

show()方法

show()方法用来展示该集合中的所有成员，非常简单

function show() {
  return this.dataStore;
}

contains()方法

contains()方法用来判断一个元素是否存在于这个集合之中

function contains(data) {
  if (this.dataStore.indexOf(data) > -1) {
    return true;
  }
  else {
    return false;
  }
}

union()方法

union()方法执行并集操作，将两个集合合并成一个。该方法首先将第一个集合里的成员悉数加入一个临时集合，然后检查第二个集合中的成员，看它们是否也同时属于第一个集合。如果属于，则跳过该成员，否则就将该成员加入临时集合。

function union(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; ++i) {
    tempSet.add(this.dataStore[i]);
  }
  for (var i = 0; i < set.dataStore.length; ++i) {
    if (!tempSet.contains(set.dataStore[i])) {
      tempSet.dataStore.push(set.dataStore[i]);
    }
  }
  return tempSet;
}

subset()方法

subset()方法是用来判断一个集合是否属于另一个集合的子集。

subset()方法首先要确定该集合的长度是否小于待比较集合。如果该集合比待比较集合还要大，那么该集合肯定不会是待比较集合的一个子集。当该集合的长度小于待比较集合时，再判断该集合内的成员是否都属于待比较集合。如果有任意一个成员不属于待比较集合，则返回 false ，程序终止。如果一直比较完该集合的最后一个元素，所有元素都属于待比较集合，那么该集合就是待比较集合的一个子集，该方法返回 true 。

我们先要实现一个size()方法来返回当前数组的长度：

function size() {
  return this.dataStore.length;
}

接着我们实现subset()方法：

function subset(set) {
  if (this.size() > set.size()) {
    return false;
  }
  else {
    for each (var member in this.dataStore) {
      if (!set.contains(member)) {
        return false;
      }
    }
  }
  return true;
}

difference()

difference()方法返回一个新集合，该集合包含的是那些属于第一个集合但不属于第二个集合的成员。此方法定义如下：

function difference(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; ++i) {
    if (!set.contains(this.dataStore[i])) {
      tempSet.add(this.dataStore[i]);
    }
  }
  return tempSet;
}

完整代码

最后我们得到的完整的代码是这样的：

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;
}
function add(data) {
  if (this.dataStore.indexOf(data) < 0) {
  this.dataStore.push(data);
  return true;
  }
  else {
   return false;
  }
}
function remove(data) {
  var pos = this.dataStore.indexOf(data);
  if (pos > -1) {
    this.dataStore.splice(pos,1);
    return true;
  }
  else {
    return false;
  }
}
function show() {
  return this.dataStore;
}
function contains(data) {
  if (this.dataStore.indexOf(data) > -1) {
    return true;
  }
  else {
    return false;
  }
}
function union(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; ++i) {
    tempSet.add(this.dataStore[i]);
  }
  for (var i = 0; i < set.dataStore.length; ++i) {
    if (!tempSet.contains(set.dataStore[i])) {
      tempSet.dataStore.push(set.dataStore[i]);
    }
  }
  return tempSet;
}
function size() {
  return this.dataStore.length;
}
function subset(set) {
  if (this.size() > set.size()) {
    return false;
  }
  else {
    for each (var member in this.dataStore) {
      if (!set.contains(member)) {
        return false;
      }
    }
  }
  return true;
}
function difference(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; ++i) {
    if (!set.contains(this.dataStore[i])) {
      tempSet.add(this.dataStore[i]);
    }
  }
  return tempSet;
}

昨日当年