集合类型

基本定义

在计算机科学中，集合是一组可变数量的数据项（也可能是0个）的组合，这些数据项可能共享某些特征，需要以某种操作方式一起进行操作。一般来讲，这些数据项的类型是相同的。几乎所有语言中都有集合的存在，常见的实现方式就是哈希表。目前先用js中的对象实现一下。

集合通常有两个特点，第一个就是无序，第二个就是不允许重复。和ES6提供的Set比较相似。

集合中常见的方法

  1. add：向集合中添加一个元素
  2. remove：从集合从移除一个元素
  3. has：如果集合包含某个元素旧返回true，反之返回false
  4. clear：移除集合中所有的元素
  5. size：返回集合中元素的数量
  6. values：返回集合中所有的元素
  7. 并集操作
  8. 交集操作
  9. 差集操作

在js中实现集合类型

当我们借助于js的对象来实现集合类型的时候就会显的非常简单

前置工作

1
2
3
4
5
class MySet {
  constructor() {
    this.items = {};
  }
}

因为集合就是一个个的对象，我们在类中创建的对象已经能够满足集合的需求，它不像链表一样那么复杂，需要包含指向上一个节点或者是下一个节点的引用

实现add方法

1
2
3
4
5
// add：向集合中添加一个元素
add(data) {
  if (this.has(data)) return false;
  this.items[data] = data;
}

实现remove方法

1
2
3
4
5
6
// remove：从集合从移除一个元素
remove(data) {
  if (!this.has(data)) return false;
  delete this.items[data];
  return true;
}

实现has方法

1
2
3
4
// has：如果集合包含某个元素旧返回true，反之返回false
has(data) {
  return Object.values(this.items).includes(data);
}

实现clear方法

1
2
3
4
// clear：移除集合中所有的元素
clear() {
  this.items = {};
}

实现size方法

1
2
3
4
// size：返回集合中元素的数量
 size() {
   return Object.keys(this.items).length;
 }

实现values方法

1
2
3
4
// values：返回集合中所有的元素
values() {
  return Object.values(this.items);
}

实现并集操作

1
2
3
4
5
6
7
8
9
10
11
12
13
// 并集操作
union(outher) {
  const set = new MySet();
  let value = this.values();
  value.forEach(item => {
    set.add(item);
  });
  value = outher.values();
  value.forEach(item => {
    set.add(item);
  });
  return set;
}

实现交集操作

1
2
3
4
5
6
7
8
9
10
11
12
13
// 交集操作
intersection(other) {
  const set = new MySet();
  const value = this.values();
  const otherValue = other.values();
  const arr = value.filter(item => {
    return otherValue.includes(item);
  });
  arr.forEach(item => {
    set.add(item);
  });
  return set;
}

实现差集操作

1
2
3
4
5
6
7
8
9
10
11
12
13
// 差集操作
difference(other) {
  const set = new MySet();
  const value = this.values();
  const otherValue = other.values();
  const arr = value.filter(item => {
    return !otherValue.includes(item);
  });
  arr.forEach(item => {
    set.add(item);
  });
  return set;
}

实现子集操作

1
2
3
4
5
6
7
8
9
10
// 子集操作
subset(other) {
  const value = this.values();
  const otherValue = other.values();
  const arr = value.filter(item => {
    return otherValue.includes(item);
  });
  if (arr.length !== this.size()) return false;
  return true;
}