js实现数据结构及算法之集合(Set)

160 阅读2分钟

集合(Set)

集合是一种包含不同元素的数据结构

很多编程语言中,集合并不是一种数据类型,但是如果你需要创建一个数据结构用来保存一些独一无二的元素时,集合就变得很有用

集合的成员是无序的

集合中不允许相同成员存在

集合(Set)是由一组无序但彼此之间又有一定关系性的成员构成,集合中的元素称为成员

不包含任何成员的集合称为空集,包含一切可能成员的集合称为全集

如果两个集合里的成员都完全相同,则称两个集合相等

如果一个集合所有成员都包含于另一个集合,则前一集合称为后一集合的一个子集

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

js实现

/**
   * 一个简单的集合
   * @constructor
   */
  function Set() {
    this.dataStore = [];            // 数据存储
    this.add = add;                 // 添加成员
    this.remove = remove;           // 删除成员
    this.show = show;               // 显示当前集合
    this.size = size;               // 集合元素个数
    this.union = union;             // 集合求并集
    this.intersect = intersect;     // 集合求交集
    this.subset = subset;           // 判断一个集合是否是另一集合的子集
    this.difference = difference;   // 集合求补集
    this.contains = contains;       // 判断某成员是否属于该集合
  }

  //添加成员
  function add(data) {
    if (this.dataStore.indexOf(data) < 0) {
      this.dataStore.push(data)
    } else {
      return false
    }
  }

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

  // 显示当前集合
  function show() {
    return this.dataStore
  }
  // 显示集合个数
  function size() {
    return this.dataStore.length
  }

  // 集合求并集
  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.add(set.dataStore[i])
      }
    }
    return tempSet
  }

  // 集合求交集
  function intersect(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 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 subset(set) {
    if(set.size() > this.size())  return false
  for(var i = 0; i < set.dataStore.length; i++) {
      if(!this.contains(set.dataStore[i])) {
        return false
      }
  }
  return true
}

// 判断某成员是否属于该集合
function contains(data) {
  return this.dataStore.indexOf(data) > -1 ? true : false
}

var set = new Set()
set.add('1')
set.add('1')
set.add('13')
set.add('14')
set.add('15')
set.remove('15')
console.log(set.show())
var set2 = new Set()
set2.add('1')
set2.add('21')
set2.add('213')
set2.add('14')
  console.log(set2.show())
console.log('=====并集====')
console.log(set.union(set2).show())
console.log('=====交集====')
console.log(set.intersect(set2).show())
console.log('=====补集====')
console.log(set.difference(set2).show())
  var set3 = new Set()
  set3.add('1')
  set3.add('13')
  set3.add('14')
  console.log('=====set3是set子集====')
 console.log(set.subset(set3))
  console.log('=====set2是set子集====')
  console.log(set.subset(set2))