乐趣区

关于javascript:前端算法系列之三数据结构数据集合

jiezi

在之前曾经介绍了数据结构：栈、队列、链表，并且晓得了这些数据结构的个性和实现形式，以及如何在理论的开发过程中通过这些数据结构来奇妙的解决一些理论问题，包含怎么去实现一个四则运算、怎么去实现最优取币形式等等；这篇接着介绍数据结构：汇合、字典散列；
前端算法系列之二：数据结构链表、双向链表、闭环链表、有序链表
前端算法系列之一：工夫复杂度、空间复杂度以及数据结构栈、队列的实现

一、汇合

汇合是由一组无序且惟一（即不能反复）的项组成的。该数据结构应用了与无限汇合雷同的数学概念，但利用在计算机科学的数据结构中。留神汇合的个性：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 认证师

退出移动版