8.JavaScript 数据结构与算法（八）集合

[webVueBlog]

集合特点

• 集合通常是由一组无序的、不能重复的元素构成。

• 数学中常指的集合中的元素是可以重复的，但是计算机中集合的元素不能重复。

• 集合是特殊的数组。

  • 特殊之处在于里面的元素没有顺序，也不能重复。
  • 没有顺序意味着不能通过下标值进行访问，不能重复意味着相同的对象在集合中只会存在一份。

封装集合

ES6 中的 Set 就是一个集合类，这里我们重新封装一个 Set 类，了解集合的底层实现。

集合常见的操作

• add(value) 向集合添加一个新的项。
• remove(value) 从集合移除一个值。
• has(value) 如果值在集合中，返回 true，否则返回 false。
• clear() 移除集合中的所有项。
• size() 返回集合所包含元素的数量。与数组的 length 属性类似。
• values() 返回一个包含集合中所有值的数组。

代码实现

// 集合结构的封装
class Set {
 constructor() {
  this.items = {};
 }
 // has(value) 判断集合中是否存在value值，存在返回true，否则返回false
 has(value) {
  return this.items.hasOwnProperty(value);
 }
 // add(value) 往集合中添加value
 add(value) {
  if (this.has(value)) return false;
  this.items[value] = value;
  return true;
 }
 // remove(value) 删除集合中指定的value
 remove(value) {
  if (!this.has(value)) return false;
  delete this.items[value];
 }
 // clear() 清空集合中所有 value
 clear() {
   this.items = {};
 }
 // size() 获取集合中的value个数
 size() {
  return Object.keys(this.items).length;
 }
 // values() 获取集合中所有的value
 values() {
  return Object.values(this.items);
 }
}

集合间的操作

• 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
• 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
• 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。
• 子集：验证一个给定集合是否是另一个集合的子集。

并集的实现

// union() 求两个集合的并集
union(otherSet) {
  // 1. 创建一个新集合
  let unionSet = new Set();
  // 2. 将当前集合(this)的所有value，添加到新集合 unionSet 中
  if (let value of this.values()) {
    unionSet.add(value)
  }
  // 3. 将 otherSet 集合的所有value，添加到新集合 unionSet 中
  for (let value of otherSet.values()) {
    unionSet.add(value)
  }
  return unionSet;
}

交集的实现

// intersection() 求两个集合的交集
intersection(otherSet) {
 // 创建一个新集合
 let intersectionSet = new Set();
 // 从当前集合中取出每一个value，判断是否在otherSet集合中
 for (let value of this.values()) {
   if (otherSet.has(value)) {
    intersectionSet.add(value);
   }
 }
 return intersectionSet;
}

差集的实现

difference(otherSet) {
 // 1. 创建一个新集合
 let differenceSet = new Set();
 // 2. 从当前集合中取出每一个value，判断是否在 otherSet 集合中存在，不存在的即为差集
 for (let value of this.values()) {
  if (!otherSet.has(value)) {
   differenceSet.add(value);
  }
 }
 return differenceSet;
}

子集的实现

// subset() 子集
subset(otherSet) {
 // 从当前集合中取出每一个value，判断是否在 otherSet 集合中存在，有不存在的返回 false
 // 遍历完所有的, 返回 true
 for (let value of this.values()) {
  if (!otherSet.has(value)) {
   return false;
  }
 }
 return true;
}

集合的完整实现

// 集合结构的封装
export default class Set {
 constructor() {
  this.items = {};
 }
 // has(value) 判断集合中是否存在 value 值，存在返回 true，否则返回 false
 has(value) {
  return this.items.hasOwnProperty(value);
 }
 // add(value) 往集合中添加value
 add(value) {
  if (this.has(value)) return false;
  this.items[value] = value;
  return true;
 }
 // remove(value) 删除集合中指定的value
 remove(value) {
  // 如果集合不存在该 value，返回false
  if (!this.has(value)) return false
  delete this.items[value];
 }
 // clear() 清空集合中所有 value
 clear() {
  this.items = {};
 }
 // size() 获取集合中的value个数
 size() {
  return Object.keys(this.items).length;
 }
 // values() 获取集合中所有的value
 values() {
  return Object.values(this.items);
 }
 // 集合间的操作
 // union() 求两个集合的并集
 union(otherSet) {
  // 1. 创建一个新集合
  let unionSet = new Set();
  // 2. 将当前集合 (this) 的所有value，添加到新集合 (unionSet) 中
  for (let value of this.values()) {
   unionSet.add(value);
  }
  // 3. 将 otherSet 集合的所有 value，添加到新集合 (unionSet) 中
  for (let value of otherSet.values()) {
   unionSet.add(value);  // add() 已经有重复判断
  }
  return unionSet;
 }
 // intersection() 求两个集合的交集
 intersection(otherSet) {
  // 创建一个新集合
  let intersectionSet = new Set();
  // 从当前集合中取出每一个 value，判断是否在 otherSet 集合中存在
  for (let value of this.values()) {
    if (otherSet.has(value)) {
      intersectionSet.add(value);
    }
  } 
  return intersectionSet;
 }
 // difference() 差集
 difference(otherSet) {
  // 1. 创建一个新集合
  let differenceSet = new Set();
  // 2.从当前集合中取出每一个value，判断是否在 otherSet 集合中存在，不存在的即为差集
  for (let value of this.values()) {
   if (!otherSet.has(value)) {
    differenceSet.add(value);
   }
  }
  return differenceSet;
 }
 
 // subset() 子集
  subset(otherSet) {
   // 从当前集合中取出每一个 value，判断是否在 otherSet 集合中存在，有不存在的返回false
   // 遍历完所有的，返回 true
   for (let value of this.values()) {
    if (!otherSet.has(value)) {
     return false;
    }
   }
   return true;
  }
}