野生前端的数据结构基础练习(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教程:http://es6.ruanyifeng.com/#docs/set-map

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记录也会被自动清除。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

Java 程序员必须掌握的 5 个注解!

* 来源:www.codeceo.com/5-annotations-every-java-developer-should-know.html

892
来自专栏对角另一面

lodash源码分析之compact中的遍历

本文为读 lodash 源码的第三篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

2166
来自专栏Java Web

《编写高质量代码》学习笔记(2)

写着写着发现简书提醒我文章接近字数极限,建议我换一篇写了。 ---- 建议52:推荐使用String直接量赋值 一般对象都是通过new关键字生成的,但是Str...

3664
来自专栏纯洁的微笑

Java 8的新特性—终极版

1. 简介 毫无疑问,Java 8是Java自Java 5(发布于2004年)之后的最重要的版本。这个版本包含语言、编译器、库、工具和JVM等方面的十多个新特...

4156
来自专栏风口上的猪的文章

.NET面试题系列[10] - IEnumerable的派生类

IEnumerable分为两个版本:泛型的和非泛型的。IEnumerable只有一个方法GetEnumerator。如果你只需要数据而不打算修改它,不打算为集合...

1102
来自专栏项勇

笔记72 | 将姓放在名的后面,排序按姓氏首字母排列的修改笔记

1825
来自专栏hbbliyong

一个小程序引发的思考

   既然是一个小程序引发的思考,那么我们就先看看这个小程序,看看他有何神奇之处: namespace ConsoleApplication1 { cl...

2424
来自专栏好好学java的技术栈

一文看透java8新特性

毫无疑问,Java 8发行版是自Java 5(发行于2004,已经过了相当一段时间了)以来最具革命性的版本。Java 8 为Java语言、编译器、类库、开发工具...

1202
来自专栏ACM算法日常

Bessie的好牌(队列)- POJ 3629

Bessie is playing a card game with her N-1 (2 ≤ N ≤ 100) cow friends using a dec...

1163
来自专栏大数据架构

Java进阶(六)从ConcurrentHashMap的演进看Java多线程核心技术

2275

扫码关注云+社区

领取腾讯云代金券