【数据结构与算法】详解什么是集合，并用代码手动实现一个集合结构 |
您所在的位置：网站首页 › 数据结构的实现是指什么 › 【数据结构与算法】详解什么是集合，并用代码手动实现一个集合结构 |
【数据结构与算法】详解什么是集合，并用代码手动实现一个集合结构
|
本系列文章【数据结构与算法】所有完整代码已上传 github，想要完整代码的小伙伴可以直接去那获取，可以的话欢迎点个Star哦~下面放上跳转链接 https://github.com/Lpyexplore/structureAndAlgorithm-JS集合这个概念应该大家在学习数学的时候都听过并且有学习过，它也是一种数据结构，我们还是需要用代码来实现集合的很多方法。 学习过ES6语法的小伙伴应该知道，ES6新增了一种 Set 数据结构，这就是集合，尽管官方已经向我们提供了这种数据结构，但是为了学习它的思想和实现过程，我们还是来亲自学习实现一下吧，顺便学习一下ES6中 Set 数据结构是如何实现的 公众号：前端印象不定时有送书活动，记得关注~关注后回复对应文字领取：【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】
集合就是一种包含着不同元素的数据结构，即在集合结构里，每一个元素都是独一无二的，互不相同，同时所有数据都是无序的。 如图中的每个圆圈就代表一个集合，集合中存储着相应的数据 其中，集合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 但不属于 集合2 的元素就是 2 4，这两个元素组成了新的集合 集合3，也称 集合3 为 集合1 与 集合2 的差集 （4）子集子集： 是判断属于 集合1 的元素是否也都属于 集合2 如图 此时因为 集合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 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 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 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 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前端 |
集合1中有数据 1 2 4 集合2中有数据 1 3 5 8
集合1中有数据 1 2 4 集合2中有数据 1 2 3 4 5 8【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |