数据结构之集合
2022-06-30 本文已影响0人
YM雨蒙
构建数据集合
集合是由一组无序且唯一（即不能重复）的项组成的。该数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中
可以把集合想象成一个既没有重复元素，也没有顺序概念的数组
创建集合类
将基于 ES6 的 Set 类来实现我们自己的 Set 类。我们也会实现一些原生 ES6 没有提供的集合运算，例如并集、交集和差集。
- 要声明一些集合可用的方法, 模拟与 ECMAScript 2015 实现相同的
Set类-
add(element):向集合添加一个新元素 -
delete(element):从集合移除一个元素 -
has(element):如果元素在集合中, 返回 true, 否则返回 false -
clear():移除集合中的所有元素 -
size():返回集合所包含元素的数量. -
values():返回一个包含集合中所有值的数组
-
class Set {
constructor() {
this.items = {};
}
add(element) {
if (!this.has(element)) {
// 添加一个 element 的时候，把它同时作为键和值保存
this.items[element] = element;
return true;
}
return false;
}
has(element) {
// 该方法返回一个表明对象是否具有特定属性的布尔值
return Object.prototype.hasOwnProperty.call(this.items, element);
}
delete(element) {
if (this.has(element)) {
delete this.items[element];
return true;
}
return false;
}
clear() {
this.items = {};
}
size() {
return Object.keys(this.items).length;
}
sizeLegacy() {
let count = 0;
for (let key in this.items) {
if (this.items.hasOwnProperty(key)) {
count++;
}
return count;
}
}
values() {
return Object.values(this.items);
}
valuesLegacy() {
let values = [];
for (let key in this.items) {
if (this.items.hasOwnProperty(key)) {
values.push(key);
}
}
return values;
}
}
-
集合运算
集合是数学中基础的概念，在计算机领域也非常重要
- 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
- 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
- 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集
合的元素的新集合。 - 子集：验证一个给定集合是否是另一集合的子集。
class Set {
constructor() {
this.items = {};
}
add(element) {
if (!this.has(element)) {
// 添加一个 element 的时候，把它同时作为键和值保存
this.items[element] = element;
return true;
}
return false;
}
has(element) {
// 该方法返回一个表明对象是否具有特定属性的布尔值
return Object.prototype.hasOwnProperty.call(this.items, element);
}
delete(element) {
if (this.has(element)) {
delete this.items[element];
return true;
}
return false;
}
clear() {
this.items = {};
}
size() {
return Object.keys(this.items).length;
}
sizeLegacy() {
let count = 0;
for (let key in this.items) {
if (this.items.hasOwnProperty(key)) {
count++;
}
return count;
}
}
values() {
return Object.values(this.items);
}
valuesLegacy() {
let values = [];
for (let key in this.items) {
if (this.items.hasOwnProperty(key)) {
values.push(key);
}
}
return values;
}
// 并集
// 没有副作用的方法和函数被称为纯函数
union(otherSet) {
const unionSet = new Set();
this.values().forEach((value) => unionSet.add(value));
otherSet.values().forEach((value) => unionSet.add(value));
return unionSet;
}
// 交集: 是 x（元素）存在于 A 中，且 x 存在于 B 中
intersection(otherSet) {
// 创建一个新的 Set 实例
const intersectionSet = new Set();
const values = this.values();
const otherValues = otherSet.values();
let biggerSet = values;
let smallerSet = otherValues;
// 比较两个集合的元素个数，如果另一个集合元素个数多于当前集合的话，我们就交换 biggerSet 和 smallerSet 的值
if (otherValues.length - values.length > 0) {
biggerSet = otherValues;
smallerSet = values;
}
// 迭代较小集合
smallerSet.forEach((value) => {
if (biggerSet.includes(value)) {
intersectionSet.add(value);
}
});
return intersectionSet;
}
// 差集: 是 x（元素）存在于 A 中，且 x 不存在于 B 中
difference(otherSet) {
const differenceSet = new Set();
this.values().forEach((value) => {
// 得到所有存在于集合 A 但不存在于集合 B 的元素
if (!otherSet.has(value)) {
differenceSet.add(value);
}
});
return differenceSet;
}
// 子集: 集合 A 中的每一个 x（元素），也需要存在于集合 B 中
isSubsetOf(otherSet) {
if (this.size() > otherSet.size()) return false;
let isSubset = true;
this.values().every((value) => {
if (!otherSet.has(value)) {
isSubset = false;
return false;
}
return true;
});
return isSubset;
}
}
ES6 的 Set 类 与我们写的 Set 类的区别
- ES6 的 Set 的 values 方法返回 Iterator, 而不是值构成的数组
- 我们实现的 size 方法返回 set 中存储的值的个数，而 ES6 的 Set 则有一个 size 属性
ES6 的 Set 没有实现交集, 差集, 并集, 自己等数学运算, 我们来模拟一下
// 并集
new Set([...setA, ...setB]);
// 交集
new Set([...setA].filter((x) => setB.has(x)));
// 差集
new Set([...setA].filter((x) => !setB.has(x)));
