JavaScript的数据结构-集合 | 写前端技术知识

前言

❤️笔芯❤️~

数组，栈，队列，链表

集合

集合是由一组无序且唯一的项组成的，（不能重复），可以理解为集合是一个既没有重复元素，也没有顺序概念的数组。

并集，交集，差集

// 使用ES6中的Set类

function Set() {
 let items = {};
}

add(value)，向集合添加一个新的项
delete(value)，从集合移除一个值
has(value)，如果值在集合中，返回true，否则返回false
clear()，移除集合中的所有项
size()，返回集合所包含元素的数量
values()，返回一个包含集合中所有值的数组

has(value)方法

1
2
3

this.has = function(value) {
 return value in items;
};

1
2
3

this.has = function(value) {
 return items.hasOwnProperty(value);
};

实现add方法：

this.add = function(value) {
 if(!this.has(value)) {
  // 如果不存在，就把value添加到集合中
  items[value] = value;
  return true;
 }
 return false;
};

添加一个值的时候，把它同时作为键和值保存，因为这样有利于查找这个值。

实现remove方法：

this.remove = function(value) {
 if(this.has(value)) {
 // 如果存在，就从集合中移除value
  delete items[value];
  return true;
 }
 return false;
};

使用Set类的示例代码：

1
2
3

let set = new Set();
set.add(1);
set.add(2);

移除集合中的所有值：

// clear方法
this.clear = function() {
 items = {}
};

size方法

使用一个length变量，每当使用add或remove方法时控制它，像使用LinkedList类一样
示例：

this.size = function() {
// 返回一个包含给定对象所有属性的数组
 return Object.keys(items).length;
};

示例：

this.sizeLegacy = function() {
 let count = 0;
 for(let key in items) {
  // 遍历items对象的所有属性
  if(items.hasOwnProperty(key))
  // 检查它们是否是对象自身的属性
  // 如果是，递增count变量的值
  ++count;
 }
 // 最后在方法结束时返回这个数字
 return count;
};

values方法，提取items对象的所有属性，以数组的形式返回

this.values = function() {
 let values = [];
 
 for(let i=0, keys = Object.keys(items); i < keys.length; i++) {
  values.push(items[keys[i]]);
 }
 return values;
};

this.valuesLegacy = function() {
 let values = [];
 
 for(let key in items) {
 // 遍历items对象的所有属性
  if(items.hasOwnProperty(key)) {
   values.push(item[key]);
  }
 }
 return values;
};

使用Set类

let set = new Set(0;
set.add(1);
console.log(set.values()); // 数组类型
console.log(set.has(1)); // true
console.log(set.size()); // 1
...

集合操作

给定的两个集合

并集，返回一个包含两个集合中所有元素的新集合
交集，返回一个包含两个集合中共有元素的新集合
差集，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合
子集，验证一个给定集合是否是另一集合的子集

并集

this.union = function(otherSet) {
// 需要创建一个新的集合，代表两个集合的并集
 let unionSet = new Set();
 // 获取第一个集合所有的值，遍历并全部添加到代表并集的集合中
 let values = this.values();
 
 for(let i=0; i<values.length; i++) {
  unionSet.add(values[i]);
 }
 values = otherSet.values();
 // 第二个集合做同样的事
 for(let i=0; i<values.length; i++) {
  unionSet.add(values[i]);
 }
 return unionSet;
}

交集

this.intersection = function(otherSet) {
// 创建一个新的Set实例，这样就能用它返回共有的元素
 let intersectionSet = new Set();
 
 let values = this.vlues();
 // 遍历当前Set实例所有的值
 for (let i=0; i<values.length; i++) {
  if(otherSet.has(values[i])){
   intersectionSet.add(values[i]);
  }
 }
 return intersectionSet;
}

差集

表示A-B,x元素存在于A中，且x不存在于B中。

this.difference = function(otherSet){
// 得到所有同时存在于两个集合中的值
 let differenceSet = new Set();
 
 let values = this.values();
 // 
 for(let i=0; i<values.length; i++){
 // 
  if(!otherSet.has(values[i])){
  // 会得到所有存在于集合A但不存在于B的值
   differenceSet.add(values[i]);
  }
 }
 return differenceSet
};

子集

集合A是集合B的子集：

this.subset = function(otherSet){ 
 if (this.size() > otherSet.size()){ 
 //需要验证的是当前Set实例的大小
 return false; 
 // 如果当前实例中的元素比otherSet实例更多，它就不是一个子集
 } else { 
 let values = this.values(); 
 for (let i=0; i<values.length; i++){ 
 //要遍历集合中的所有元素
 if (!otherSet.has(values[i])){ 
 //验证这些元素也存在于otherSet中 
 return false; 
 //如果有任何元素不存在于otherSet中，就意味着它不是一个子集，返回false
 } 
 } 
 return true; 
 //如果所有元素都存在于otherSet中，那么就返回true
 } 
};

Set类

let set = new Set(); 
set.add(1); 
// ES6的Set的values方法返回Iterator
// 而不是值构成的数组
console.log(set.values()); // 输出@Iterator 
console.log(set.has(1)); // 输出true 
console.log(set.size); // 输出1

ES6 Set 类

let setA = new Set(); 
setA.add(1); 
setA.add(2); 
setA.add(3); 

let setB = new Set(); 
setB.add(2); 
setB.add(3); 
setB.add(4);

并集

let unionAb = new Set(); 
//创建一个新的集合，用来添加两个集合中所有的元素
//迭代这两个集合 
for (let x of setA) unionAb.add(x); 

for (let x of setB) unionAb.add(x);

交集

// 创建一个辅助函数
// 来生成包含setA和setB都有的元素的新集合
let intersection = function(setA, setB) { 

 let intersectionSet = new Set(); 
 
 for (let x of setA) { 
 if (setB.has(x)) {  
 intersectionSet.add(x); 
 } 
 
 } 
 return intersectionSet; 
}; 
let intersectionAB = intersection(setA, setB);

简单语法：

1	intersectionAb = new Set([x for (x of setA) if (setB.has(x))]);

差集

let difference = function(setA, setB) { 

 let differenceSet = new Set(); 
 
 for (let x of setA) { 
   if (!setB.has(x)) {
    // 差集中只添加setA有而setB没有的元素
   	differenceSet.add(x); 
   } 
 } 
 
 return differenceSet; 
}; 
let differenceAB = difference(setA, setB);