愉快的假期告一段落,繼續(xù)我們的學(xué)習(xí)~
集合(Set)
同數(shù)學(xué)中所學(xué)的一樣了赵,集合(Set)是由一組無(wú)序但彼此之間又有一定關(guān)系性的成員構(gòu)成树肃,每個(gè)成員在集合中只能出現(xiàn)一次,不同于我們之前說(shuō)的字典娄徊,鏈表之類的闽颇,它是一種包含了不同元素的數(shù)據(jù)結(jié)構(gòu)(集合中的元素稱為成員),從其定義中我們可以看出它具有兩個(gè)很重要的特征:首先寄锐,集合中的成員是無(wú)序的兵多,其次,集合中的成員是不相同的橄仆,即集合中不存在相同的成員剩膘。
實(shí)際上,很多編程語(yǔ)言中盆顾,集合并不是一種數(shù)據(jù)類型怠褐,但是如果你需要?jiǎng)?chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)用來(lái)保存一些獨(dú)一無(wú)二的元素時(shí),集合就變得很有用了您宪,接下來(lái)我們一起來(lái)看看JS中如何實(shí)現(xiàn)一個(gè)集合奈懒。
集合的定義
我們要實(shí)現(xiàn)一個(gè)集合具温,首先要對(duì)其一些定義做了解
- 不包含任何成員的集合稱為空集,包含一切可能成員的集合稱為全集筐赔。
- 如果兩個(gè)集合里的成員都完全相同铣猩,則稱兩個(gè)集合相等。
- 如果一個(gè)集合所有成員都包含于另一個(gè)集合茴丰,則前一集合稱為后一集合的一個(gè)子集达皿。
集合的操作
通常來(lái)說(shuō),集合的基本操作有以下三種:
- 并集:將兩個(gè)集合中的成員進(jìn)行合并贿肩,得到一個(gè)新的集合
- 交集:將兩個(gè)集合中共同存在的成員組成的一個(gè)新的集合
- 補(bǔ)集:屬于一個(gè)集合而不屬于另一個(gè)集合的成員組成的新的集合
集合的實(shí)現(xiàn)
集合(Set)的實(shí)現(xiàn)我們這里基于數(shù)組峦椰,用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù),根據(jù)我們之前學(xué)習(xí)的以及上面提到的一些方法汰规,我們可以將集合的構(gòu)造函數(shù)定義如下(為了區(qū)別ES6的 set 類型汤功,我們這里選擇用 MySet 命名):
//構(gòu)造函數(shù)
function MySet () {
this.dataStore = []; // 數(shù)據(jù)存儲(chǔ)
this.add = add; // 添加成員
this.remove = remove; // 刪除成員
this.size = size; // 集合元素個(gè)數(shù)
this.union = union; // 集合求并集
this.intersect = intersect; // 集合求交集
this.subset = subset; // 判斷一個(gè)集合是否是另一集合的子集
this.difference = difference; // 集合求補(bǔ)集
this.contains = contains; // 判斷某成員是否屬于該集合
this.show = show; // 顯示當(dāng)前集合
}
我們第一個(gè)要實(shí)現(xiàn)的方法就是向集合中添加一個(gè)成員,即 add 方法
add:向集合中添加一個(gè)成員
//添加元素
function add (data) {
//判斷元素是否存在集合當(dāng)中
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;
}
}
我們之前提到溜哮,集合中的元素是獨(dú)一無(wú)二的滔金,因此,我們?cè)趯?shù)據(jù)存儲(chǔ)到數(shù)組之前茂嗓,首先就是要確保該集合不存在該數(shù)據(jù)餐茵,因此,我們先用 indexOf 方法檢查新加入的元素是否存在述吸,如果找到了就返回該成員在數(shù)組中的位置忿族;否則,就返回 -1 蝌矛,那么對(duì)應(yīng)的 add 方法就可以定義返回布爾值道批,添加成功我們返回 true , 否則返回 false 入撒,這樣就可以明確告訴我們是否正確的插入了一個(gè)元素隆豹。
remove:刪除集合中某個(gè)成員
//刪除元素
function remove (data) {
//判斷元素是否存在集合當(dāng)中
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;
}
}
這里,我們順理成章的實(shí)現(xiàn)了刪除方法衅金,它跟 add 方法很類似噪伊,首先要檢查待刪除元素是否存在于數(shù)組中,如果存在氮唯,我們調(diào)用數(shù)組的 splice() 方法刪除該元素并返回 true ,否則姨伟,直接返回 false 惩琉,表示集合中不存在該元素。
現(xiàn)在夺荒,我們可以完成集合的添加和刪除瞒渠,要測(cè)試這些方法之前良蒸,我們首先得定義 show 方法,該方法用來(lái)顯示集合中的成員伍玖,該方法的實(shí)現(xiàn)很簡(jiǎn)答嫩痰,只需返回我們定義的數(shù)組即可:
show:顯示集合中的成員
// 顯示集合成員
function show(){
console.log(this.dataStore);
return this.dataStore;
}
接著,我們這會(huì)來(lái)測(cè)試一下:
var fruits = new MySet();
// 添加成員
fruits.add('Apple');
fruits.add('Banana');
fruits.add('Pear');
fruits.show(); // ["Apple", "Banana", "Pear"]
// 添加重復(fù)成員
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
嗯窍箍,一切正常串纺,我們可以來(lái)實(shí)現(xiàn)集合的一些高級(jí)操作了,我們先來(lái)看看 union (并集)的實(shí)現(xiàn)椰棘。
union:求集合并集
求集合的并集纺棺,就是要將兩個(gè)集合合并成一個(gè),并除去重復(fù)的元素邪狞,我們實(shí)現(xiàn)思路就是將第一個(gè)集合成員放到一個(gè)臨時(shí)集合中祷蝌,判斷第二個(gè)集合的成員是否也屬于第一個(gè)集合,如果為真帆卓,代表為重復(fù)元素巨朦,我們直接跳過(guò)該成員,否則將該成員加入臨時(shí)集合剑令,最后返回該集合即可罪郊;
那么,問(wèn)題來(lái)了尚洽,我們要如何判斷一個(gè)成員是否存在于該集合中悔橄?因此,我們需要一個(gè)輔助方法 contains()腺毫,它的實(shí)現(xiàn)也非常簡(jiǎn)單癣疟,直接用 indexOf 判斷即可
//判斷元素是否屬于該集合
function contains (data) {
if( this.dataStore.indexOf(data) > -1 ){
return true;
}else{
return false;
}
}
現(xiàn)在,我們可以定義 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"]
成功了!我們可以來(lái)看看求集合的交集了急黎。
intersect:求集合的交集
有了上面求并集的思路扎狱,那么交集的定義來(lái)說(shuō)也相對(duì)簡(jiǎn)單,思路就是發(fā)現(xiàn)第一個(gè)集合的成員也屬于第二個(gè)集合時(shí)勃教,就將該成員加入到新的集合淤击,最后返回新的集合即可;
//求集合的交集
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;
}
我們還是利用上面的兩個(gè)集合接著求其交集:
var intersect = fruits1.intersect( fruits2 );
intersect.show(); // ["Banana", "Pear"]
下一個(gè)定義的操作是 subset 故源;
subset:判斷集合是否是另一集合的子集
該方法首先要確定 該集合的長(zhǎng)度是否小于待比較的集合污抬。如果該集合比待比較集合還要大,那么肯定不是待比較集合的一個(gè)子集。只要當(dāng)印机,待比較集合比較大時(shí)矢腻,才去判斷集合類的成員是否都屬于待比較集合,如果有一個(gè)不是射赛,直接返回 false 多柑, 只有當(dāng)所有元素都屬于待比較集合的時(shí)候,我們才能說(shuō)該集合是待比較集合的一個(gè)子集楣责,該方法才會(huì)返回 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 方法帐偎,它的定義如下:
//返回集合長(zhǎng)度
function size () {
return this.dataStore.length;
}
我們保留上面的 fruits1 和 fruits2 , 新建一個(gè) fruits3 來(lái)演示 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
看起來(lái)一切都很順利蛔屹,我們只剩最后一個(gè) difference 方法削樊,該方法返回一個(gè)新集合,該集合是由屬于第一個(gè)集合而不屬于第二個(gè)集合的成員組成的兔毒。
difference:補(bǔ)集
有了交集的思路漫贞,補(bǔ)集的實(shí)現(xiàn)就顯得很自然了。
//補(bǔ)集
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;
}
我們測(cè)試一下:
fruits1.difference(fruits2).show(); // ['Apple']
fruits1.difference(fruits3).show(); // []
fruits2.difference(fruits1).show(); // ["Grape", "Orange"]
ok育叁,到現(xiàn)在迅脐,我們完成了一個(gè)完整的 set 集合,是不是很棒豪嗽!
本篇介紹的集合和 ES6 的集合略微有點(diǎn)差別谴蔑,ES6 提供的 Set 數(shù)據(jù)結(jié)構(gòu),有很多現(xiàn)成的方法可以直接調(diào)用龟梦,很是方法隐锭,不是很了解的小伙伴可以參考我之前的一篇博文,關(guān)于ES6中Symbol 计贰、Set 和 Map 一文钦睡,相信會(huì)有不錯(cuò)的收獲~