【数据结构与算法】详解什么是集合，并用代码手动实现一个集合结构

亦凉 2022-12-02 04:16 138阅读 0赞

本系列文章【数据结构与算法】所有完整代码已上传 **github**，想要**完整代码**的小伙伴可以直接去那获取，可以的话欢迎点个**Star**哦~下面放上跳转链接

*  [https://github.com/Lpyexplore/structureAndAlgorithm-JS][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

**集合**这个概念应该大家在学习数学的时候都听过并且有学习过，它也是一种数据结构，我们还是需要用代码来实现集合的很多方法。

学习过ES6语法的小伙伴应该知道，ES6新增了一种 **Set** 数据结构，这就是集合，尽管官方已经向我们提供了这种数据结构，但是为了学习它的思想和实现过程，我们还是来亲自学习实现一下吧，顺便学习一下ES6中 `Set` 数据结构是如何实现的

>  *  公众号：**前端印象**
>  *  不定时有送书活动，记得关注~
>  *  关注后回复对应文字领取：【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center]

### 数据结构——集合 ###

*  一、什么是集合
 *  二、集合分类
 *   *  （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()方法
 *  五、结束语

# 一、什么是集合 #

**集合**就是一种包含着不同元素的数据结构，即在集合结构里，每一个元素都是独一无二的，互不相同，同时所有数据都是无序的。

如图中的每个圆圈就代表一个集合，集合中存储着相应的数据  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 1]

其中，`集合1` 和 `集合2` 中同样是存储着数据 `1 2 3 4`，但分布情况却不同，这说明集合的**无序性**，而且 `集合1` 与 `集合2`并不相等

# 二、集合分类 #

集合也有几种特殊的分类，即 **并集** 、**交集** 、**差集** 、**子集**。其展示的是两个集合之间的关系

## （1）交集 ##

**交集**就是由既属于 `集合1` 又属于 `集合2` 的元素组成的集合。

如图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 2]

集合1中有数据 `1 2 3 4`  
集合2中有数据 `1 2 4 5 8`

那么既属于 `集合1` 又属于 `集合2` 的元素就是 `1 2 4`，因此这几个元素就组合成了新的集合 `集合3`，也称为 `集合1` 与 `集合2` 的**交集**

## （2）并集 ##

**并集：** 由所有属于 `集合1` 和 `集合2` 的元素组成的集合

如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 3]

集合1中有数据 `1 4`  
集合2中有数据 `2 3 5 8`

那么 `集合1` 与 `集合2` 所有元素组合起来就是 `1 2 3 4 5 8`·，这些元素组合起来就组成了新集合 `集合3`，也称 `集合3` 为 `集合1` 与 `集合2` 的**并集**

## （3）差集 ##

**差集：** 就是属于 `集合1` 但不属于 `集合2` 的所有元素组成的集合

如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 4]  
集合1中有数据 `1 2 4`  
集合2中有数据 `1 3 5 8`

那么属于 `集合1` 但不属于 `集合2` 的元素就是 `2 4`，这两个元素组成了新的集合 `集合3`，也称 `集合3` 为 `集合1` 与 `集合2` 的**差集**

## （4）子集 ##

**子集：** 是判断属于 `集合1` 的元素是否也都属于 `集合2`

如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 5]  
集合1中有数据 `1 2 4`  
集合2中有数据 `1 2 3 4 5 8`

此时因为 `集合1` 中的所有元素同时也属于 `集合2`，所以说 `集合1` 是 `集合2` 的子集，也可以说是 `集合1` 属于 `集合2`

# 三、集合的方法 #

了解了以上这些集合的概念，接下来我们来看一下封装一个集合，都有哪些方法。

首先一个数据结构，必备的增删改查方法是肯定需要的，其次我们尽可能地与ES6的 `Set` 数据结构中的方法一致，这样方便大家之后学习

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>add()</td> 
   <td>将一个数据添加到集合中</td> 
  </tr> 
  <tr> 
   <td>has()</td> 
   <td>判断一个元素是否存在于集合中</td> 
  </tr> 
  <tr> 
   <td>delete()</td> 
   <td>删除集合中的某个元素</td> 
  </tr> 
  <tr> 
   <td>clear()</td> 
   <td>清空集合内的所有元素</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>返回集合内的元素个数</td> 
  </tr> 
  <tr> 
   <td>values()</td> 
   <td>返回集合内的所有元素，保存在数组中</td> 
  </tr> 
  <tr> 
   <td>union()</td> 
   <td>获取与另一个集合的并集</td> 
  </tr> 
  <tr> 
   <td>intersect()</td> 
   <td>获取与另一个集合的交集</td> 
  </tr> 
  <tr> 
   <td>difference()</td> 
   <td>获取与另一个集合的差集</td> 
  </tr> 
  <tr> 
   <td>subset()</td> 
   <td>判断是否为另一个集合的子集</td> 
  </tr> 
 </tbody> 
</table>

# 四、用代码实现集合 #

## （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` 作为参数

**实现思路：**

1.  先创建一个空的新集合 `newSet`
2.  通过 `values()` 方法获取到包含当前集合的所有元素的数组 `oldSetValue`，并对其进行遍历，将遍历到每一个元素都添加到 `newSet()` 中去
3.  再通过 `values()` 方法获取到包含 `otherSet` 的所有元素的数组 `otherSetValue`，并对其进行遍历，将遍历到每一个元素都添加到 `newSet()` 中去
4.  返回 `newSet`

在该实现过程中，我们是通过 `add()` 方法将两个集合中的所有元素添加到新的集合中的，因为 `add()` 方法中已经包含了检验元素的重复性部分，所以我们无需担心两个集合的元素是否会重复

我们来看一下代码

我们来使用一下该方法

// 创建集合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` 作为参数

**实现思路：**

1.  先创建一个空的新集合 `newSet`
2.  通过 `values()` 方法获取到包含当前集合的所有元素的数组 `oldSetValue`，并对其进行遍历，判断每一个元素是否也存在于 `otherSet` 中，若不存在，则不做任何处理
3.  若存在，则将该元素添加到 `newSet` 中去
4.  返回 `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` 作为参数

**实现思路：**

1.  先创建一个空的新集合 `newSet`
2.  通过 `values()` 方法获取到包含当前集合的所有元素的数组 `oldSetValue`，并对其进行遍历，判断每一个元素是否也存在于 `otherSet` 中，若存在，则不做任何处理
3.  若不存在，则将该元素添加到 `newSet` 中去
4.  返回 `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` 作为参数

**实现思路：**

1.  先创建一个空的新集合 `newSet`
2.  通过 `values()` 方法获取到包含当前集合的所有元素的数组 `oldSetValue`，并对其进行遍历，判断每一个元素是否也存在于 `otherSet` 中，若不存在，则直接返回 `false`，表示当前集合不是 `otherSet` 的子集
3.  若所有元素遍历完后，该方法仍为返回任何值，此时直接返回 `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][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

我是Lpyexplore，创作不易，喜欢的加个关注，点个收藏，给个赞~ 带你们在Python爬虫的过程中学习Web前端

[https_github.com_Lpyexplore_structureAndAlgorithm-JS]: https://github.com/Lpyexplore/structureAndAlgorithm-JS
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/dc5f46e3157c430c8eb2e9c84ee113de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/1a1a7a8c7792458886c3a3cdc7879cd8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/c7889920a5794a96bcf310b1c10d0472.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/c9527f24f6a2453685848bad854a2fb6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/1040e4eae9ea40fd8fd44b1043144b1b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/db3bca342ff143f2902fce80b338629c.png