4. 数据结构-集合

集合　

　　说到集合，第一个想到的就是中学学到的那个数学概念：集合。在我们开始集合相关的 js 实现前，我们有必要来了解一下什么是集合以及集合的数学概念。
　　集合是由一组无序且唯一的项组成的。集合这个数据结构使用了与有限集合相同的数学概念。在数学中，集合是指具有某种特定性质的具体的或抽象的对象汇总成的集体，这些对象称为该集合的元素。

比如，一个包括 0 到 9 十个数字的集合表示为：N = {0,1,2,3,4,5,6,7,8,9}。集合中的对象列表用{}（大括号）包围。还有一个概念叫做空集，也就是该集合中不包含任何元素，也就是{}，空集是任何集合的子集。

除了集合的基本概念，还有一些简单的集合操作，比如并集、交集、差集和子集等。在后面会详细的介绍这些集合的操作。

那么集合的数据概念就简单介绍完了。我们看看如何去创建一个集合类（set）。

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

set 类可用的方法:

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

function Set() {
  let items = {};
  //判断该set实例中是否存在该value
  this.has = function (value) {
    //检查它（或其原型链）上是否包含具有指定名称的属性的对象。但是in运算符会查找其原型链上的属性。所以我们用下面的方法更好
    //return value in items;
    //hasOwnProperty方法可以用来检测一个对象是否含有特定的自身属性；和 in 运算符不同，该方法会忽略掉那些从原型链上继承到的属性。
    //所以我们也可以用hasOwnProperty来判断一个对象的自身属性是否存在
    return items.hasOwnProperty(value);
  };
  this.add = function (value) {
    //通过我们上面写的has方法来判断这个值是否存在，如果不存在就添加进去，存在就返回false
    if (!this.has(value)) {
      items[value] = value;
      return true;
    }
    return false;
  };
  //同样的道理，判断该set中是否有要删除的对象，如果有就删除，没有就返回false
  this.remove = function (value) {
    if (this.has(value)) {
      delete items[value];
      return true;
    }

    return false;
  };
  //直接充值items为空，就变相的清空了items中的所有属性
  this.clear = function () {
    items = {};
  };
  //Object.keys是ES6中为对象新增的原生方法，它会返回一个数组，其中包含对象的所有元素，这样我们就可以获取其元素的个数了。
  this.size = function () {
    return Object.keys(items).length;
  };
  //上面我们用ES6新方法来获取items的长度，但是或许有些浏览器的兼容性不是很好。所以我们也可以用循环遍历计数的方式来完成这个功能
  this.sizeLegacy = function () {
    let count = 0;
    for (let key in items) {
      if (items.hasOwnProperty(key)) ++count;
    }
    return count;
  };

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

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

集合的操作

并集: 对于给定的两个集合,返回一个包含两个集合中所有元素的新集合.注意,集合中不会有重复的值.
交集: 对于给定的两个集合,返回一个包含两个集合中共有元素的新集合.
差集: 对于给定的集合,返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合.简单来说就是我有你没有的元素.
验证一个给定集合是否是另一个集合的子集.

1. 并集

//并集操作
this.union = function (otherSet) {
  //存储两个集合元素的新集合，后面我们会把它作为返回值返回。
  let unionSet = new Set();
  //values为当前set的数组列表
  let values = this.values();
  //循环加入
  for (let i = 0; i < values.length; i++) {
    unionSet.add(values[i]);
  }
  //重新复制values
  values = otherSet.values();
  //把otherSet的值循环存入unionSet，由于我们的add不会加入重复的值，自然在unionSet中就不会出现重复的值
  for (let i = 0; i < values.length; i++) {
    unionSet.add(values[i]);
  }

  return unionSet;
};

/*
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
let setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);

let unionAB = setA.union(setB);
console.log(unionAB.values()); // [1, 2, 3, 4, 5, 6]
*/

2. 交集

//交集操作
this.intersection = function (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;
};

/*
let setC = new Set();
setC.add(5);
setC.add(6);
setC.add(7);

let setD = new Set();
setD.add(5);
setD.add(7);
setD.add(4);
setD.add(8);

let intersectionSetCD = setC.intersection(setD);
console.log(intersectionSetCD.values()); //[5,7]
*/

3. 差集

//差集操作
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])) {
      differenceSet.add(values[i]);
    }
  }
  return differenceSet;
};

/* 
let setM = new Set();
setM.add(5);
setM.add(6);
setM.add(7);

let setN = new Set();
setN.add(5);
setN.add(7);
setN.add(4);
setN.add(8);


let differenceSetMN = setM.difference(setN);
console.log(differenceSetMN.values());//[6]
*/

4. 子集

//子集操作
this.subset = function (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;
  }
};

/* 
let setX = new Set();
setX.add(1);
setX.add(2);

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

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

console.log(setX.subset(setY));//true
console.log(setX.subset(setZ));//false
*/

ES6 原生 Set 类

let set = new Set();
set.add(1);
console.log(set.values()); //SetIterator {1}
set.add(2);
console.log(set.has(1)); //true
console.log(set.size); //2
console.log(set.delete(1)); //true
console.log(set.size); //1
console.log(set.has(1)); //false
console.log(set.has(2)); //true

原生Set 类拥有 has()、add()、delete()、clear()等方法。也拥有 values()、keys()、entries()、forEach()等遍历方法，还拥有一个 size 属性

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();
//其实跟我们自定义并集操作的原理是一样的，分别遍历两个集合并把其元素加入到unionAb中
//for...of 这种操作也是ES6的循环遍历方法。
for (let x of setA) unionAb.add(x);
for (let x of setB) unionAb.add(x);
console.log(unionAb.values()); //SetIterator {1, 2, 3, 4}

//模拟交集操作
//模拟交集操作需要创建一个辅助函数，来生成包含setA和setB都有的元素的新集合。
let intersetion = function (setA, setB) {
  let intersetionSet = new Set();

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

  return intersetionSet;
};

let intersetionAb = intersetion(setA, setB);
console.log(intersetionAb.values()); //SetIterator {2, 3}

//模拟差集操作
//同样的，跟交集操作极为类似，只是判断条件刚好相反罢了
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);
console.log(differenceAb.values()); //SetIterator {1}

ES6 原生 Set 类模拟集合操作和自定义的集合操作方法极为相似,只是使用了 ES6 原生的接口罢了.

4.数据结构-集合