JavaScript數據結構-集合

介紹

　　集合是由一組無序且唯一(即不能重覆)的項組成的。比如由一個大於等於0的整數組成的集合：N={0,1,2,3,4,5,6,...}。

還有一個概念叫空集。用'{}'表示。

創建集合

我們使用對象來表示集合。

1 function Set() { 
2     let items = {}; 
3 }

常見方法

add(value)：向集合添加一個新的項。
delete(value)：從集合移除一個值。
has(value)：如果值在集合中，返回true，否則返回false。  clear()：移除集合中的所有項。
size()：返回集合所包含元素的數量。與數組的length屬性類似。
values()：返回一個包含集合中所有值的數組。

has方法

1 this.has = function(value){ 
2     return value in items; 
3 };
4 
5 ----------------或者-----------------
6 
7 this.has = function(value){ 
8  return items.hasOwnProperty(value); 
9 };

add方法

1 this.add = function (value) {
2     if (!this.has(value)) {
3         items[value] = value; 
4         return true;
5     }
6     return false;
7 };

remove方法

 1 this.remove = function (value) {
 2     if (this.has(value)) {
 3         delete items[value];
 4         return true;
 5     }
 6     return false;
 7 };
 8 
 9 this.clear = function(){ 
10     items = {};
11 };

size方法

1 this.size = function(){ 
2     return Object.keys(items).length;
3 };

values方法

values方法也應用了相同的邏輯，提取items對象的所有屬性，以數組的形式返回

1 this.values = function () {
2     let values = [];
3     for (let i = 0, keys = Object.keys(items); i < keys.length; i++) {
4         values.push(items[keys[i]]);
5     }
6     return values;
7 };

使用set類

 1 let set = new Set(); 
 2 set.add(1); 
 3 console.log(set.values()); //輸出["1"] 
 4 console.log(set.has(1)); //輸出true 
 5 console.log(set.size()); //輸出1 
 6 set.add(2); 
 7 console.log(set.values()); //輸出["1", "2"] 
 8 console.log(set.has(2)); //true 
 9 console.log(set.size()); //2 
10 set.remove(1); 
11 console.log(set.values()); //輸出["2"] 
12 set.remove(2); 
13 console.log(set.values()); //輸出[]

集合的一些操作

高中數學課本里也有。

並集：對於給定的兩個集合，返回一個包含兩個集合中所有元素的新集合。
交集：對於給定的兩個集合，返回一個包含兩個集合中共有元素的新集合。
差集：對於給定的兩個集合，返回一個包含所有存在於第一個集合且不存在於第二個集合的元素的新集合。
子集：驗證一個給定集合是否是另一集合的子集。

並集

並集的數學概念是集合A和集合B的並集，表示為：A∪B，集合定義如下：

A∪B = { x | x ∈ A∨x ∈ B }

代碼實現Set類的union方法

 1 this.union = function (otherSet) {
 2     let unionSet = new Set(); //定義兩個集合的並集 
 3     let values = this.values();
 4     for (let i = 0; i < values.length; i++) { //獲取第一個集合的集都添加到並集中
 5         unionSet.add(values[i]);
 6     }
 7     values = otherSet.values(); 
 8     for (let i = 0; i < values.length; i++) { //獲取第二個集合的集都添加到並集中
 9         unionSet.add(values[i]);
10     }
11     return unionSet;
12 };

測試代碼

 1 let setA = new Set(); 
 2 setA.add(1); 
 3 setA.add(2); 
 4 setA.add(3); 
 5 let setB = new Set(); 
 6 setB.add(3); 
 7 setB.add(4); 
 8 setB.add(5); 
 9 setB.add(6); 
10 let unionAB = setA.union(setB); 
11 console.log(unionAB.values());
12 
13 //結果
14 ["1", "2", "3", "4", "5", "6"]

交集

交集的數學概念是集合A和集合B的交集，表示為：A∩B，集合的定義如下：

A∩B = { x | x ∈ A∧x ∈ B }

代碼實現Set類的intersection方法

 1 this.intersection = function (otherSet) {
 2     let intersectionSet = new Set(); //創建交集返回共有的元素 
 3     let values = this.values();
 4     for (let i = 0; i < values.length; i++) { //便利當前Set類所有制
 5         if (otherSet.has(values[i])) { //驗證是否存在otherSet中
 6             intersectionSet.add(values[i]); //存在則添加
 7         }
 8     }
 9     return intersectionSet;
10 }

測試代碼

 1 let setA = new Set(); 
 2 setA.add(1); 
 3 setA.add(2); 
 4 setA.add(3); 
 5 let setB = new Set(); 
 6 setB.add(2); 
 7 setB.add(3); 
 8 setB.add(4); 
 9 let intersectionAB = setA.intersection(setB); 
10 console.log(intersectionAB.values());
11 
12 //結果
13 ["2", "3"] 

差集

差集的數學概念是集合A和集合B的差集，表示為：A-B，集合的定義如下：

A-B = { x | x ∈ A ∧ x B }

代碼實現Set類的difference方法

 1 this.difference = function (otherSet) {
 2     let differenceSet = new Set(); //創建差集的集合 
 3     let values = this.values();
 4     for (let i = 0; i < values.length; i++) { //遍歷當前Set類所有值
 5         if (!otherSet.has(values[i])) { //存在A但不存在與B的值
 6             differenceSet.add(values[i]); //添加到集合中
 7         }
 8     }
 9     return differenceSet;
10 };

測試代碼

 1 let setA = new Set(); 
 2 setA.add(1); 
 3 setA.add(2); 
 4 setA.add(3); 
 5 let setB = new Set(); 
 6 setB.add(2); 
 7 setB.add(3); 
 8 setB.add(4); 
 9 let differenceAB = setA.difference(setB); 
10 console.log(differenceAB.values());
11 
12 //結果
13 ["1"]

子集

子集的數學概念是集合A是集合B的子集，表示為：A⊆B ，集合的定義如下：

∀x { x ∈ A → x ∈ B }

代碼實現Set類的subset方法

 1 this.subset = function (otherSet) {
 2     if (this.size() > otherSet.size()) { //當前set類的大小必須要大於otherSet實例大小
 3         return false;
 4     } else {
 5         let values = this.values();
 6         for (let i = 0; i < values.length; i++) { //遍歷Set類所有元素
 7             if (!otherSet.has(values[i])) { //驗證元素是否頁都存在與otherSet中
 8                 return false; //有不存在的，為false
 9             }
10         }
11         return true; //都存在則為true
12     }
13 };

測試代碼

 1 let setA = new Set(); 
 2 setA.add(1);
 3 setA.add(2); 
 4 let setB = new Set(); 
 5 setB.add(1); 
 6 setB.add(2); 
 7 setB.add(3); 
 8 let setC = new Set(); 
 9 setC.add(2); 
10 setC.add(3); 
11 setC.add(4); 
12 console.log(setA.subset(setB)); 
13 console.log(setA.subset(setC));
14 
15 //結果
16 setA是setB的子集（因此輸出為true），然而setA不是setC的子集（setC只包含了setA中的2，而不包含1），因此輸出為false。

 來源：JavaScript數據結構與演算法

 總結：along