JavaScript資料結構-集合

語雀入口

　https://www.yuque.com/along-n3gko/ezt5z9

介紹

　　集合是由一組無序且唯一(即不能重復)的項組成的，比如由一個大于等于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

標籤：JavaScript

上一篇：Vular開發手記#1：設計并實作一個拼插式應用程式框架

下一篇：JavaScript連載9-三目運算子、綜合復習