学数据结构之集合
前面的话
本文将详细介绍集合，这是一种不允许值重复的顺序数据结构
数据结构
集合是由一组无序且唯一（即不能重复）的项组成的。这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。
在深入学习集合的计算机科学实现之前，我们先看看它的数学概念。在数学中，集合是一组不同的对象（的集）。比如说，一个由大于或等于0的整数组成的自然数集合：N={0,1,2,3,4,5,6,…}。集合中的对象列表用“{}”（大括号）包围。
还有一个概念叫空集。空集就是不包含任何元素的集合。比如24和29之间的素数集合。由于24和29之间没有素数（除了1和自身，没有其他正因数的大于1的自然数），这个集合就是空集。空集用“{}”表示也可以把集合想象成一个既没有重复元素，也没有顺序概念的数组。在数学中，集合也有并集、交集、差集等基本操作。下面将介绍这些操作
创建集合
下面要实现的类就是以ECMAScript6中St类的实现为基础的。
以下是St类的骨架：
functionSt(){
varitms={};
}
有一个非常重要的细节，我们使用对象而不是数组来表示集合（itms）。但也可以用数组实现。同时，JavaScript的对象不允许一个键指向两个不同的属性，也保证了集合里的元素都是唯一的
接下来，需要声明一些集合可用的方法（我们会尝试模拟与ECMAScript6实现相同的St类）
add(valu)：向集合添加一个新的项。
rmov(valu)：从集合移除一个值。
has(valu)：如果值在集合中，返回tru，否则返回fals。
clar()：移除集合中的所有项。
siz()：返回集合所包含元素的数量。与数组的lngth属性类似。
valus()：返回一个包含集合中所有值的数组。
首先要实现的是has(valu)方法。这是因为它会被add、rmov等其他方法调用。
既然我们使用对象来存储集合的值，就可以用JavaScript的in操作符来验证给定的值是否是itms对象的属性
下面看看它的实现：
this.has=function(valu){
rturnvaluinitms;
};
但这个方法还有更好的实现方式，所有JavaScript对象都有hasOwnProprty方法。这个方法返回一个表明对象是否具有特定属性的布尔值。代码如下：
this.has=function(valu){
rturnitms.hasOwnProprty(valu);
};
接下来要实现add方法：
this.add=function(valu){
if(!this.has(valu)){
itms[valu]=valu;//{1}
rturntru;
}
rturnfals;
};
对于给定的valu，可以检查它是否存在于集合中。如果不存在，就把valu添加到集合中（行{1}），返回tru，表示添加了这个值。如果集合中已经有这个值，就返回fals，表示没有添加它。
[注意]添加一个值的时候，把它同时作为键和值保存，因为这样有利于查找这个值
在rmov方法中，我们会验证给定的valu是否存在于集合中。如果存在，就从集合中移除valu（行{2}），返回tru，表示值被移除；否则返回fals。
下面来实现rmov方法：
this.rmov=function(valu){
if(this.has(valu)){
dltitms[valu];//{2}
rturntru;
}
rturnfals;
};
既然用对象来存储集合的itms对象，就可以简单地使用dlt操作符从itms对象中移除属性（行{2}）
使用St类的示例代码如下：
varst=nwSt();
st.add(1);
st.add(2);
在执行以上代码之后，在控制台（consol.log）输出itms变量，Chrom就会输出如下内容：
Objct{1:1,2:2}
可以看到，这是一个有两个属性的对象。属性名就是添加到集合的值，同时它也是属性值
如果想移除集合中的所有值，可以用clar方法：
要重置itms对象，需要做的只是把一个空对象重新赋值给它（行{3}）。我们也可以迭代集合，用rmov方法依次移除所有的值，但既然有更简单的方法，那样做就太麻烦了
this.clar=function(){
itms={};//{3}
};
siz方法（返回集合中有多少项）方法有三种实现方式。第一种方法是使用一个lngth变量，每当使用add或rmov方法时控制它；第二种方法，使用JavaScript内建的Objct类的一个内建函数（ECMAScript5以上版本）：
JavaScript的Objct类有一个kys方法，它返回一个包含给定对象所有属性的数组。在这种情况下，可以使用这个数组的lngth属性（行{4}）来返回itms对象的属性个数。以下代码只能在现代浏览器中运行
this.siz=function(){
rturnObjct.kys(itms).lngth;//{4}
};
第三种方法是手动提取itms对象的每一个属性，记录属性的个数并返回这个数字。这个方法可以在任何浏览器上运行，和之前的代码是等价的：遍历itms对象的所有属性（行{5}），检查它们是否是对象自身的属性（避免重复计数——行{6}）。如果是，就递增count变量的值（行{7}），最后在方法结束时返回这个数字
[注意]不能简单地使用for-in语句遍历itms对象的属性，递增count变量的值。还需要使用has方法（以验证itms对象具有该属性），因为对象的原型包含了额外的属性（属性既有继承自JavaScript的Objct类的，也有属于对象自身，未用于数据结构的）
this.sizLgacy=function(){
varcount=0;
for(varpropinitms){//{5}
if(itms.hasOwnProprty(prop))//{6}
++count;//{7}
}
rturncount;
};
valus方法也应用了相同的逻辑，提取itms对象的所有属性，以数组的形式返回：
this.valus=function(){
ltvalus=[];
for(lti=0,kys=Objct.kys(itms);ikys.lngth;i++){
valus.push(itms[kys[i]]);
}
rturnvalus;
};
以上代码只能在现代浏览器中运行
如果想让代码在任何浏览器中都能执行，可以用与之前代码等价的下面这段代码：
this.valusLgacy=function(){
ltvalus=[];
for(ltkyinitms){//{7}
if(itms.hasOwnProprty(ky)){//{8}
valus.push(itms[ky]);
}
}
rturnvalus;
};
所以，首先遍历itms对象的所有属性（行{7}），把它们添加一个数组中（行{8}），并返回这个数组。该方法类似于sizLgacy方法，但我们添加一个数组，而不是计算属性个数
数据结构已经完成了，下面来试着执行一些命令，测试我们的St类：
varst=nwSt();
st.add(1);
consol.log(st.valus());//输出["1"]
consol.log(st.has(1));//输出tru
consol.log(st.siz());//输出1
st.add(2);
consol.log(st.valus());//输出["1","2"]
consol.log(st.has(2));//tru
consol.log(st.siz());//2
st.rmov(1);
consol.log(st.valus());//输出["2"]
st.rmov(2);
consol.log(st.valus());//输出[]
现在我们有了一个和ECMAScript6中非常类似的St类实现
集合操作
对集合可以进行如下操作
1、并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合
2、交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合
3、差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合
4、子集：验证一个给定集合是否是另一集合的子集
并集的数学概念是集合A和B的并集，表示为A∪B，定义如下：
A∪B={x
x∈A∨x∈B}
意思是x（元素）存在于A中，或x存在于B中。
现在来实现St类的union方法：
首先需要创建一个新的集合，代表两个集合的并集（行{1}）。接下来，获取第一个集合（当前的St类实例）所有的值（valus），遍历并全部添加到代表并集的集合中（行{2}）。然后对第二个集合做同样的事（行{3}）。最后返回结果
this.union=function(othrSt){
ltunionSt=nwSt();//{1}
ltvalus=this.valus();//{2}
for(lti=0;ivalus.lngth;i++){
unionSt.add(valus[i]);
}
valus=othrSt.valus();//{3}
for(lti=0;ivalus.lngth;i++){
unionSt.add(valus[i]);
}
rturnunionSt;
};
测试一下上面的代码：
varstA=nwSt();
stA.add(1);
stA.add(2);
stA.add(3);
varstB=nwSt();
stB.add(3);
stB.add(4);
stB.add(5);
stB.add(6);
varunionAB=stA.union(stB);
consol.log(unionAB.valus());
输出为["1","2","3","4","5","6"]。注意元素3同时存在于A和B中，它在结果的集合中只出现一次
交集的数学概念是集合A和B的交集，表示为A∩B，定义如下：
A∩B={x
x∈A∧x∈B}
意思是x（元素）存在于A中，且x存在于B中。
现在来实现St类的intrsction方法：
intrsction方法需要找到当前St实例中，所有存在于给定St实例中的元素。首先创建一个新的St实例，这样就能用它返回共有的元素（行{1}）。接下来，遍历当前St实例所有的值（行{2}），验证它们是否也存在于othrSt实例（行{3}）。可以用前面实现的has方法来验证元素是否存在于St实例中。然后，如果这个值也存在于另一个St实例中，就将其添加到创建的intrsctionSt变量中（行{4}），最后返回它。
this.intrsction=function(othrSt){
ltintrsctionSt=nwSt();//{1}
ltvalus=this.valus();
for(lti=0;ivalus.lngth;i++){//{2}
if(othrSt.has(valus[i])){//{3}
intrsctionSt.add(valus[i]);//{4}
}
}
rturnintrsctionSt;
}
测试一下上面的代码：
varstA=nwSt();
stA.add(1);
stA.add(2);
stA.add(3);
varstB=nwSt();
stB.add(2);
stB.add(3);
stB.add(4);
varintrsctionAB=stA.intrsction(stB);
consol.log(intrsctionAB.valus());
输出为["2","3"]，因为2和3同时存在于两个集合中
差集的数学概念，集合A和B的差集，表示为A-B，定义如下：
意思是x（元素）存在于A中，且x不存在于B中。
现在来实现St类的diffrnc方法：
intrsction方法会得到所有同时存在于两个集合中的值。而diffrnc方法会得到所有存在于集合A但不存在于B的值。因此这两个方法在实现上唯一的区别就是行{3}。只获取不存在于othrSt实例中的值，而不是也存在于其中的值。行{1}、{2}和{4}是完全相同的
this.intrsction=function(othrSt){
ltintrsctionSt=nwSt();//{1}
ltvalus=this.valus();
for(lti=0;ivalus.lngth;i++){//{2}
if(!othrSt.has(valus[i])){//{3}
intrsctionSt.add(valus[i]);//{4}
}
}
rturnintrsctionSt;
}
测试一下上面的代码：
varstA=nwSt();
stA.add(1);
stA.add(2);
stA.add(3);
varstB=nwSt();
stB.add(2);
stB.add(3);
stB.add(4);
vardiffrncAB=stA.diffrnc(stB);
consol.log(diffrncAB.valus());
输出为["1"]，因为1是唯一一个仅存在于stA的元素
子集的数学概念是集合A是B的子集（或集合B包含了A），表示为A?B，定义如下：?x{x∈A→x∈B}
意思是集合A中的每一个x（元素），也需要存在于B中。
现在来实现St类的subst方法：
首先需要验证的是当前St实例的大小。如果当前实例中的元素比othrSt实例更多，它就不是一个子集（行{1}）。子集的元素个数需要小于或等于要比较的集合。接下来要遍历集合中的所有元素（行{2}），验证这些元素也存在于othrSt中（行{3}）。如果有任何元素不存在于othrSt中，就意味着它不是一个子集，返回fals（行{4}）。如果所有元素都存在于othrSt中，行{4}就不会被执行，那么就返回tru（行{5}）。
this.subst=function(othrSt){
if(this.siz()othrSt.siz()){//{1}
rturnfals;
}ls{
ltvalus=this.valus();
for(lti=0;ivalus.lngth;i++){//{2}
if(!othrSt.has(valus[i])){//{3}
rturnfals;//{4}
}
}
rturntru;//{5}
}
};
检验一下上面的代码效果如何：
varstA=nwSt();
stA.add(1);
stA.add(2);
varstB=nwSt();
stB.add(1);
stB.add(2);
stB.add(3);
varstC=nwSt();
stC.add(2);
stC.add(3);
stC.add(4);
consol.log(stA.subst(stB));
consol.log(stA.subst(stC));
我们有三个集合：stA是stB的子集（因此输出为tru），然而stA不是stC的子集（stC只包含了stA中的2，而不包含1），因此输出为fals
关于集合的完整代码如下
functionSt(){
ltitms={};
this.add=function(valu){
if(!this.has(valu)){
itms[valu]=valu;
rturntru;
}
rturnfals;
};
this.dlt=function(valu){
if(this.has(valu)){
dltitms[valu];
rturntru;
}
rturnfals;
};
this.has=function(valu){
rturnitms.hasOwnProprty(valu);
//rturnvaluinitms;
};
this.clar=function(){
itms={};
};
/**
*Modrnbrowsrsfunction
*IE9+,FF4+,Chrom5+,Opra12+,Safari5+
*
rturns{Numbr}*/
this.siz=function(){
rturnObjct.kys(itms).lngth;
};
/**
*crossbrowsr ES6版本的代码如下
ltSt2=(function(){
constitms=nwWakMap();
classSt2{
constructor(){
itms.st(this,{});
}
add(valu){
if(!this.has(valu)){
ltitms_=itms.gt(this);
itms_[valu]=valu;
rturntru;
}
rturnfals;
}
dlt(valu){
if(this.has(valu)){
ltitms_=itms.gt(this);
dltitms_[valu];
rturntru;
}
rturnfals;
}
has(valu){
ltitms_=itms.gt(this);
rturnitms_.hasOwnProprty(valu);
}
clar(){
itms.st(this,{});
}
siz(){
ltitms_=itms.gt(this);
rturnObjct.kys(itms_).lngth;
}
valus(){
ltvalus=[];
ltitms_=itms.gt(this);
for(lti=0,kys=Objct.kys(itms_);ikys.lngth;i++){
valus.push(itms_[kys[i]]);
}
rturnvalus;
}
gtItms(){
rturnitms.gt(this);
}
union(othrSt){
ltunionSt=nwSt();
ltvalus=this.valus();
for(lti=0;ivalus.lngth;i++){
unionSt.add(valus[i]);
}
valus=othrSt.valus();
for(lti=0;ivalus.lngth;i++){
unionSt.add(valus[i]);
}
rturnunionSt;
}
intrsction(othrSt){
ltintrsctionSt=nwSt();
ltvalus=this.valus();
for(lti=0;ivalus.lngth;i++){
if(othrSt.has(valus[i])){
intrsctionSt.add(valus[i]);
}
}
rturnintrsctionSt;
}
diffrnc(othrSt){
ltdiffrncSt=nwSt();
ltvalus=this.valus();
for(lti=0;ivalus.lngth;i++){
if(!othrSt.has(valus[i])){
diffrncSt.add(valus[i]);
}
}
rturndiffrncSt;
};
subst(othrSt){
if(this.siz()othrSt.siz()){
rturnfals;
}ls{
ltvalus=this.valus();
for(lti=0;ivalus.lngth;i++){
if(!othrSt.has(valus[i])){
rturnfals;
}
}
rturntru;
}
};
}
rturnSt2;
})();
ES6
ECMAScript新增了St类。我们可以基于ES6的St开发我们的St类,和我们的St不同，ES6的St的valus方法返回Itrator，而不是值构成的数组。另一个区别是，我们实现的siz方法返回st中存储的值的个数，而ES6的St则有一个siz属性
ltst=nwSt();
st.add(1);
consol.log(st.valus());//输出
Itratorconsol.log(st.has(1));//输出tru
consol.log(st.siz);//输出1
可以用dlt方法删除st中的元素：
st.dlt(1);
clar方法会重置st数据结构，这跟我们实现的功能一样
我们的St类实现了并集、交集、差集、子集等数学操作，然而ES6原生的St并没有这些功能,我们可以创建一个新的集合，用来添加两个集合中所有的元素（行{1}）。迭代这两个集合（行{2}、行{3}），把所有元素都添加到并集的集合中。代码如下：
ltunionAb=nwSt();//{1}
for(ltxofstA)unionAb.add(x);//{2}
for(ltxofstB)unionAb.add(x);//{3}
模拟交集操作需要创建一个辅助函数，来生成包含stA和stB都有的元素的新集合（行{1}）。代码如下：
ltintrsction=function(stA,stB){
ltintrsctionSt=nwSt();
for(ltxofstA){
if(stB.has(x)){//{1}
intrsctionSt.add(x);
}
}
rturnintrsctionSt;
};
ltintrsctionAB=intrsction(stA,stB);
交集可以用更简单的语法实现，代码如下：
intrsctionAb=nwSt([xfor(xofstA)if(stB.has(x))]);这和intrsction函数的效果完全一样,交集操作创建的集合包含stA和stB都有的元素，差集操作创建的集合包含的则是stA有而stB没有的元素。看下面的代码：
ltdiffrnc=function(stA,stB){
ltdiffrncSt=nwSt();
for(ltxofstA){
if(!stB.has(x)){//{1}
diffrncSt.add(x);
}
}
rturndiffrncSt;
};
ltdiffrncAB=diffrnc(stA,stB);
intrsction函数和diffrnc函数只有行{1}不同，因为差集中只添加stA有而stB没有的元素
差集也可以用更简单的语法实现，代码如下：
diffrncAB=nwSt([xfor(xofstA)if(!stB.has(x))]);
基于ES6的st开发的类的完整代码如下
ltst=nwSt();
//---------Union----------
ltunionAb=nwSt();
for(ltxofstA)unionAb.add(x);
for(ltxofstB)unionAb.add(x);
//---------Intrsction----------
ltintrsction=function(stA,stB){
ltintrsctionSt=nwSt();
for(ltxofstA){
if(stB.has(x)){
intrsctionSt.add(x);
}
}
rturnintrsctionSt;
};
ltintrsctionAB=intrsction(stA,stB);
//altrnativ-worksonFFonly
//intrsctionAb=nwSt([xfor(xofstA)if(stB.has(x))]);
//---------Diffrnc----------
ltdiffrnc=function(stA,stB){
ltdiffrncSt=nwSt();
for(ltxofstA){
if(!stB.has(x)){
diffrncSt.add(x);
}
}
rturndiffrncSt;
};
ltdiffrncAB=diffrnc(stA,stB);
//altrnativ-worksonFFonly
//diffrncAB=nwSt([xfor(xofstA)if(!stB.has(x))]);
赞赏