当前位置 博文首页 > 司夏的博客:JavaScript 数据结构与算法(集合)
集合,这是一种不允许值重复的顺序数据结构,是由一组无序且唯一(即不能重复)的项组成的。该数据结构使用了与有限集合相同的数学概念,但应用在计算机科学的数据结构中。
在数学中,集合是一组不同对象的集。
比如说,一个由大于或等于 0 的整数组成的自然数集合:N = {0, 1, 2, 3, 4, 5, 6, …}。集合中的对象列表用花括号({}
)包围。
还有一个概念叫空集。空集就是不包含任何元素的集合。比如 24 和 29 之间的素数集合,由于 24 和 29 之间没有素数(除了 1 和自身,没有其他正因数的、大于 1 的自然数),这个集合就是空集。空集用{ }
表示。
你也可以把集合想象成一个既没有重复元素,也没有顺序概念的数组。集合有并集、交集、差集等基本运算。
ECMAScript 2015 介绍了 Set 类是 JavaScript API 的一部分,所以将基于 ES2015 的 Set 类来实现自己的 Set 类。也会实现一些原生 ES2015 没有提供的集合运算,例如并集、交集和差集。
用下面的 Set 类以及它的构造函数声明作为开始。
class Set {
constructor() {
this.items = {};
}
}
JavaScript 的对象不允许一个键指向两个不同的属性,也保证了集合里的元素都是唯一的。
has(element)方法
has(element)
:如果元素在集合中,返回 true,否则返回 false。
首先要实现的是 has(element)方法,因为它会被 add、delete 等其他方法调用。
实现一:
has(element){
// 用 JavaScript 的 in 运算符来验证给定元素是否是 items 对象的属性。
return element in items;
};
实现二:
has(element) {
return Object.prototype.hasOwnProperty.call(this.items, element);
}
Object
原型有 hasOwnProperty
方法。该方法返回一个表明对象是否具有特定属性的布尔 值。in
运算符则返回表示对象在原型链上是否有特定属性的布尔值。
add 方法
add(element)
:向集合添加一个新元素。
add(element) {
if (!this.has(element)) { // 是否存在于集合中。
this.items[element] = element; // 如果不存在,就把 element 添加到集合中
return true;
}
return false;
}
测试 add 方法
const set = new Set();
set.add(1);
set.add(2);
console.log(set.items); // {1: 1, 2: 2}
delete 和 clear 方法
delete (element)
:从集合移除一个元素。
delete (element) {
if (this.has(element)) {
delete this.items[element]; // 存在 element ,就从集合中移除 element
return true;
}
return false;
}
clear()
:移除集合中的所有元素。
clear() {
this.items = {}; // 把一个空对象重新赋值给它
}
size 方法
size()
:返回集合所包含元素的数量。它与数组的 length 属性类似。
该方法有三种实现方式
第一种方式是使用一个length
变量,每当使用 add 或 delete 方法时就控制它.
第二种方式是使用 JavaScript 中 Object
类的一个内置方法keys
(ECMAScript 2015 以上版本)。
size() {
return Object.keys(this.items).length;
};
JavaScript 的 Object
类有一个keys
方法,它返回一个包含给定对象所有属性的数组。在这
种情况下,可以使用这个数组的length
属性来返回items
对象的属性个数。以上代码只能在现代浏览器(比如 IE9 以上版本、Firefox 4 以上版本、Chrome 5 以上版本、Opera 12 以上版本、Safari 5 以上版本等)中运行。
第三种方式是手动提取 items 对象的每一个属性,记录属性的个数并返回这个数。
sizeLegacy() {
let count = 0;
for (let key in this.items) { // 迭代 items 对象的所有属性
if (this.items.hasOwnProperty(key)) { // 检查它们是否是对象自身的属性(避免重复计数)
count++; // 如果是,就递增 count 变量的值
}
return count;
};
}
values 方法
values()
:返回一个包含集合中所有值(元素)的数组。
要实现 values 方法,同样可以使用 Object 类内置的 values 方法。
values() {
return Object.values(this.items);
}
Object.values()
方法返回了一个包含给定对象所有属性值的数组。它是在ECMAScript 2017 中被添加进来的,目前只在现代浏览器中可用。
如果想让代码在任何浏览器中都能执行,可以用与之前代码等价的下面这段代码。
valuesLegacy() {
let values = [];
for (let key in this.items) { // 迭代 items 对象的所有属性
if (this.items.hasOwnProperty(key)) {
values.push(key); // 把它们添加到一个数组中
}
}
return values;
};
自定义 Set 类
class Set {
constructor() {
this.items = {};
};
has(element) {
return Object.prototype.hasOwnProperty.call(this.items, element);
};
add(element) {
if (!this.has(element)) { // 是否存在于集合中。
this.items[element] = element; // 如果不存在,就把 element 添加到集合中
return true;
}
return false;
};
delete(element) {
if (this.has(element)) {
delete this.items[element]; // 存在 element ,就从集合中移除 element
return true;
}
return false;
};
clear() {
this.items = {}; // 把一个空对象重新赋值给它
};
size() {
return Object.keys(this.items).length; // {1}
};
values() {
return Object.values(this.items);
}
}
使用 Set 类
const set = new Set();
set.add(1);
set.add(2);
console.log(set.values()); // 输出[1, 2]
console.log(set.has(2)); // 输出 true
console.log(set.size()); // 输出 2
set.delete(1);
console.log(set.values()); // 输出[2]
set.delete(2);
console.log(set.values()); // 输出[]
并集:对于给定的两个集合,返回一个包含两个集合中所有元素的新集合。
union(otherSet) {
// unionSet 代表两个集合的并集
const unionSet = new Set();
// 获取第一个集合(当前的 Set 类实例)所有的值(values),迭代并全部添加到代表并集的集合中
this.values().forEach(value => unionSet.add(value));
// 对第二个集合做同样的事
otherSet.values().forEach(value => unionSet.add(value));
// 返回结果
return unionSet;
}
使用 ES2015 以上版本的功能。使用 forEach 方法和箭头函数,只要可以,就应该试着使用
测试
const setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);
const unionAB = setA.union(setB);
console.log(unionAB.values()); // [1, 2, 3, 4, 5, 6]
交集:对于给定的两个集合,返回一个包含两个集合中共有元素的新集合。
intersection(otherSet) {
const intersectionSet = new Set