首页 » 学习JavaScript数据结构与算法(第2版) » 学习JavaScript数据结构与算法(第2版)全文在线阅读

《学习JavaScript数据结构与算法(第2版)》6.3 集合操作

关灯直达底部

对集合可以进行如下操作。

  • 并集:对于给定的两个集合,返回一个包含两个集合中所有元素的新集合。

  • 交集:对于给定的两个集合,返回一个包含两个集合中共有元素的新集合。

  • 差集:对于给定的两个集合,返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。

  • 子集:验证一个给定集合是否是另一集合的子集。

6.3.1 并集

并集的数学概念是集合A和集合B的并集,表示为:

AB

该集合定义如下:

AB = { x | xAxB }

意思是x(元素)存在于A中,或x存在于B中。下图展示了并集操作:

现在来实现Set类的union方法:

this.union = function(otherSet){  let unionSet = new Set; //{1}  let values = this.values; //{2}  for (let i=0; i<values.length; i++){    unionSet.add(values[i]);  }  values = otherSet.values; //{3}  for (let i=0; i<values.length; i++){    unionSet.add(values[i]);  }  return unionSet;};  

首先需要创建一个新的集合,代表两个集合的并集(行{1})。接下来,获取第一个集合(当前的Set类实例)所有的值(values),遍历并全部添加到代表并集的集合中(行{2})。然后对第二个集合做同样的事(行{3})。最后返回结果。

测试一下上面的代码:

let setA = new Set;setA.add(1);setA.add(2);setA.add(3);let setB = new Set;setB.add(3);setB.add(4);setB.add(5);setB.add(6);let unionAB = setA.union(setB);console.log(unionAB.values);  

输出为[/"1/", /"2/", /"3/", /"4/", /"5/", /"6/"]。注意元素3同时存在于AB中,它在结果的集合中只出现一次。

6.3.2 交集

交集的数学概念是集合A和集合B的交集,表示为:

AB

该集合定义如下:

AB = { x | xAxB }

意思是x(元素)存在于A中,且x 存在于B中。下图展示了交集操作:

现在来实现Set类的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;}  

intersection方法需要找到当前Set实例中,所有也存在于给定Set实例中的元素。首先创建一个新的Set实例,这样就能用它返回共有的元素(行{1})。接下来,遍历当前Set实例所有的值(行{2}),验证它们是否也存在于otherSet实例(行{3})之中。可以用这一章前面实现的has方法来验证元素是否存在于Set实例中。然后,如果这个值也存在于另一个Set实例中,就将其添加到创建的intersectionSet变量中(行{4}),最后返回它。

做些测试:

let setA = new Set;setA.add(1);setA.add(2);setA.add(3);let setB = new Set;setB.add(2);setB.add(3);setB.add(4);let intersectionAB = setA.intersection(setB);console.log(intersectionAB.values);  

输出为[/"2/", /"3/"],因为23同时存在于两个集合中。

6.3.3 差集

差集的数学概念是集合A和集合B的差集,表示为:A-B,定义如下:

A-B = { x | xAxB }

意思是x(元素)存在于A中,且x不存在于B 中。下图展示了集合AB 的差集操作:

现在来实现Set类的difference方法:

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

intersection方法会得到所有同时存在于两个集合中的值。而difference方法会得到所有存在于集合A但不存在于B的值。因此这两个方法在实现上唯一的区别就是行{3}。只获取不存在于otherSet实例中的值,而不是也存在于其中的值。行{1}{2}{4}是完全相同的。

(用跟intersection部分相同的集合)做些测试:

let setA = new Set;setA.add(1);setA.add(2);setA.add(3);let setB = new Set;setB.add(2);setB.add(3);setB.add(4);let differenceAB = setA.difference(setB);console.log(differenceAB.values);  

输出为[/"1/"],因为1是唯一一个仅存在于setA的元素。

6.3.4 子集

我们要介绍的最后一个集合操作是子集。子集的数学概念是集合A是集合B的子集(或集合B包含了A),表示为:

AB

该集合定义如下:

x { xAxB }

意思是集合A中的每一个x(元素),也需要存在于B 中。下图展示了集合A是集合B 的子集:

现在来实现Set类的subset方法:

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}  }};  

首先需要验证的是当前Set实例的大小。如果当前实例中的元素比otherSet实例更多,它就不是一个子集(行{1})。子集的元素个数需要小于或等于要比较的集合。

接下来要遍历集合中的所有元素(行{2}),验证这些元素也存在于otherSet中(行{3})。如果有任何元素不存在于otherSet中,就意味着它不是一个子集,返回false(行{4})。如果所有元素都存在于otherSet中,行{4}就不会被执行,那么就返回true(行{5})。

检验一下上面的代码效果如何:

let setA = new Set;setA.add(1);setA.add(2);let setB = new Set;setB.add(1);setB.add(2);setB.add(3);let setC = new Set;setC.add(2);setC.add(3);setC.add(4);console.log(setA.subset(setB));console.log(setA.subset(setC));  

我们有三个集合:setAsetB的子集(因此输出为true),然而setA不是setC的子集(setC只包含了setA中的2,而不包含1),因此输出为false