JS中的算法与数据结构之集合(Set)实例详解
作者:Cryptic 发布时间:2024-04-16 09:28:34
本文实例讲述了JS中的算法与数据结构之集合(Set)。分享给大家供大家参考,具体如下:
集合(Set)
同数学中所学的一样,集合(Set)是由一组无序但彼此之间又有一定关系性的成员构成,每个成员在集合中只能出现一次,不同于我们之前说的字典,链表之类的,它是一种包含了不同元素的数据结构(集合中的元素称为成员),从其定义中我们可以看出它具有两个很重要的特征:首先,集合中的成员是无序的,其次,集合中的成员是不相同的,即集合中不存在相同的成员。
实际上,很多编程语言中,集合并不是一种数据类型,但是如果你需要创建一个数据结构用来保存一些独一无二的元素时,集合就变得很有用了,接下来我们一起来看看JS中如何实现一个集合。
集合的定义
我们要实现一个集合,首先要对其一些定义做了解
不包含任何成员的集合称为空集,包含一切可能成员的集合称为全集。
如果两个集合里的成员都完全相同,则称两个集合相等。
如果一个集合所有成员都包含于另一个集合,则前一集合称为后一集合的一个子集。
集合的操作
通常来说,集合的基本操作有以下三种:
并集:将两个集合中的成员进行合并,得到一个新的集合
交集:将两个集合中共同存在的成员组成的一个新的集合
补集:属于一个集合而不属于另一个集合的成员组成的新的集合
集合的实现
集合(Set)的实现我们这里基于数组,用数组来存储数据,根据我们之前学习的以及上面提到的一些方法,我们可以将集合的构造函数定义如下(为了区别ES6的 set 类型,我们这里选择用 MySet 命名):
//构造函数
function MySet () {
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:向集合中添加一个成员
//添加元素
function add (data) {
//判断元素是否存在集合当中
if( this.dataStore.indexOf( data ) < 0 ){
this.dataStore.push(data);
return true;
}else{
console.warn( 'Can not add ' + data + ', must already be in set');
return false;
}
}
我们之前提到,集合中的元素是独一无二的,因此,我们在将数据存储到数组之前,首先就是要确保该集合不存在该数据,因此,我们先用 indexOf 方法检查新加入的元素是否存在,如果找到了就返回该成员在数组中的位置;否则,就返回 -1 ,那么对应的 add 方法就可以定义返回布尔值,添加成功我们返回 true , 否则返回 false ,这样就可以明确告诉我们是否正确的插入了一个元素。
remove:删除集合中某个成员
//删除元素
function remove (data) {
//判断元素是否存在集合当中
var pos = this.dataStore.indexOf(data);
if( pos > -1 ){
this.dataStore.splice(pos,1);
return true;
}else{
console.warn( data + ' is not in set');
return false;
}
}
这里,我们顺理成章的实现了删除方法,它跟 add 方法很类似,首先要检查待删除元素是否存在于数组中,如果存在,我们调用数组的 splice() 方法删除该元素并返回 true ,否则,直接返回 false ,表示集合中不存在该元素。
现在,我们可以完成集合的添加和删除,要测试这些方法之前,我们首先得定义 show 方法,该方法用来显示集合中的成员,该方法的实现很简答,只需返回我们定义的数组即可:
show:显示集合中的成员
// 显示集合成员
function show(){
console.log(this.dataStore);
return this.dataStore;
}
接着,我们这会来测试一下:
var fruits = new MySet();
// 添加成员
fruits.add('Apple');
fruits.add('Banana');
fruits.add('Pear');
fruits.show(); // ["Apple", "Banana", "Pear"]
// 添加重复成员
fruits.add('Apple'); // Can not add Apple, must already be in set
// 删除成员
fruits.remove('Banana');
fruits.show(); // ["Apple", "Pear"]
// 删除不存在的成员
fruits.remove('Banana'); // Banana is not in set
嗯,一切正常,我们可以来实现集合的一些高级操作了,我们先来看看 union (并集)的实现。
union:求集合并集
求集合的并集,就是要将两个集合合并成一个,并除去重复的元素,我们实现思路就是将第一个集合成员放到一个临时集合中,判断第二个集合的成员是否也属于第一个集合,如果为真,代表为重复元素,我们直接跳过该成员,否则将该成员加入临时集合,最后返回该集合即可;
那么,问题来了,我们要如何判断一个成员是否存在于该集合中?因此,我们需要一个辅助方法 contains(),它的实现也非常简单,直接用 indexOf 判断即可
//判断元素是否属于该集合
function contains (data) {
if( this.dataStore.indexOf(data) > -1 ){
return true;
}else{
return false;
}
}
现在,我们可以定义 union 方法了
//求集合的并集
function union ( set ) {
var tempSet = new MySet();
for( var i = 0 ; i < this.dataStore.length ; i++ ){
tempSet.add(this.dataStore[i]);
}
for( var i = 0 ; i< set.dataStore.length ; i++ ){
if( !tempSet.contains(set.dataStore[i])){
tempSet.dataStore.push(set.dataStore[i]);
}
}
return tempSet;
}
这样,我们就可以就集合的并集了,
var fruits1 = new MySet();
fruits1.add('Apple');
fruits1.add('Banana');
fruits1.add('Pear');
var fruits2 = new MySet();
fruits2.add('Grape');
fruits2.add('Banana');
fruits2.add('Pear');
fruits2.add('Orange');
var union = fruits1.union( fruits2 );
union.show(); // ["Apple", "Banana", "Pear", "Grape", "Orange"]
成功了!我们可以来看看求集合的交集了。
intersect:求集合的交集
有了上面求并集的思路,那么交集的定义来说也相对简单,思路就是发现第一个集合的成员也属于第二个集合时,就将该成员加入到新的集合,最后返回新的集合即可;
//求集合的交集
function intersect (set) {
var tempSet = new MySet();
for(var i = 0 ; i < this.dataStore.length ; i++ ){
if( set.contains(this.dataStore[i])){
tempSet.add(this.dataStore[i]);
}
}
return tempSet;
}
我们还是利用上面的两个集合接着求其交集:
var intersect = fruits1.intersect( fruits2 );
intersect.show(); // ["Banana", "Pear"]
下一个定义的操作是 subset ;
subset:判断集合是否是另一集合的子集
该方法首先要确定 该集合的长度是否小于待比较的集合。如果该集合比待比较集合还要大,那么肯定不是待比较集合的一个子集。只要当,待比较集合比较大时,才去判断集合类的成员是否都属于待比较集合,如果有一个不是,直接返回 false , 只有当所有元素都属于待比较集合的时候,我们才能说该集合是待比较集合的一个子集,该方法才会返回 true , 为了方便查看,我加入了console打印;
//子集判断
function subset (set) {
if( this.size() > set.size() ){
console.log('not a subset');
return false;
}else{
for ( var i = 0 ; i < this.dataStore.length ; i++ ){
if( !set.contains(this.dataStore[i])){
console.log('not a subset');
return false;
}
}
}
console.log(' a subset');
return true;
}
我们看到上面用到了 size 方法,它的定义如下:
//返回集合长度
function size () {
return this.dataStore.length;
}
我们保留上面的 fruits1 和 fruits2 , 新建一个 fruits3 来演示 subset 方法
var fruits3 = new MySet();
fruits3.add('Apple');
fruits3.add('Banana');
fruits3.add('Pear');
fruits3.add('Grape');
fruits3.add('Orange');
//子集判断
fruits1.subset( fruits2 ); // not a subset
fruits2.subset( fruits2 ); // a subset
fruits1.subset( fruits3 ); // a subset
看起来一切都很顺利,我们只剩最后一个 difference 方法,该方法返回一个新集合,该集合是由属于第一个集合而不属于第二个集合的成员组成的。
difference:补集
有了交集的思路,补集的实现就显得很自然了。
//补集
function difference (set) {
var tempSet = new MySet();
for( var i = 0 ; i < this.dataStore.length ; i ++ ){
if( !set.contains(this.dataStore[i])){
tempSet.dataStore.push( this.dataStore[i] );
}
}
return tempSet;
}
我们测试一下:
fruits1.difference(fruits2).show(); // ['Apple']
fruits1.difference(fruits3).show(); // []
fruits2.difference(fruits1).show(); // ["Grape", "Orange"]
ok,到现在,我们完成了一个完整的 set 集合,是不是很棒!
本篇介绍的集合和 ES6 的集合略微有点差别,ES6 提供的 Set 数据结构,有很多现成的方法可以直接调用,很是方法,不是很了解的小伙伴可以参考我之前的一篇博文,关于ES6中Symbol 、Set 和 Map 一文,相信会有不错的收获~
希望本文所述对大家JavaScript程序设计有所帮助。
来源:https://www.jianshu.com/p/e2d208725bc3
猜你喜欢
- 本期做一个selenium详细实例,会把我在元素定位中遇到的一些阻塞和经验分享给大家。(浏览器为Chrome)(如果只需要最终的完整代码,请
- 本文实例讲述了python通过ssh-powershell监控windows的方法。分享给大家供大家参考。具体分析如下:对于服务器的监控来说
- 打算切换某个网站的主机,没想到遇到Php和Mysql中文乱码的问题。 以前的国外主机用的Mysql是4.x系列的,感觉还比较好,都无论GBK
- 有时候我们可能会把CSV中的数据导入到某个数据库的表中,比如做报表分析的时候。对于这个问题,我想一点也难不倒程序人员吧!但是要是SQL Se
- 假设有如下目录结构:-- dir0| file1.py| file2.py| dir3| file3.py| dir4| file4.pyd
- python数组和列表的区别列表和数组的定义列表用于顺序存储结构。它可以方便、高效的的添加删除元素,并且列表中的元素可以是多种类型。数组是一
- 本文实例为大家分享了JavaScript实现淘宝网图片的局部放大的具体代码,供大家参考,具体内容如下要实现的效果如下:<!DOCTYP
- 前言今天呢,笔者想和大家来聊聊python+pytest接口自动化测试的参数关联,笔者这边就不多说废话了,咱们直接进入正题。一、什么是参数关
- createTrackbar是Opencv中的API,其可在显示图像的窗口中快速创建一个滑动控件,用于手动调节阈值,具有非常直观的效果。具体
- 和我之前写的通过导入jdbc驱动jar包来连接mysql数据库而言,用mybatis来说可以有很多好处呀,首先mybatis,就是对jdbc
- 先说结论model.state_dict()是浅拷贝,返回的参数仍然会随着网络的训练而变化。应该使用deepcopy(model.state
- 信号与槽介绍信号(Signal)与槽(Slot)是Qt中的核心机制,也是在PyQt编程中对象之间进行通信的机制。PyQt的窗口控件类有很多内
- 本文实例讲述了flask框架自定义过滤器。分享给大家供大家参考,具体如下:除了一些内置的join length safe等过滤器外, fla
- 一、Excel环境配置 服务器端的环境配置从参考资料上看,微软系列的配置应该都行,即:1.Win9x+PWS+Office2.Wi
- 本文实例讲述了django框架模板中定义变量的方法。分享给大家供大家参考,具体如下:总有一些情况,你会想在django template中设
- 迭代器迭代器协议对象必须提供一个next方法,执行该方法要么返回迭代中的下一项,要么返回一个异常来终止本次迭代。(只能往前走,不能往后退!)
- ISSET();——适合于检测是否存在这个参数。 定义和作用范围:用于测试一个变量是否具有值(包括0,FALSE,或者一个空字串,但不能是N
- 前提条件,两台服务器都安装了mysql相同的版本,数据库名也一样,最好数据都是尽量的差不多。mysql服务器端 192.168.0.1: 新
- 方法一、简单安装(通过yum)1.安装epel-releaserpm -ivh http://dl.fedoraproject.
- phpinfo() 功能描述:输出 PHP 环境信息以及相关的模块、WEB 环境等信息。 危险等级:中 passthru() 功能描述:允许