溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了JS中的算法與數據結構之集合(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 一文，相信會有不錯的收獲~
感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.jb51.net/code/HtmlJsRun測試上述代碼運行效果。
更多關于JavaScript相關內容可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
