集合

本文共--字 阅读约--分钟 | 浏览: -- Last Updated: 2021-05-10

集合(Set)是一种包含不同元素的数据结构。集合中的元素称为成员，集合有两个最重要的特性：首先，集合中的成员是无序的；其次，集合中不允许相同成员存在，当你想要创建一个数据结构，用来保存一些独一无二的元素时，集合就变得非常有用。

集合的定义

下面列举了一些使用集合时必须了解的定义：

  • 不包含任何成员的集合称为空集，全集则是包含一切可能的成员的集合。
  • 如果两个集合的成员完全相同，则称两个集合相等。
  • 如果一个集合中所有的成员都属于另一个集合，则前一集合称为后一集合的子类。

对集合的基本操作有下面几种：并集，将两个集合的成员进行合并，得到一个新集合；交集，两个集合中共同存在的成员组成一个新的集合；补集，属于一个集合而不属于另一个集合的成员组成的集合。

Set类的实现

Set 类的实现基于数组。

function MySet() {
  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;
}

function add(data) {
  if (this.dataStore.indexOf(data) < 0) { // 不存在
    this.dataStore.push(data)
    return true;
  }
  return false;
}

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

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

function show() {
  console.log(this.dataStore);
  return this.dataStore;
}

function contains(data) {
  return this.dataStore.indexOf(data) > -1
}

// 并集操作
function union(set) {
  var tmpSet = new MySet();
  for (var i = 0; i < this.dataStore.length; i++) {
    tmpSet.add(this.dataStore[i]);
  }

  for (var j = 0; j < set.dataStore.length; j++) {
    if (!tmpSet.contains(set.dataStore[j])) { // 原集合没有
      tmpSet.add(set.dataStore[j])
    }
  }
  return tmpSet;
}

// 交集操作
function intersect(set) {
  var tmpSet = new MySet();
  for (var i = 0; i < this.dataStore.length; i++) {
    if (set.contains(this.dataStore[i])) { // 两者都有
      tmpSet.add(this.dataStore[i])
    }
  }
  return tmpSet;
}

// 判断当前集合是不是待比较集合的子集
function subset(set) {
  if (this.size() > set.size()) { // 当前集合比待比较集合还有大，则一定不是待比较集合的子集
    return false
  }

  for (var i = 0; i < this.dataStore.length; i++) {
    if (!set.contains(this.dataStore[i])) { // 待比较集合应该包含当前集合的所有成员，当前集合才可能是待比较集合的子集
      return false
    }
  }
  return true;
}

// 补集操作，返回一个新集合，该集合包含的是那些属于当前集合但不属于传入集合的成员
// a.difference(b) 返回的集合包含 => a有而b没有的
function difference(set) {
  var tmpSet = new MySet();
  for (var i = 0; i < this.dataStore.length; i++) {
    if (!set.contains(this.dataStore[i])) {
      tmpSet.add(this.dataStore[i])
    }
  }
  return tmpSet;
}

测试代码：

var s = new MySet();
s.add('Mike')
s.add('Clayton')
s.add('Jennifer')
s.add('Raymond')

var ss = new MySet();
ss.add('Raymond')
ss.add('Cynthia')
ss.add('Jonathan')

var result = s.union(ss)
result.show() // [ 'Mike', 'Clayton', 'Jennifer', 'Raymond', 'Cynthia', 'Jonathan' ]

var result2 = s.intersect(ss);
result2.show() // [ 'Raymond' ]

var c = new MySet()
c.add('Mike')
c.add('Clayton')
console.log(c.subset(s)); // true
console.log(c.subset(ss)); // false

var d = new MySet();
d.add('Raymond')
d.add('Cynthia')
d.add('David')

var d1 = d.difference(ss)
d1.show() // [ 'David' ]

var d2 = ss.difference(d)
d2.show() // [ 'Jonathan' ]