前者学数据结构之集合

前方的话

  本文将详细介绍集合,这是一种不允许值重复的依次数据结构

 

数据结构

  集合是由一组无序且唯一(即不可能重新)的项组成的。这么些数据结构使用了与有限集合相同的数学概念,但选拔在微机科学的数据结构中。

  在深深学习集合的电脑科学落实往日,我们先看看它的数学概念。在数学中,集合是一组不同的靶子(的集)。比如说,一个由高于或等于0的平头组成的自然数集合:N={0,1,2,3,4,5,6,…}。集合中的对象列表用“{}”(大括号)包围。

  还有一个定义叫空集。空集就是不含有其他因素的集结。比如24和29之内的素数集合。由于24和29期间没有素数(除了1和自身,没有任何正因数的大于1的自然数),那些集合就是空集。空集用“{}”表示

  也可以把集合想象成一个既没有重新元素,也一向不各样概念的数组。在数学中,集合也有并集、交集、差集等基本操作。下边将介绍这多少个操作

 

创建集合

  下边要实现的类就是以ECMAScript6中Set类的兑现为底蕴的。

  以下是Set类的骨架:

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

  有一个非常重大的细节,我们应用对象而不是数组来代表集合(items)。但也足以用数组实现。
同时,JavaScript的对象不允许一个键指向五个不等的性质,也准保了集合里的要素都是绝无仅有的

  接下去,需要阐明一些会聚可用的方法(我们会尝试模拟与ECMAScript
6落实均等的Set类)

add(value):向集合添加一个新的项。
remove(value):从集合移除一个值。
has(value):如果值在集合中,返回true,否则返回false。
clear():移除集合中的所有项。
size():返回集合所包含元素的数量。与数组的length属性类似。
values():返回一个包含集合中所有值的数组。

【has】

  首先要落实的是has(value)方法。这是因为它会被add、remove等任何格局调用。

  既然我们运用对象来囤积集合的值,就可以用JavaScript的in操作符来表明给定的值是否是items对象的性能

  上面看看它的兑现:

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

  但这个方法还有更好的兑现形式,所有JavaScript对象都有hasOwnProperty方法。这个办法再次回到一个标志对象是不是具有一定属性的布尔值。代码如下:

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

【add】

  接下去要落实add方法:

this.add = function(value){ 
  if (!this.has(value)){
    items[value] = value; //{1} 
    return true;
  }
  return false;
};

  对于给定的value,可以检查它是否留存于聚集中。假诺不存在,就把value添加到聚集中(行{1}),再次来到true,表示添加了这一个值。假设集合中已经有这些值,就回来false,表示尚无添加它。

  [注意]累加一个值的时候,把它同时作为键和值保存,因为这样方便查找这多少个值

【remove】

  在remove方法中,大家会注明给定的value是否留存于聚集中。假如存在,就从集合中移除value(行{2}),再次回到true,表示值被移除;否则再次回到false。

  下边来落实remove方法:

this.remove = function(value){ 
  if (this.has(value)){
    delete items[value]; //{2}
    return true;
  }
  return false;
};

  既然用对象来囤积集合的items对象,就可以省略地运用delete操作符从items对象中移除属性(行{2})

  使用Set类的演示代码如下:

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

  在推行以上代码之后,在控制台(console.log)输出items
变量,Chrome就会输出如下内容:

 Object {1: 1, 2: 2}

  能够见到,这是一个有两个特性的对象。属性名就是加上到聚集的值,同时它也是属性值

【clear】

  虽然想移除集合中的所有值,可以用clear方法:

  要重置items对象,需要做的只是把一个空对象重新赋值给它(行{3})。大家也足以迭代集合,用remove方法依次移除所有的值,但既然有更简明的措施,这样做就太难为了

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

【size】

  size方法(重临集合中有稍许项)方法有两种实现模式。
第一种艺术是运用一个length变量,每当使用add或remove方法时控制它;第二种格局,使用JavaScript内建的Object类的一个内建函数(ECMAScript
5以上版本):

  JavaScript的Object类有一个keys方法,它回到一个含有给定对象具备属性的数组。在这种气象下,可以动用这些数组的length属性(行{4})来回到items对象的习性个数。以下代码只能在现世浏览器中运行

this.size = function(){
  return Object.keys(items).length; //{4}
};

  第两种模式是手动提取items对象的每一个性质,记录属性的个数并赶回这些数字。这一个措施可以在其它浏览器上运行,和事先的代码是等价的:

  遍历items对象的持有属性(行{5}),检查它们是否是对象自我的性能(避免再度计数——
行{6})。如果是,就与日俱增count变量的值(行{7}),最后在章程停止时再次回到这个数字

  [注意]不能简单地接纳for-in语句遍历items对象的习性,递增count变量的值。
还索要动用has方法(以验证items对象具备该属性),因为对象的原型包含了额外的性能(属性既有持续自JavaScript的Object类的,也有属于对象自我,未用于数据结构的)

this.sizeLegacy = function(){ 
  var count = 0;
  for(var prop in items) { //{5}
    if(items.hasOwnProperty(prop)) //{6}
    ++count; //{7}
  }
  return count;
};

【values】

  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) { //{7}
  if(items.hasOwnProperty(key)) { //{8}
    values.push(items[key]);
  }
 }
 return values;
};

  所以,首先遍历items对象的有着属性(行{7}),把它们增长一个数组中(行{8}),并回到这几个数组。该情势类似于sizeLegacy方法,但大家抬高一个数组,而不是计量属性个数

【使用Set类】

  数据结构已经到位了,下边来试着执行一些命令,测试我们的Set类:

var set = new Set(); 
set.add(1);
console.log(set.values()); //输出["1"]
console.log(set.has(1)); //输出true
console.log(set.size()); //输出1
set.add(2);
console.log(set.values()); //输出["1", "2"]
console.log(set.has(2)); //true 
console.log(set.size()); //2
set.remove(1); 
console.log(set.values()); //输出["2"]
set.remove(2); 
console.log(set.values()); //输出[]

  现在大家有了一个和ECMAScript6中丰富接近的Set类实现

 

集合操作

  对聚集可以展开如下操作

  1、并集:对于给定的多少个汇集,再次回到一个饱含七个聚众中颇具因素的新集合

  2、交集:对于给定的几个汇聚,重临一个涵盖多少个聚众中共有元素的新集合

  3、差集:对于给定的三个会聚,重返一个含有所有存在于第一个集合且不设有于第二个汇聚的要素的新集合

  4、子集:验证一个加以集合是否是另一聚集的子集

【并集】

  并集的数学概念是集合A和B的并集,表示为A∪B,定义如下:

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

  意思是x(元素)存在于A中,或x存在于B中。下图体现了并集操作:

图片 1

  现在来促成Set类的union方法:

  首先需要创立一个新的聚合,代表多少个会聚的并集(行{1})。接下来,获取首个聚众(当前的Set类实例)所有的值(values),遍历并全体加上到代表并集的聚集中(行{2})。然后对第二个汇集做相同的事(行{3})。最后回到结果

this.union = function(otherSet){
 let unionSet = new Set(); //{1}
 let values = this.values(); //{2}
 for (let i=0; i<values.length; i++){
  unionSet.add(values[i]);
 }
 values = otherSet.values(); //{3}
 for (let i=0; i<values.length; i++){
   unionSet.add(values[i]);
 }
 return unionSet;
};

  测试一下方面的代码:

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

var setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);

var unionAB = setA.union(setB);
console.log(unionAB.values());

  输出为[“1”, “2”, “3”, “4”, “5”,
“6”]。注意元素3并且设有于AB中,它在结果的 集合中只现出三次

【交集】

  交集的数学概念是集合A和B的混杂,表示为A∩B,定义如下:

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

  意思是x(元素)存在于A中,且x存在于B中。下图显示了交集操作:

图片 2

  现在来促成Set类的intersection方法:

  intersection方法需要找到当前Set实例中,所有存在于给定Set实例中的元素。首先创立一个新的Set实例,这样就能用它回到共有的因素(行{1})。接下来,遍历当前Set实例所有的值(行{2}),验证它们是不是也存在于otherSet实例(行{3})。可以用前边实现的has方法来证实元素是否存在于Set实例中。然后,假如这个值也设有于另一个Set实例中,就将其添加到创建的intersectionSet变量中(行{4}),最终回来它。

this.intersection = function(otherSet){
 let intersectionSet = new Set(); //{1}
 let values = this.values();
 for (let i=0; i<values.length; i++){ //{2}
  if (otherSet.has(values[i])){ //{3}
    intersectionSet.add(values[i]); //{4}
  }
 }
 return intersectionSet;
}

  测试一下方面的代码:

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

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

var intersectionAB = setA.intersection(setB); 
console.log(intersectionAB.values());

  输出为[“2”, “3”],因为2和3还要设有于六个聚众中

【差集】

  差集的数学概念,集合AB的差集,表示为AB,定义如下:

图片 3

  意思是x(元素)存在于A中,且x不设有于B中。下图呈现了汇集AB的差集操作:

图片 4

  现在来兑现Set类的difference方法:

  intersection方法会得到所有同时设有于三个聚众中的值。而difference方法会拿到所有存在于集合A但不设有于B的值。由此这五个法子在实现上唯一的区分就是行{3}。只得到不设有于otherSet实例中的值,而不是也存在于其中的值。行{1}、{2}和{4}是完全相同的

this.intersection = function(otherSet){
 let intersectionSet = new Set(); //{1}
 let values = this.values();
 for (let i=0; i<values.length; i++){ //{2}
  if (!otherSet.has(values[i])){ //{3}
    intersectionSet.add(values[i]); //{4}
  }
 }
 return intersectionSet;
}

  测试一下下边的代码:

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

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

var differenceAB = setA.difference(setB); 
console.log(differenceAB.values());

  输出为[“1”],因为1是绝无仅有一个仅设有于setA的因素

【子集】

  子集的数学概念是集合A是B的子集(或集合B包含了A),表示为A⊆B,定义如下:

∀x { x ∈ A → x ∈ B }

  意思是集合A中的每一个x(元素),也亟需存在于B中。下图彰显了集合A是集合B的子集:

图片 5

  现在来实现Set类的subset方法:

  首先需要表明的是时下Set实例的分寸。尽管当前实例中的元素比otherSet实例更多,它就不是一个子集(行{1})。子集的因素个数需要小于或等于要相比的会师。

  接下去要遍历集合中的所有因素(行{2}),验证这一个要素也设有于otherSet中(行{3})。假使有此外因素不设有于otherSet中,就意味着它不是一个子集,重临false(行{4})。倘诺拥有因素都设有于otherSet中,行{4}就不会被实践,那么就赶回true(行{5})。

this.subset = function(otherSet){
 if (this.size() > otherSet.size()){ //{1}
  return false;
 } else {
  let values = this.values();
  for (let i=0; i<values.length; i++){ //{2}
    if (!otherSet.has(values[i])){ //{3}
      return false; //{4}
    }
  }
  return true; //{5}
 }
};

  检验一下地方的代码效果怎么着:

var setA = new Set(); 
setA.add(1);
setA.add(2);

var setB = new Set(); 
setB.add(1);
setB.add(2);
setB.add(3);

var setC = new Set(); 
setC.add(2);
setC.add(3);
setC.add(4);

console.log(setA.subset(setB)); 
console.log(setA.subset(setC));

  我们有两个会聚:setA是setB的子集(由此输出为true),然则setA不是setC的子集(setC
只包含了setA中的2,而不含有1),因而输出为false

【完整代码】

  关于集合的全部代码如下

function Set() {

    let items = {};

    this.add = function(value){
        if (!this.has(value)){
            items[value] = value;
            return true;
        }
        return false;
    };

    this.delete = function(value){
        if (this.has(value)){
            delete items[value];
            return true;
        }
        return false;
    };

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

    this.clear = function(){
        items = {};
    };

    /**
     * Modern browsers function
     * IE9+, FF4+, Chrome5+, Opera12+, Safari5+
     * @returns {Number}
     */
    this.size = function(){
        return Object.keys(items).length;
    };

    /**
     * cross browser compatibility - legacy browsers
     * for modern browsers use size function
     * @returns {number}
     */
    this.sizeLegacy = function(){
        let count = 0;
        for(let key in items) {
            if(items.hasOwnProperty(key))
                ++count;
        }
        return count;
    };

    /**
     * Modern browsers function
     * IE9+, FF4+, Chrome5+, Opera12+, Safari5+
     * @returns {Array}
     */
    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) {
            if(items.hasOwnProperty(key)) {
                values.push(items[key]);
            }
        }
        return values;
    };

    this.getItems = function(){
      return items;
    };

    this.union = function(otherSet){
        let unionSet = new Set(); //{1}

        let values = this.values(); //{2}
        for (let i=0; i<values.length; i++){
            unionSet.add(values[i]);
        }

        values = otherSet.values(); //{3}
        for (let i=0; i<values.length; i++){
            unionSet.add(values[i]);
        }

        return unionSet;
    };

    this.intersection = function(otherSet){
        let intersectionSet = new Set(); //{1}

        let values = this.values();
        for (let i=0; i<values.length; i++){ //{2}
            if (otherSet.has(values[i])){    //{3}
                intersectionSet.add(values[i]); //{4}
            }
        }

        return intersectionSet;
    };

    this.difference = function(otherSet){
        let differenceSet = new Set(); //{1}

        let values = this.values();
        for (let i=0; i<values.length; i++){ //{2}
            if (!otherSet.has(values[i])){    //{3}
                differenceSet.add(values[i]); //{4}
            }
        }

        return differenceSet;
    };

    this.subset = function(otherSet){

        if (this.size() > otherSet.size()){ //{1}
            return false;
        } else {
            let values = this.values();
            for (let i=0; i<values.length; i++){ //{2}
                if (!otherSet.has(values[i])){    //{3}
                    return false; //{4}
                }
            }
            return true;
        }
    };
}

【ES6】

  ES6本子的代码如下

let Set2 = (function () {

    const items = new WeakMap();

    class Set2 {

        constructor () {
            items.set(this, {});
        }

        add(value){
            if (!this.has(value)){
                let items_ = items.get(this);
                items_[value] = value;
                return true;
            }
            return false;
        }

        delete(value){
            if (this.has(value)){
                let items_ = items.get(this);
                delete items_[value];
                return true;
            }
            return false;
        }

        has(value){
            let items_ = items.get(this);
            return items_.hasOwnProperty(value);
        }

        clear(){
            items.set(this, {});
        }

        size(){
            let items_ = items.get(this);
            return Object.keys(items_).length;
        }


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

        getItems(){
            return items.get(this);
        }

        union(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;
        }

        intersection(otherSet){
            let intersectionSet = new Set();

            let values = this.values();
            for (let i=0; i<values.length; i++){
                if (otherSet.has(values[i])){
                    intersectionSet.add(values[i]);
                }
            }

            return intersectionSet;
        }

        difference(otherSet){
            let differenceSet = new Set();

            let values = this.values();
            for (let i=0; i<values.length; i++){
                if (!otherSet.has(values[i])){
                    differenceSet.add(values[i]);
                }
            }

            return differenceSet;
        };

        subset(otherSet){

            if (this.size() > otherSet.size()){
                return false;
            } else {
                let values = this.values();
                for (let i=0; i<values.length; i++){
                    if (!otherSet.has(values[i])){
                        return false;
                    }
                }
                return true;
            }
        };
    }
    return Set2;
})();

 

ES6

  ECMAScript 2015新增了Set类。大家得以基于ES6的Set开发我们的Set类

  和大家的Set不同,ES6的Set的values方法再次回到Iterator,而不是值构成的数组。另一个有别于是,我们落实的size方法再次回到set中储存的值的个数,而ES6的Set则有一个size属性

let set = new Set();
set.add(1);
console.log(set.values()); // 输出@Iterator
console.log(set.has(1)); // 输出true
console.log(set.size); // 输出1 

  可以用delete方法删除set中的元素:

set.delete(1); 

  clear方法会重置set数据结构,这跟我们兑现的功效雷同

【集合】

  我们的Set类实现了并集、交集、差集、子集等数学操作,不过ES6原生的Set并不曾这几个效用

  我们可以创制一个新的汇集,用来添加七个聚众中负有的因素(行{1})。迭代这四个会聚(行{2}、行{3}),把拥有因素都助长到并集的联谊中。代码如下:

let unionAb = new Set(); //{1}
for (let x of setA) unionAb.add(x); //{2}
for (let x of setB) unionAb.add(x); //{3} 

  模拟交集操作需要成立一个声援函数,来生成包含setA和setB都有的元素的新集合(行
{1})。代码如下:

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

  交集能够用更简明的语法实现,代码如下:

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

  这和intersection函数的效用完全一样

  交集操作创设的成团包含setA和setB都有的元素,差集操作创设的集纳包含的则是setA有
而setB没有的元素。看上边的代码:

let difference = function(setA, setB) {
 let differenceSet = new Set();
 for (let x of setA) {
     if (!setB.has(x)) { //{1}
         differenceSet.add(x);
     }
 }
 return differenceSet;
};
let differenceAB = difference(setA, setB); 

  intersection函数和difference函数只有行{1}不同,因为差集中只添加setA有而setB
没有的因素

  差集也足以用更简便易行的语法实现,代码如下:

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

【set代码】

  基于ES6的set开发的类的总体代码如下

let set = new Set();

//--------- Union ----------
let unionAb = new Set();
for (let x of setA) unionAb.add(x);
for (let x of setB) unionAb.add(x);

//--------- Intersection ----------
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);
//alternative - works on FF only
//intersectionAb = new Set([x for (x of setA) if (setB.has(x))]);

//--------- Difference ----------
let difference = function(setA, setB){
    let differenceSet = new Set();

    for (let x of setA){
        if (!setB.has(x)){
            differenceSet.add(x);
        }
    }

    return differenceSet;
};
let differenceAB = difference(setA, setB);
//alternative  - works on FF only
//differenceAB = new Set([x for (x of setA) if (!setB.has(x))]);