前端算法系列之三：数据结构数据集合

本文主要是介绍前端算法系列之三：数据结构数据集合，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在之前已经介绍了数据结构：栈、队列、链表，并且知道了这些数据结构的特性和实现方式，以及如何在实际的开发过程中通过这些数据结构来巧妙的解决一些实际问题，包括怎么去实现一个四则运算、怎么去实现最优取币方式等等；这篇接着介绍数据结构：集合、字典散列；
前端算法系列之二：数据结构链表、双向链表、闭环链表、有序链表
前端算法系列之一：时间复杂度、空间复杂度以及数据结构栈、队列的实现

一、集合

集合是由一组无序且唯一（即不能重复）的项组成的。该数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。注意集合的特性：1、无序；2、唯一；这和我们数学概念的集合大体是一致的，在数学中我们用大括号来表示集合，把满足条件的元素归类于放在一块形成了集合，例如把大于等于0的整数放入集合N = {0,1,2,3,4,5,6...}；集合也可能是没有任何元素的，比如把没写过bug的程序猿归类在一个集合那结果就是N = {};那怎么去实现一个集合呢？
在es6以后JavaScript有一个原生支持集合的Set，这个就是一个集合，那我们在es6以前的怎么去实现一个集合呢？我们可以模仿es6中Set相关来实现；
定义相关api:
add(ele):向集合中添加一个元素；
delete(ele): 删除集合中一个元素；
has(ele): 集合中是否包含某个元素
clear(): 清空集合
size(): 计算集合的大小
values(): 获取集合的所有元素，返回一个数组

class MySet {
    constructor() {
     this.items = {};
    }
    add(element) {
     const key = this.keyToString(element);
     if(!this.has(element)) {
      this.items[key] = element;
     return true;
     }
     return false;
    }
    delete(element) {
     if(this.has(element)) {
      delete this.items[this.keyToString(element)];
     return true;
     }
     return false;
    }
    keyToString(str) {
     return keyToString(str);
    }
    has(element) {
     return Object.prototype.hasOwnProperty.call(this.items, this.keyToString(element));
    }
    clear() {
     this.items = {};
     return true;
    }
    size() {
     return Object.keys(this.items).length;
    }
    values() {
     return Object.values(this.items);
    }
}

注：上面代码中有一个将键转换为字符串的函数keyToString，这是为了当添加的元素是对象或者其他特殊类型时候直接作为对象的键可能会引发错误；

function keyToString(str) {
 if (str === null) {
  return 'null';
 } else if (str === undefined) {
  return 'undefined';
 } else if(typeof str === 'function') {
  return str.toString();
 }
 return JSON.stringify(str)
}

实例测试：

const myset = new MySet();
myset.add(1); // true
myset.add(2); // true
myset.add(3); // true
myset.add({a:1}); // true
myset.add({b:1}); // true
console.log(myset.has(2)); // true
console.log(myset.has({a:1})); // true
console.log(myset.has({a:2})); // false
console.log(myset.size());// 5
console.log(myset.values());// [1, 2, 3, {a:1}, {b:1}]
myset.delete({a:1});
console.log(myset.values());// [1, 2, 3, {b:1}]
console.log(myset.has({a:1})); // false
console.log(myset.size(); // 4
myset.clear();
console.log(myset.values());// []
console.log(myset.size(); // 0

通过上面的代码实现集合还是比较容易理解的，就是对一个对象键值对的增删改查之类的操作，没有涉及到什么复杂的运用，但我们知道集合的应用远远不止是这样；集合的应用其实在于集合间的操作，比如我们查找数据的时候，从两个不同的表里面查出了两个集合的数据，我们可以通过集合的运算来实现集合的并集、交集、差集等操作，从而得到满足需求的数据；

1、集合的并集

在数学概念中两个集合A\B的并集是在元素存在于A或者存在于B中，用数学表达式表达如下：
A∪B = {x | x ∈ A ∨ x ∈ B}；

// 并集
union(otherSet) {
 const unionSet = new MySet();
 const values = this.values();
 const otherSetValues = otherSet.values();
 for (let i = 0; i < values.length; i++) {
  unionSet.add(values[i]);
 }
 for (let i = 0; i < otherSetValues.length; i++) {
  unionSet.add(otherSetValues[i]);
 }
 return unionSet;
}

测试并集：

const setA = new MySet();
setA.add(1);
setA.add(2);
setA.add(3);

const setB = new MySet();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);
const unionSet = setA.union(setB);
unionSet.values(); // [1,2,3,4,5,6]

2、交集

A∩B = {x | x ∈ A ∧ x ∈ B}意思是x（元素）存在于A中，且x存在于B中。下图展示了交集运算。

// 交集
intersection(otherSet) {
 const intersectionSet = new MySet();
 const values = this.values();
 const otherSetValues = otherSet.values();
 const lenSelf = values.length;
 const lenOther = otherSetValues.length;
 if (lenSelf < lenOther) {
  for (let i = 0; i < lenSelf; i++) {
   if(otherSet.has(values[i])){
    intersectionSet.add(values[i])
   }
  }
 } else {
  for (let i = 0; i < lenOther; i++) {
   if(this.has(otherSetValues[i])){
    intersectionSet.add(otherSetValues[i])
   }
  }
 };
 return intersectionSet;
}

测试代码：

const setA = new MySet();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new MySet();
setB.add(2);
setB.add(3);
setB.add(4);
const interse = setA.intersection(setB);
console.log(interse.values()); // [2,3]

3、差集

集合A和集合B的差集表示为A - B，定义如下。A-B= {x|x∈A∧x∉B}意思是x（元素）存在于A中，且x不存在于B中。下图展示了集合A和集合B的差集运算。

实现代码：

// 差集
difference(otherSet) {
 const differenceSet = new MySet();
 this.values().forEach(v => {
  if(!otherSet.has(v)) {
   differenceSet.add(v);
 }
 });
 return differenceSet;
}

测试代码：

const setA = new MySet();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new MySet();
setB.add(2);
setB.add(3);
setB.add(4);
const differenceSet = setA.difference(setB);
console.log(differenceSet.values()); // [1]

4、子集

子集表示如下。
A ⊆ B该集合定义如下。{x | ∀x ∈ A ⇒ x ∈ B}意思是集合A中的每一个x（元素），也需要存在于集合B中。下图展示了集合A是集合B的子集。

实现方式：

isChildSet(otherSet) {
 if (this.size() > otherSet.size()) {
  return false;
 }
 let res = false;
 otherSet.values().every(v => {
  if (!otherSet.has(v)) {
   res = false;
 return false
 }
  return true;
 })
 return res;
}

下面咱们来验证一下测试一下子集的验证

const setA = new MySet();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new MySet();
setB.add(1);
setB.add(2);
setB.add(3);
setB.add(4);
const setChild = setA.isChildSet(setB);
console.log(setChild.values()); // true

小结

es6新增了Set类作为JavaScript API的一部分。我们上面是实现了自己的集合，现在来看一下es6原生的set有哪些不同；

const setA = new Set();
setA.add(1);
setA.add(2);
console.log(setA.size); // 2
setA.delete(2);// true
console.log(setA.values());//SetIterator

原生api的Set对于集合长度有一个属性size，通过属性可以拿到集合的长度，我们实现的时候也可以把size方法转变成属性值的，此外原生values方法返回的不是直接的一个数组，而是一个Set迭代器SetIterator可进行迭代访问；原生Set没有提供集合的交集、并集、差集、子集的方法，不过也可以进行扩展实现，而且运用es6的一些新型的语法特性以及api能够比较简单的实现，这里不再赘述；

想了解更多请看：源码
或者搜索公众号：非著名bug认证师

这篇关于前端算法系列之三：数据结构数据集合的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！