JavaScript数据结构与算法（3）集合

素颜马尾好姑娘i 2022-01-30 07:25 249阅读 0赞

主要参考：  
[https://www.cnblogs.com/xiaohuochai/p/8176248.html][https_www.cnblogs.com_xiaohuochai_p_8176248.html]  
《学习JavaScript数据结构与算法》

**1.集合介绍**

一个集合示例：

{1,2,3,4,5}

其实集合set内部是键值对方式：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]  
集合这种键值对方式和字典很相似，集合是以\[值，值\]的形式存储元素，字典则是以\[键，值\]的形式来存储元素。

**2.创建集合**

声明一些集合可用的方法：  
add(value)：向集合添加一个新的项。  
remove(value)：从集合移除一个值。  
has(value)：如果值在集合中，返回true，否则返回false。  
clear()：移除集合中的所有项。  
size()：返回集合所包含元素的数量。与数组的length属性类似。  
values()：返回一个包含集合中所有值的数组。

代码实现如下：

**3.集合操作**

对集合可以进行如下操作  
1、并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合  
2、交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合  
3、差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合  
4、子集：验证一个给定集合是否是另一集合的子集

并集:

this.union = function(otherSet){
    
    	//这里面用到了上面声明的new Set()、values()、add()
    
    	//新的Set合集
    	let unionSet = new Set();
    
    	let values = this.values(); //this，获取当前示例的values（）,即集合的数组形式
    	for(let i=0;i<values.length;i++){
    		unionSet.add(values[i]);
    	}
    
    	let values1 = otherSet.values();
    	for(let i=0;i<values1.length;i++){
    		unionSet.add(values1[i]);
    	}
    
    	return unionSet;
    
    }

交集：

this.intersection = function(otherSet){
    
    	let intersection = new Set();
    
    	let values = this.values();
     
    	for(let i=0;i<values.length;i++){
    		if(otherSet.has(values[i])){
    			intersection.add(values[i]);
    		}
    	}
    
    	return intersection;
    
    }

差集:

this.intersection = function(otherSet){
     let intersectionSet = new Set(); //{1}
     let values = this.values();
     for (let i=0; i<values.length; i++){ //{2}
      if (!otherSet.has(values[i])){ //{3}
        intersectionSet.add(values[i]); //{4}
      }
     }
     return intersectionSet;
    }

子集：

this.subset = function(otherSet){
     if (this.size() > otherSet.size()){ //{1}
      return false;
     } else {
      let values = this.values();
      for (let i=0; i<values.length; i++){ //{2}
        if (!otherSet.has(values[i])){ //{3}
          return false; //{4}
        }
      }
      return true; //{5}
     }
    };

**4.完整代码**

**ES6版本代码：**

**5.ES6中集合**

ECMAScript 2015新增了Set类。我们可以基于ES6的Set开发我们的Set类

和我们的Set不同，ES6的Set的values方法返回Iterator，而不是值构成的数组。另一个区别是，我们实现的size方法返回set中存储的值的个数，而ES6的Set则有一个size属性:

let set = new Set([1,2,3,2,4,5,6,7])
    
    set.has(1)
    true
    
    set.size
    8

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

可以用delete方法删除set中的元素：

set.delete(1)
    true

clear方法会重置set数据结构，这跟我们实现的功能一样

set.clear()
    undefined
    
    set
    Set(0) {}

**ES6中的集合**

更详细可以参考上面链接和书籍。

[https_www.cnblogs.com_xiaohuochai_p_8176248.html]: https://www.cnblogs.com/xiaohuochai/p/8176248.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]: /images/20220130/fe08d00e93f141869903f3eff851b307.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]: /images/20220130/433dd3554191439c98e4cd19617d0639.png