【数据结构与算法】详解什么是集合，并用代码手动实现一个集合结构
本系列文章【数据结构与算法】所有完整代码已上传 github，想要完整代码的小伙伴可以直接去那获取，可以的话欢迎点个Star哦~下面放上跳转链接
- https://github.com/Lpyexplore/structureAndAlgorithm-JS
集合这个概念应该大家在学习数学的时候都听过并且有学习过，它也是一种数据结构，我们还是需要用代码来实现集合的很多方法。
学习过ES6语法的小伙伴应该知道，ES6新增了一种 Set 数据结构，这就是集合，尽管官方已经向我们提供了这种数据结构，但是为了学习它的思想和实现过程，我们还是来亲自学习实现一下吧，顺便学习一下ES6中 Set 数据结构是如何实现的
- 公众号：前端印象
- 不定时有送书活动，记得关注~
- 关注后回复对应文字领取：【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】
数据结构——集合
- 一、什么是集合
- 二、集合分类
- （1）交集
- （2）并集
- （3）差集
- （4）子集
- 三、集合的方法
- 四、用代码实现集合
- （1）创建一个构造函数
- （2）实现has()方法
- （3）实现add()方法
- （4）实现delete()方法
- （5）实现clear()方法
- （6）实现size()方法
- （7）实现values()方法
- （8）实现union()方法
- （9）实现intersect()方法
- （10）实现difference()方法
- （11）实现subset()方法
- 五、结束语
一、什么是集合
集合就是一种包含着不同元素的数据结构，即在集合结构里，每一个元素都是独一无二的，互不相同，同时所有数据都是无序的。
如图中的每个圆圈就代表一个集合，集合中存储着相应的数据
其中，集合1 和 集合2 中同样是存储着数据 1 2 3 4，但分布情况却不同，这说明集合的无序性，而且 集合1 与 集合2并不相等
二、集合分类
集合也有几种特殊的分类，即 并集 、交集 、差集 、子集。其展示的是两个集合之间的关系
（1）交集
交集就是由既属于 集合1 又属于 集合2 的元素组成的集合。
如图
集合1中有数据 1 2 3 4
集合2中有数据 1 2 4 5 8
那么既属于 集合1 又属于 集合2 的元素就是 1 2 4，因此这几个元素就组合成了新的集合 集合3，也称为 集合1 与 集合2 的交集
（2）并集
并集： 由所有属于 集合1 和 集合2 的元素组成的集合
如图
集合1中有数据 1 4
集合2中有数据 2 3 5 8
那么 集合1 与 集合2 所有元素组合起来就是 1 2 3 4 5 8·，这些元素组合起来就组成了新集合 集合3，也称 集合3 为 集合1 与 集合2 的并集
（3）差集
差集： 就是属于 集合1 但不属于 集合2 的所有元素组成的集合
如图
集合1中有数据 1 2 4
集合2中有数据 1 3 5 8
那么属于 集合1 但不属于 集合2 的元素就是 2 4，这两个元素组成了新的集合 集合3，也称 集合3 为 集合1 与 集合2 的差集
（4）子集
子集： 是判断属于 集合1 的元素是否也都属于 集合2
如图
集合1中有数据 1 2 4
集合2中有数据 1 2 3 4 5 8
此时因为 集合1 中的所有元素同时也属于 集合2，所以说 集合1 是 集合2 的子集，也可以说是 集合1 属于 集合2
三、集合的方法
了解了以上这些集合的概念，接下来我们来看一下封装一个集合，都有哪些方法。
首先一个数据结构，必备的增删改查方法是肯定需要的，其次我们尽可能地与ES6的 Set 数据结构中的方法一致，这样方便大家之后学习
方法 | 作用 |
|---|---|
add() | 将一个数据添加到集合中 |
has() | 判断一个元素是否存在于集合中 |
delete() | 删除集合中的某个元素 |
clear() | 清空集合内的所有元素 |
size() | 返回集合内的元素个数 |
values() | 返回集合内的所有元素，保存在数组中 |
union() | 获取与另一个集合的并集 |
intersect() | 获取与另一个集合的交集 |
difference() | 获取与另一个集合的差集 |
subset() | 判断是否为另一个集合的子集 |
四、用代码实现集合
（1）创建一个构造函数
首先创建一个大的构造函数，用于存放集合的一些属性和方法。
function Set() {
// 属性
this.items = {}
}属性 items 用于存放集合中的元素，这里之所以使用对象来存储而不是数组，是因为数组若实现无重复数据很麻烦，需要遍历全部元素，而对象就很方便，直接通过 key 就能获取到集合中是否已存在该数据
（2）实现has()方法
has() 方法是用于判断集合中是否存在某数据。该方法接收一个参数 value 用于查找数据
这里先介绍一个JS中对象的内置方法：
hasOwnProperty() 方法可以判断某属性是否为对象的自有属性，若是，则返回 true ；否则返回 false
所以实现思路就很简单了，直接将参数 value 传给 hasOwnProperty() 方法，并将其返回结果作为 has() 方法的返回结果即可
我们来看一下代码吧
function Set() {
// 属性
this.items = {}
// 方法
// 判断是否存在元素
Set.prototype.has = function(value) {
return this.items.hasOwnProperty(value)
}
}因为这里我们还没有介绍到 add() 方法，因此还没法验证该方法是否可行，而且之后我们会在别的方法中频繁用到 has() 方法用于验证集合中元素是否重复，这里就不做过多的验证了
（3）实现add()方法
add() 方法是用于向集合中添加数据，并返回当前集合。该方法接收一个参数 value 用于存储
实现思路很简单，先通过我们封装的 has()方法 判断集合中是否存在该元素，若存在，则直接返回 false ；否则直接通过 obj[key] = value 的方式存储即可。这里我们是将参数 value 既作为 key 又作为 value
来看一下代码
function Set() {
// 属性
this.items = {}
// 方法
// 添加元素
Set.prototype.add = function(value) {
// 判断是否存在重复元素
if(this.has(value)) return false;
// 存储元素
this.items[value] = value
// 返回当前集合内容
return this.items
}
}我们来使用一下该方法
let set = new Set()
set.add(3)
set.add(1)
set.add(6)
console.log(set.items)
/* 打印结果：
{
'1': 1,
'3': 3,
'6': 6
}
*/可以看到，我们三个添加数据的操作都成功了
（4）实现delete()方法
delete() 方法就是用于删除集合中指定的元素。该方法接收一个参数 value 用于查找到对应的元素并删除
实现思路很简单，先通过 has() 方法判断集合中是否存在该元素，若不存在，则直接返回 false ，表示删除失败 ；否则，直接用关键字 delete 删除集合中对应的元素，并返回 true 表示删除成功
我们来看一下代码
function Set() {
// 属性
this.items = {}
// 方法
// 删除元素
Set.prototype.delete = function(value) {
// 判断集合中是否存在该元素
if(!this.has(value)) return false;
// 删除指定元素
delete this.items[value]
// 返回 true，表示删除成功
return true
}
}我们来使用一下该方法
let set = new Set()
// 添加三个元素，分别为 3 1 6
set.add(3)
set.add(1)
set.add(6)
// 删除元素 6
set.delete(6)
console.log(set.items)
/* 打印结果：
{
'1': 1,
'3': 3
}
*/我们可以看到，6 成功被删除了
（5）实现clear()方法
clear() 方法时用于清空集合中的所有元素的。该方法无需传入参数
实现思路： 直接将 this.items 指向一个空的对象即可
我们看一下代码
function Set() {
// 属性
this.items = {}
// 方法
// 清空集合
Set.prototype.clear = function() {
this.items = {}
}
}来使用一下该方法
let set = new Set()
// 添加三个元素，分别为 3 1 6
set.add(3)
set.add(1)
set.add(6)
// 清空集合
set.clear()
console.log(set.items)
/* 打印结果：
{}
*/我们可以看到，集合中的所有元素已经被清空了
（6）实现size()方法
size() 方法就是返回集合中的元素个数。该方法无需传入参数
这里先介绍一个JS中对象的内置方法：
keys()方法可以接收一个对象参数，并返回该对象所有的键，存放在一个数组中并返回
实现思路： 通过 keys() 获取包含集合所有键的数组，并返回该数组的 length 即可
我们来看一下代码吧
function Set() {
// 属性
this.items = {}
// 方法
// 判断集合内元素个数
Set.prototype.size = function() {
return Object.keys(this.items).length
}
}来使用一下该方法
let set = new Set()
console.log(set.size()) // 0，此时集合为空
// 添加三个元素，分别为 3 1 6
set.add(3)
set.add(1)
set.add(6)
console.log(set.size()) // 3，此时集合内有三个元素（7）实现values()方法
values() 方法是用于返回集合中的所有元素。该方法无需传入任何参数
实现思路： 直接将通过方法 keys() 获取到的数组返回即可
我们来看一下代码
function Set() {
// 属性
this.items = {}
// 方法
// 返回集合内所有元素
Set.prototype.values = function() {
return Object.keys(this.items)
}
}我们来使用一下该方法
let set = new Set()
console.log(set.values()) // []，此时集合为空
// 添加三个元素，分别为 3 1 6
set.add(3)
set.add(1)
set.add(6)
console.log(set.values()) // ['1', '3', '6']，此时集合内有三个元素，分别为 1 、3 、6（8）实现union()方法
union() 方法用于获取当前集合与另一个集合的并集。该方法需要传入一个集合 otherSet 作为参数
实现思路：
- 先创建一个空的新集合
newSet - 通过
values()方法获取到包含当前集合的所有元素的数组oldSetValue，并对其进行遍历，将遍历到每一个元素都添加到newSet()中去 - 再通过
values()方法获取到包含otherSet的所有元素的数组otherSetValue，并对其进行遍历，将遍历到每一个元素都添加到newSet()中去 - 返回
newSet
在该实现过程中，我们是通过 add() 方法将两个集合中的所有元素添加到新的集合中的，因为 add() 方法中已经包含了检验元素的重复性部分，所以我们无需担心两个集合的元素是否会重复
我们来看一下代码
function Set() {
// 属性
this.items = {}
// 方法
// 获取交集
Set.prototype.union = function(otherSet) {
// 1. 创建新的空集合
let newSet = new Set()
// 2. 获取当前集合的所有元素
let oldSetValue = this.values()
// 2.1 遍历当前集合的元素，并添加到 newSet中
for(let i = 0; i < oldSetValue.length; i++) {
newSet.add(oldSetValue[i])
}
// 3. 获取 otherSet集合的所有元素
let otherSetValue = otherSet.values()
// 3.1 遍历 otherSet集合的元素，并添加到 newSet中
for(let j = 0; j < otherSetValue.length; j++) {
newSet.add(otherSetValue[j])
}
// 4. 返回获取到的交集
return newSet
}
}我们来使用一下该方法
// 创建集合1
let set1 = new Set()
// 向集合1中添加元素 3 1 6
set1.add(3)
set1.add(1)
set1.add(6)
// 创建集合2
let set2 = new Set()
// 向集合2中添加元素 3 2 8
set2.add(3)
set2.add(2)
set2.add(8)
// 获取集合1和集合2的并集，即集合3
let set3 = set1.union(set2)
// 查看集合3内的所有元素
console.log(set3.values())
/* 打印结果：
[ '1', '2', '3', '6', '8' ]
*/（9）实现intersect()方法
intersect() 方法是用于获取当前集合与另一个集合的交集。该放需要传入一个集合 otherSet 作为参数
实现思路：
- 先创建一个空的新集合
newSet - 通过
values()方法获取到包含当前集合的所有元素的数组oldSetValue，并对其进行遍历，判断每一个元素是否也存在于otherSet中，若不存在，则不做任何处理 - 若存在，则将该元素添加到
newSet中去 - 返回
newSet
我们来看一下代码
function Set() {
// 属性
this.items = {}
// 方法
// 获取并集
Set.prototype.intersect = function(otherSet) {
// 1. 创建空的新集合
let newSet = new Set()
// 2. 获取当前集合的所有元素
let oldSetValue = this.values()
// 3. 遍历当前集合的所有元素
for(let i = 0; i < oldSetValue.length; i++) {
let item = oldSetValue[i]
// 3.1 元素同时存在于 otherSet中
if(otherSet.has(item)) {
newSet.add(item)
}
}
// 4. 返回获取到的交集
return newSet
}
}我们来使用一下该方法
// 创建集合1
let set1 = new Set()
// 向集合1中添加元素 3 1 6
set1.add(3)
set1.add(1)
set1.add(6)
// 创建集合2
let set2 = new Set()
// 向集合2中添加元素 3 2 8
set2.add(3)
set2.add(2)
set2.add(8)
// 获取集合1和集合2的交集，即集合3
let set3 = set1.intersect(set2)
// 查看集合3内的所有元素
console.log(set3.values())
/* 打印结果：
[ '3' ]
*/（10）实现difference()方法
difference() 方法是用于获取当前集合与另一个集合的差集。该放需要传入一个集合 otherSet 作为参数
实现思路：
- 先创建一个空的新集合
newSet - 通过
values()方法获取到包含当前集合的所有元素的数组oldSetValue，并对其进行遍历，判断每一个元素是否也存在于otherSet中，若存在，则不做任何处理 - 若不存在，则将该元素添加到
newSet中去 - 返回
newSet
我们来看一下代码
function Set() {
// 属性
this.items = {}
// 方法
// 获取差集
Set.prototype.difference = function(otherSet) {
// 1. 创建空的新集合
let newSet = new Set()
// 2. 获取当前集合的所有元素
let oldSetValue = this.values()
// 3. 遍历当前集合的所有元素
for(let i = 0; i < oldSetValue.length; i++) {
let item = oldSetValue[i]
// 3.1 otherSset中没有该元素
if(!otherSet.has(item)) {
newSet.add(item)
}
}
// 4. 返回获取到的差集
return newSet
}
}我们来使用一下该方法
// 创建集合1
let set1 = new Set()
// 向集合1中添加元素 3 1 6
set1.add(3)
set1.add(1)
set1.add(6)
// 创建集合2
let set2 = new Set()
// 向集合2中添加元素 3 2 8
set2.add(3)
set2.add(2)
set2.add(8)
// 获取集合1和集合2的差集，即集合3
let set3 = set1.difference(set2)
// 查看集合3内的所有元素
console.log(set3.values())
/* 打印结果：
[ '1', '6' ]
*/（11）实现subset()方法
subset() 方法用于判断当前集合是否为另一个集合的子集。该方法需要传入一个集合 otherSet 作为参数
实现思路：
- 先创建一个空的新集合
newSet - 通过
values()方法获取到包含当前集合的所有元素的数组oldSetValue，并对其进行遍历，判断每一个元素是否也存在于otherSet中，若不存在，则直接返回false，表示当前集合不是otherSet的子集 - 若所有元素遍历完后，该方法仍为返回任何值，此时直接返回
true，表示当前集合为otherSet的子集
我们来看一下代码
function Set() {
// 属性
this.items = {}
// 方法
// 判断是否为另一个集合的子集
Set.prototype.subset = function(otherSet) {
// 1. 创建空的新集合
let oldSetValue = this.values()
for(let i = 0; i < oldSetValue.length; i++) {
if(!otherSet.has(oldSetValue[i])) {
return false
}
}
return true
}
}我们来是用一下该方法
// 创建集合1
let set1 = new Set()
// 向集合1中添加元素 3 1
set1.add(3)
set1.add(1)
// 创建集合2
let set2 = new Set()
// 向集合2中添加元素 3 2 8 1 9
set2.add(3)
set2.add(2)
set2.add(8)
set2.add(1)
set2.add(9)
// 判断集合1是否为集合2的子集
let ret = set1.subset(set2)
// 查看集合3内的所有元素
console.log(ret)
// 打印结果：true五、结束语
集合的讲解就到这里了，希望大家对集合有了更深一层的理解。下一篇文章我将讲解一下图。
大家可以关注我，之后我还会一直更新别的数据结构与算法的文章来供大家学习，并且我会把这些文章放到【数据结构与算法】这个专栏里，供大家学习使用。
然后大家可以关注一下我的微信公众号：前端印象，等这个专栏的文章完结以后，我会把每种数据结构和算法的笔记放到公众号上，大家可以去那获取。
或者也可以去我的github上获取完整代码，欢迎大家点个Star
- https://github.com/Lpyexplore/structureAndAlgorithm-JS
我是Lpyexplore，创作不易，喜欢的加个关注，点个收藏，给个赞~ 带你们在Python爬虫的过程中学习Web前端