共计 2195 个字符,预计需要花费 6 分钟才能阅读完成。
1. 集合数据结构
集合是一组无序且唯一(不能重复)的项组成的。这个数据结构使用了和有限集合相同的数学概念。
2. 创建集合
function Set() {
// 这里使用对象而不是数组来表示集合
// js 对象中不允许一个键值指向两个不同属性,也保证了集合中的元素都是唯一的
let items = {};
//1. 首先实现 has(value) 方法
this.has = function(value) {
return value in items;
//return items.hasOwnProperty(value);
}
//2. 向集合添加一个项
this.add = function(value) {
if (!this.has(value)) {
items[value] = value;
return true;
} else{
return false;
}
}
//3. 移除某一项和清空集合
this.remove = function(value) {
if (this.has(value)) {
delete items[value];
return true;
} else{
return false;
}
}
this.clear = function() {
items = {};
}
//4. 返回集合长度
this.size = function() {
return Object.keys(items).length;
}
// 兼容性更好
this.sizeLegacy = function() {
let count = 0;
for(let key in items) {
if(items.hasOwnProperty(key))
++count;
}
return count;
}
//5. 返回一个包含集合中所有值的数组
this.values = function() {
let values = [];
for (let i = 0, keys=Object.keys[items]; i < keys.length; i++) {
values.push(items[keys[i]])
};
return values;
}
// 兼容性更好
this.valuesLegacy = function() {
let values = [];
for (let key in items) {
if(items.hasOwnProperty(key)) {
values.push(items[keys)
}
};
return values;
}
}
集合的使用
let set = new Set();
set.add(1);
console.log(set.values()); // [‘1’]
console.log(set.has(1)); // true
console.log(set.size()); // 1
set.add(2);
console.log(set.values()); // [‘1’, ‘2’]
console.log(set.has(2)); // true
console.log(set.size()); // 2
set.remove(1);
console.log(set.values()); // [‘2’]
console.log(set.has(1)); // false
console.log(set.size()); // 1
3. 集合的操作
集合有:并集、交集、差集、子集
// 1. 实现并集
this.union = function(otherSet) {
let unionSet = new Set();
let values = this.values();
for(let i=0; i<values.length; i++){
unionSet.add(values[i])
}
values = otherSet.values();
for(let i=0; i<values.length; i++){
unionSet.add(values[i])
}
return unionSet;
}
// 2. 实现交集
this.intersection = function(otherSet){
let intersectionSet = new Set();
let values = this.values();
for(let i=0; i<values.length; i++){
if(otherSet.has(values[i])) {
intersectionSet.add(values[i])
}
}
return intersectionSet;
}
// 3. 实现差集
this.difference = function(otherSet) {
let differenceSet = new Set();
let values = this.values();
for(let i=0; i<values.length; i++){
if(!otherSet.has(values[i])) {
differenceSet.add(values[i])
}
}
return differenceSet;
}
// 4. 子集
this.subset = function(otherSet) {
if(this.size() > otherSet.size()) {
return false;
} else {
let values = this.values();
for(let i=0; i<values.length; i++){
if(!otherSet.has(values[i])) {
return true
}
}
return true;
}
}
在 es6 中新增了 set 类,我们也可以使用其中自带的方法。