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;
}