野生前端的数据结构基础练习（6）——集合

目录

网上的相关教程非常多，基础知识自行搜索即可。

习题主要选自orelly出版的《数据结构与算法javascript描述》一书。

参考代码可见:https://github.com/dashnowords/blogs/tree/master/structure/set

集合的基本知识

• 定义：

  集合set是一种不包含不同元素的数据结构，主要特性包括无序性和单一性，即集合中的成员是无序的，同时也是不重复的。

基本练习

实现一个自定义的cset类（避免与原生的set类冲突），包含以下方法:

datastore-类属性，用于存储集合中的成员，用数组实现即可。

add(value)- 向集合中加入成员。

remove(value)- 从集合中移除成员。

union(csetinstance) - 求并集

intersect(csetinstance)求交集

difference(csetinstance)求差集

show( )-显示集合成员

课后习题（书中第九节习题）

1.修改set类，使得里面的元素按顺序存储，并写一段代码测试该修改。

2.修改set类，将存储方式从数组替换为链表，并写一段代码测试该修改。

3.为set类增加一个higher(element)方法，该方法返回比传入元素大的元素中最小的一个，并写一段代码来测试该功能。

4.为set类增加一个lower(element)方法，该方法返回比传入元素小的元素中最大的一个，并写一段代码来测试该功能。

习题思路

1.add(value)方法中检测完重复性后，使用插入排序算法和splice(i,0,value)方法将成员直接插入正确位置。

2.将前述章节中实现的list.js类引入，使用一个新的类继承set类并复写其构造函数及相关方法即可。

3.习题1中已经实现了插入排序，higher(element)只需要在set中找到element应该插入的位置，该位置后一个元素即满足查找条件。

4.思路同上，不再赘述。

es6新特性

阮一峰的es6教程：

es6中原生实现了set,map,weakset,weakmap跟集合相关的类型，和数据结构中的集合不完全一致，数据结构中的集合主要是一种数学概念的表现，而es6中的集合拥有一些针对特定问题的开发相关的特性。

1.数组去重

借助集合可以实现js中最简洁的数组去重方式:

//实现了iterable接口的数据结构都可以作为初始化set的参数
cosnt uniquearr = [...new set(arr)];

2.集合遍历

keys(),values(),entries()方法分别返回不同类型的遍历器，可供for...of循环结构消费。

3.数学特性

原生set类并没有定义集合的数学运算操作方法，因为可以很方便的直接实现：

//并集
let union = new set([...a,...b]);
//交集
let intersect = new set([...a].filter(x=>b.has(a)));
//差集
let difference = new set([...a].filter(x=>!b.has(a)));

4.weakset

weakset的成员变量只能是对象，被放入其中的对象都是弱引用，在其他引用都解除后，垃圾回收机制不会考虑weakset对该对象的持有。上面的教程中提到weakmap的主要用途是用于dom节点的存储，防止dom节点移除后造成内存泄漏。基础知识可以参考这篇博文《javascript中4种常见的内存泄漏陷阱》。

5.weakmap

weakmap的设计目的，在于当在某个dom对象上存放一些数据时，会形成对这个对象的引用，影响垃圾回收机制，典型应用场景是在dom元素上添加数据，当dom元素被清除时，对应的weakmap记录也会被自动清除。