JS中的算法与数据结构之集合(Set)实例详解
本文实例讲述了JS中的算法与数据结构之集合(Set)。分享给大家供大家参考，具体如下：
集合(Set)
同数学中所学的一样，集合(Set)是由一组无序但彼此之间又有一定关系性的成员构成，每个成员在集合中只能出现一次，不同于我们之前说的字典，链表之类的，它是一种包含了不同元素的数据结构(集合中的元素称为成员)，从其定义中我们可以看出它具有两个很重要的特征：首先，集合中的成员是无序的，其次，集合中的成员是不相同的，即集合中不存在相同的成员。
实际上，很多编程语言中，集合并不是一种数据类型，但是如果你需要创建一个数据结构用来保存一些独一无二的元素时，集合就变得很有用了，接下来我们一起来看看JS中如何实现一个集合。
集合的定义
我们要实现一个集合，首先要对其一些定义做了解
- 不包含任何成员的集合称为空集，包含一切可能成员的集合称为全集。
- 如果两个集合里的成员都完全相同，则称两个集合相等。
- 如果一个集合所有成员都包含于另一个集合，则前一集合称为后一集合的一个子集。
集合的操作
通常来说，集合的基本操作有以下三种：
- 并集：将两个集合中的成员进行合并，得到一个新的集合
- 交集：将两个集合中共同存在的成员组成的一个新的集合
- 补集：属于一个集合而不属于另一个集合的成员组成的新的集合
集合的实现
集合（Set）的实现我们这里基于数组，用数组来存储数据，根据我们之前学习的以及上面提到的一些方法，我们可以将集合的构造函数定义如下（为了区别ES6的set类型，我们这里选择用MySet命名）：
//构造函数
functionMySet(){
this.dataStore=[];//数据存储
this.add=add;//添加成员
this.remove=remove;//删除成员
this.size=size;//集合元素个数
this.union=union;//集合求并集
this.intersect=intersect;//集合求交集
this.subset=subset;//判断一个集合是否是另一集合的子集
this.difference=difference;//集合求补集
this.contains=contains;//判断某成员是否属于该集合
this.show=show;//显示当前集合
}
我们第一个要实现的方法就是向集合中添加一个成员，即add方法
add：向集合中添加一个成员
//添加元素
functionadd(data){
//判断元素是否存在集合当中
if(this.dataStore.indexOf(data)<0){
this.dataStore.push(data);
returntrue;
}else{
console.warn('Cannotadd'+data+',mustalreadybeinset');
returnfalse;
}
}
我们之前提到，集合中的元素是独一无二的，因此，我们在将数据存储到数组之前，首先就是要确保该集合不存在该数据，因此，我们先用indexOf方法检查新加入的元素是否存在，如果找到了就返回该成员在数组中的位置；否则，就返回-1，那么对应的add方法就可以定义返回布尔值，添加成功我们返回true，否则返回false，这样就可以明确告诉我们是否正确的插入了一个元素。
remove：删除集合中某个成员
//删除元素
functionremove(data){
//判断元素是否存在集合当中
varpos=this.dataStore.indexOf(data);
if(pos>-1){
this.dataStore.splice(pos,1);
returntrue;
}else{
console.warn(data+'isnotinset');
returnfalse;
}
}
这里，我们顺理成章的实现了删除方法，它跟add方法很类似，首先要检查待删除元素是否存在于数组中，如果存在，我们调用数组的splice()方法删除该元素并返回true，否则，直接返回false，表示集合中不存在该元素。
现在，我们可以完成集合的添加和删除，要测试这些方法之前，我们首先得定义show方法，该方法用来显示集合中的成员，该方法的实现很简答，只需返回我们定义的数组即可：
show：显示集合中的成员
//显示集合成员
functionshow(){
console.log(this.dataStore);
returnthis.dataStore;
}
接着，我们这会来测试一下：
varfruits=newMySet();
//添加成员
fruits.add('Apple');
fruits.add('Banana');
fruits.add('Pear');
fruits.show();//["Apple","Banana","Pear"]
//添加重复成员
fruits.add('Apple');//CannotaddApple,mustalreadybeinset
//删除成员
fruits.remove('Banana');
fruits.show();//["Apple","Pear"]
//删除不存在的成员
fruits.remove('Banana');//Bananaisnotinset
嗯，一切正常，我们可以来实现集合的一些高级操作了，我们先来看看union（并集）的实现。
union：求集合并集
求集合的并集，就是要将两个集合合并成一个，并除去重复的元素，我们实现思路就是将第一个集合成员放到一个临时集合中，判断第二个集合的成员是否也属于第一个集合，如果为真，代表为重复元素，我们直接跳过该成员，否则将该成员加入临时集合，最后返回该集合即可；
那么，问题来了，我们要如何判断一个成员是否存在于该集合中？因此，我们需要一个辅助方法contains()，它的实现也非常简单，直接用indexOf判断即可
//判断元素是否属于该集合
functioncontains(data){
if(this.dataStore.indexOf(data)>-1){
returntrue;
}else{
returnfalse;
}
}
现在，我们可以定义union方法了
//求集合的并集
functionunion(set){
vartempSet=newMySet();
for(vari=0;i
这样，我们就可以就集合的并集了，
varfruits1=newMySet();
fruits1.add('Apple');
fruits1.add('Banana');
fruits1.add('Pear');
varfruits2=newMySet();
fruits2.add('Grape');
fruits2.add('Banana');
fruits2.add('Pear');
fruits2.add('Orange');
varunion=fruits1.union(fruits2);
union.show();//["Apple","Banana","Pear","Grape","Orange"]
成功了！我们可以来看看求集合的交集了。
intersect：求集合的交集
有了上面求并集的思路，那么交集的定义来说也相对简单，思路就是发现第一个集合的成员也属于第二个集合时，就将该成员加入到新的集合，最后返回新的集合即可；
//求集合的交集
functionintersect(set){
vartempSet=newMySet();
for(vari=0;i
我们还是利用上面的两个集合接着求其交集：
varintersect=fruits1.intersect(fruits2);
intersect.show();//["Banana","Pear"]
下一个定义的操作是subset；
subset：判断集合是否是另一集合的子集
该方法首先要确定该集合的长度是否小于待比较的集合。如果该集合比待比较集合还要大，那么肯定不是待比较集合的一个子集。只要当，待比较集合比较大时，才去判断集合类的成员是否都属于待比较集合，如果有一个不是，直接返回false，只有当所有元素都属于待比较集合的时候，我们才能说该集合是待比较集合的一个子集，该方法才会返回true,为了方便查看，我加入了console打印；
//子集判断
functionsubset(set){
if(this.size()>set.size()){
console.log('notasubset');
returnfalse;
}else{
for(vari=0;i
我们看到上面用到了size方法，它的定义如下：
//返回集合长度
functionsize(){
returnthis.dataStore.length;
}
我们保留上面的fruits1和fruits2，新建一个fruits3来演示subset方法
varfruits3=newMySet();
fruits3.add('Apple');
fruits3.add('Banana');
fruits3.add('Pear');
fruits3.add('Grape');
fruits3.add('Orange');
//子集判断
fruits1.subset(fruits2);//notasubset
fruits2.subset(fruits2);//asubset
fruits1.subset(fruits3);//asubset
看起来一切都很顺利，我们只剩最后一个difference方法，该方法返回一个新集合，该集合是由属于第一个集合而不属于第二个集合的成员组成的。
difference：补集
有了交集的思路，补集的实现就显得很自然了。
//补集
functiondifference(set){
vartempSet=newMySet();
for(vari=0;i
我们测试一下：
fruits1.difference(fruits2).show();//['Apple']
fruits1.difference(fruits3).show();//[]
fruits2.difference(fruits1).show();//["Grape","Orange"]
ok，到现在，我们完成了一个完整的set集合，是不是很棒！
本篇介绍的集合和ES6的集合略微有点差别，ES6提供的Set数据结构，有很多现成的方法可以直接调用，很是方法，不是很了解的小伙伴可以参考我之前的一篇博文，关于ES6中Symbol、Set和Map一文，相信会有不错的收获~
感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。
更多关于JavaScript相关内容可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。