《javascript数据结构和算法》读书笔记（5）：集合
第四讲 集合（items）
集合是一种不允许重复的数据结构（无序且唯一）。
{1,2,3,4}就是一个集合。 {}视为空集。
创建一个集合（基于ES6的Set）
在创建时有一个细节，使用对象（items）而不是数组来创建集合。但使用数组的话意义似乎不大。
元素存在的键值对类似 'value':value
创建一个基于对象的集合，是之拥有以下方法：
- add(value):在集合中添加新项
- remove(value):从集合中移除一个值
- has(value)： 如果值在集合中，返回true，否则为false
- clear():移除所有集合中的项目，返回空集
- size：返回集合包含的元素个数
- values:以数组形式返回集合元素列表
// 集合
class Set{
constructor(){
this.items={};
}
// 是否含有
has(value){
// return value in this.items;
return this.items.hasOwnProperty(value)
}
// 添加
add(value){
if(!this.has(value)){
this.items[value]=value;
}
}
// 删除
remove(value){
if(this.has(value)){
delete this.items[value];
return true
}
}
// 清理
clear(){
this.items={}
}
// 长度
size(){
// ES6中Obeject.key方法以数组形式返回对象的属性列表（IE9+）
return Object.keys(this.items).length;
}
// 以数组形式返回所有值
values(){
let values=[];
let keys=Object.keys(this.items);
for(let i=0;i<keys.length;i++){
values.push(this.items[keys[i]])
}
return values;
}
}来测试一下吧
// 测试用例
let a=new Set();
a.add('dangjingtao');
a.add('djtao')
console.log(a.has('taotao'))
a.add('taotao');
console.log(a.has('taotao'))
console.log(a.values())
a.remove('djtao')
console.log(a.size())集合操作
高一数学补白
集合的数据类型精髓在于运算。在此补白如下
this is 交集
这是并集：
这是差集
并集（union）运算的实现
并集定义如下：
A ∪B={x|x ∈A V x ∈B}
// 并集
union(otheSet){
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;
}测试用例：
let a = new Set();
a.add(1);
a.add(2);
a.add(3);
let b = new Set();
b.add(3);
b.add(4);
b.add(5);
console.log(a.union(b))注意，3只会1一次。
交集（intersection）的实现
A∩B={x|x ∈A ^ x ∈B}
交集的话，最好是去遍历其中一个，拿另一个去判断，就可以了、
// 交集
intersection(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;
}测试用例：
let a = new Set();
a.add(1);
a.add(2);
a.add(3);
let b = new Set();
b.add(3);
b.add(4);
b.add(5);
console.log(a.intersection(b))差集(difference)实现
A-B={x|x ∈A ^ x 不属于B}
思路是遍历A，找出不属于B的
// 差集
difference(otherSet){
let values=this.values();
let set=new Set();
for(let i=0;i<values.length;i++){
if(!otherSet.has(values[i])){
set.add(values[i])
}
}
return set;
}判断是否子集（subSet）
A包含于B
// 是否子集
subSet(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 false;
}
}
}
}ES6中的类
ECMA2015中，新增了Set类。
Set 对象允许你存储任何类型的唯一值，无论是[原始值)或者是对象引用。
语法
new Set([iterable]);参数
- iterable 如果传递一个可迭代对象，它的所有元素将不重复地被添加到新的 Set中。如果不指定此参数或其值为null，则新的 Set为空。
返回的事一个新的 Set对象。
const set = new Set([1, 2, 3, 4, 5]);
console.log(set.size)
//5
console.log(set.has(1));
// true
console.log(set.has(6));
// false
console.log(set.values());
// SetIterator { 1, 2, 3, 4, 5 }values()方法返回的是一个SetIterator 对象。
原生Set支持的方法
-
Set.prototype.add(value)在Set对象尾部添加一个元素。返回该``Set对象。 -
Set.prototype.clear()移除Set对象内的所有元素。 -
Set.prototype.delete(value)移除Set的中与这个值相等的元素，返回Set.prototype.has(value)在这个操作前会返回的值（即如果该元素存在，返回true，否则返回false）。``Set.prototype.has(value)在此后会返回false。 -
Set.prototype.entries()返回一个新的迭代器对象，该对象包含Set对象中的按插入顺序排列的所有元素的值的[value,value]数组。为了使这个方法和Map对象保持相似，每个值的键和值相等。 -
Set.prototype.forEach(callbackFn[,thisArg\])按照插入顺序，为Set对象中的每一个值调用一次callBackFn。如果提供了thisArg参数，回调中的this会是这个参数。 -
Set.prototype.has(value)返回一个布尔值，表示该值在Set中存在与否。 -
Set.prototype.keys()与values()方法相同，返回一个新的迭代器对象，该对象包含Set对象中的按插入顺序排列的所有元素的值。 -
Set.prototype.values()返回一个新的迭代器对象，该对象包含Set对象中的按插入顺序排列的所有元素的值。 -
Set.prototype[@@iterator]()返回一个新的迭代器对象，该对象包含Set对象中的按插入顺序排列的所有元素的值。
我们说的迭代器对象 SetIterator。可以使用iterable内置的forEach方法 ：
let set=new Set([1,2,3,4,5])
set.forEach((element, sameElement, set) => {
console.log(element, sameElement, set)
});
// 1 1 Set { 1, 2, 3, 4, 5 }
// 2 2 Set { 1, 2, 3, 4, 5 }
// 3 3 Set { 1, 2, 3, 4, 5 }
// 4 4 Set { 1, 2, 3, 4, 5 }
// 5 5 Set { 1, 2, 3, 4, 5 }使用举例：数组去重
ES6中 Array新增了一个静态方法 Array.from，可以把类似数组的对象转换为数组，如通过 querySelectAll方法得到 HTML DOMNodeList，以及ES6中新增的 Set和 Map等可遍历对象，
由此可以实现一行代码数组去重：
let array = Array.from(new Set([1, 1, 1, 2, 3, 2, 4]));
console.log(array);对象语法的扩展
对象并没有实现集合运算。现在来扩展一下吧。
并集：
// 并集
Set.prototype.union = function (otherSet) {
let unionSet = new Set();
this.forEach((element, sameElement, set) => {
// console.log(element, sameElement, set)
unionSet.add(element)
});
otherSet.forEach((element, sameElement, set) => {
// console.log(element, sameElement, set)
unionSet.add(element)
});
return unionSet;
}
const set = new Set([1, 2, 3, 4, 5]);
let set2=new Set([1,2,6,7])
console.log(set.union(set2))//Set { 1, 2, 3, 4, 5, 6, 7 }交集
// 并集
Set.prototype.intersection = function (otherSet) {
let unionSet = new Set();
this.forEach((element, sameElement, set) => {
if(otherSet.has(element)){
unionSet.add(element)
}
});
return unionSet;
}
const set = new Set([1, 2, 3, 4, 5]);
let set2=new Set([1,2,6,7])
console.log(set.intersection(set2))//Set { 1, 2 }差集
// 差集
Set.prototype.difference = function (otherSet) {
let unionSet = new Set();
this.forEach((element, sameElement, set) => {
if(!otherSet.has(element)){
unionSet.add(element)
}
});
return unionSet;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录