Liawn's blog

# 集合

# 集合数据结构

    集合是由一组无序且唯一（即不能重复）的元素组成。元素之间没有任何关系；空集是不包含任何元素的集合。
    可以像数学当中的集合一样，可进行并集、交集、差集等基本运算。

# 集合实现

    其实在 es2015，新增了Set (opens new window)类作为 JavaScript API 的一部分，所以我们可以直接使用它（跟 Array 一样可以不用自己实现，但在这里还是实现一下 Set，开发过程中直接使用 es2015 的 Set），但是这个 Set 缺少并集、交集、差集等基本功能，这个可以去util.ts (opens new window)中找寻 union（并集）、intersection（交集）、difference（差集）、isSubsetOf（子集）等方法实现细节。

    集合实现代码细节：set.ts (opens new window)

    1.声明一个私有变量_items 用于存储集合里的元素，类型选用对象（用属性名保证不重复）。声明一个私有变量_count 用于记录集合大小。

    2.has 方法，判断元素是否在集合中，其实就是判断对象中是否有这个属性。

Object.prototype.hasOwnProperty.call(this._items, element);
1

    如果你使用 this._items.hasOwnProperty(element)，这个可能会有问题。一般对象的 hasOwnProperty 继承自 Object.prototype 的 hasOwnProperty，而这 hasOwnProperty 方法可能会被覆盖，况且并不是所有的对象都继承有 Object.prototype，所以这里直接使用Object.prototype.hasOwnProperty (opens new window)和call (opens new window)更好。

    3.add 方法，向集合添加一个新元素。先用 has 方法判断这个元素是否已经存在于集合中了，不存在再将新元素添加到_item 里，再更新_count。

    4.delete 方法，从集合移除一个元素。先用 has 方法判断这个元素是否已经存在于集合中了，存在再去_item 里使用 delete 运算符删除该元素，再更新_count。

    5.size 方法，返回集合所包含元素的数量。因为我们声明了_count 变量，并且在添加和删除都会更新它，返回它是最方便的。如果我们没有声明_count，我们可以

return Object.keys(this._items).length;
1

如果不想使用Object.keys (opens new window)（es5 可以用于遍历对象而不能遍历数组，es2015 都可遍历），那么你也可以这样

let count = 0;
for (const key in this._items) {
  if (Object.prototype.hasOwnProperty.call(this._items, key)) {
    count++;
  }
}
return count;
1
2
3
4
5
6
7

    6.values 方法，返回一个包含集合中所有值（元素）的数组。我们可以

return Object.values(this._items);
1

如果不想使用 es2017 才支持的Object.values (opens new window)，那么你也可以这样

const values: T[] = [];
for (const key in this._items) {
  if (Object.prototype.hasOwnProperty.call(this._items, key)) {
    values.push(this._items[key]);
  }
}
return values;
1
2
3
4
5
6
7

    7.clear 方法就是置空_items 和置零_count；toString 先掉 values 方法，再遍历调用各自的 toString 然后拼在一起即可。

# 集合的运算

# 并集

定义：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。

    在util.ts (opens new window)中的 union 有实现

    思路：遍历集合 A，将集合 A 的所有元素 add 进新集合；遍历集合 B，将集合 B 的所有元素 add 进新集合。新集合就是 AB 集合的并集，因为 add 时会避免掉重复的元素。

    使用展开运算符... (opens new window)，再配合 Set 的构造函数会更简单

return new Set() < T > [...setA, ...setB];
1

# 交集

定义：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。

    在util.ts (opens new window)中的 intersection 有实现

    思路：遍历集合 A，判断当前元素是否存在于集合 B 中，如果存在就把这个元素放入新集合中，遍历完后集合 A 后，新集合就是 AB 集合的交集。

    使用展开运算符... (opens new window)和 Set 的构造函数再配合filter (opens new window)方法会更简单

let smallerSet: Set<T> = setA; // 我们默认遍历小的
let biggerSet: Set<T> = setB;
if (setA.size > setB.size) {
  // 如果B更小就对调
  smallerSet = setB;
  biggerSet = setA;
}
return new Set() < T > [...smallerSet].filter((x) => biggerSet.has(x));
1
2
3
4
5
6
7
8

# 差集

定义：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。

    在util.ts (opens new window)中的 difference 有实现

    思路：遍历集合 A，判断当前元素是否存在于集合 B 中，如果不存在就把这个元素放入新集合中，遍历完后集合 A 后，新集合就是 AB 集合的差集。

    使用展开运算符... (opens new window)和 Set 的构造函数再配合filter (opens new window)方法会更简单

return new Set() < T > [...setA].filter((x) => !setB.has(x));
1

# 子集

定义：验证一个给定集合是否是另一个集合的子集。

    在util.ts (opens new window)中的 isSubsetOf 有实现

    思路：遍历集合 A，判断当前元素是否存在于集合 B 中，如果每次遍历都存在，那么集合 A 是集合 B 的子集。

    使用展开运算符... (opens new window)，再配合every (opens new window)方法会更简单

return [...setA].every((x) => setB.has(x));
1

← 6.字典和散列表 →