JavaScript数据结构与算法（3）集合

素颜马尾好姑娘i 2022-01-30 07:25 345阅读 0赞

主要参考：
https://www.cnblogs.com/xiaohuochai/p/8176248.html
《学习JavaScript数据结构与算法》

1.集合介绍

一个集合示例：

  1. {1,2,3,4,5}

其实集合set内部是键值对方式：

在这里插入图片描述
集合这种键值对方式和字典很相似，集合是以[值，值]的形式存储元素，字典则是以[键，值]的形式来存储元素。

2.创建集合

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

代码实现如下：

  1. function Set(){
  3.     var items = {};
  5.     //has(value)值是否在集合中，而且has方法会被下面调用
  6.     this.has = function(value){
  7.         return items.hasOwnProperty(value);
  8.     }
  9.     //add(value)添加值
  10.     this.add = function(value){
  11.         if(!this.has(value)){
  12.             items[value] = value;
  13.             return true; //表示执行到此结束，返回true，不然执行下面，返回false
  14.         }
  15.         return false;
  16.     }
  18.     //remove(value)
  19.     this.remove = function(value){
  20.         if(has(value)){
  21.             delete items[value]; //delete 操作符用于删除对象{}/数组[]的某个属性；如果没有指向这个属性的引用，那它最终会被释放。
  22.             return true;
  23.         }
  24.     }
  26.     //clear()，移除集合中所有值,把一个空对象重新赋值给它
  27.     this.clear = function(){
  28.         items = {};
  29.     }
  31.     //size，一种方法是add或remove时length控制，下面是第二种方法
  32.     this.size = function(){
  33.         return Object.keys(items).length;
  34.     }
  35.     //sizeLegacy第三种方法，遍历items对象的每一个属性，记录属性的个数并返回这个数字。
  36.     this.sizeLegacy = function(){
  37.         var count = 0;
  38.         for(var prop in items){
  39.             if(items.hasOwnProperty(prop)){
  40.                 ++count;
  41.             }
  42.         }
  43.         return count;
  44.     }
  46.     //values 返回一个包含集合中所有值的数组，第一种方法，通过Object.keys()返回一个索引数组。
  47.     this.values = function(){
  48.         let values = [];
  49.         let keys = Object.keys(items);
  51.         for(let i=0;i<keys.length;i++){
  52.             values.push(items[keys[i]]); //因为items是以对象形式，所以是[]形式
  53.         }
  54.         return values;
  56.     }
  57.     //values第二种方法，for in遍历可遍历对象，for in返回的是对象的每一个下标，还要记得使用hasOwenProperty（）
  58.     this.valuesLegacy = function(){
  59.         let values1 = [];
  60.         for(let key in items){
  61.             if(items.hasOwnProperty(key)){
  62.                 values.push(items[keys])
  63.             }
  64.         }
  65.         return values1;
  66.     }
  68. }
  70. //测试Set类
  71. var set = new Set(); 
  72. set.add(1);
  73. console.log(set.values()); //输出["1"]
  74. console.log(set.has(1)); //输出true
  75. console.log(set.size()); //输出1
  76. set.add(2);
  77. console.log(set.values()); //输出["1", "2"]
  78. console.log(set.has(2)); //true 
  79. console.log(set.size()); //2
  80. set.remove(1); 
  81. console.log(set.values()); //输出["2"]
  82. set.remove(2); 
  83. console.log(set.values()); //输出[]

3.集合操作

对集合可以进行如下操作
1、并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合
2、交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合
3、差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合
4、子集：验证一个给定集合是否是另一集合的子集

并集:

  1. this.union = function(otherSet){
  3.     //这里面用到了上面声明的new Set()、values()、add()
  5.     //新的Set合集
  6.     let unionSet = new Set();
  8.     let values = this.values(); //this，获取当前示例的values（）,即集合的数组形式
  9.     for(let i=0;i<values.length;i++){
  10.         unionSet.add(values[i]);
  11.     }
  13.     let values1 = otherSet.values();
  14.     for(let i=0;i<values1.length;i++){
  15.         unionSet.add(values1[i]);
  16.     }
  18.     return unionSet;
  20. }

交集：

  1. this.intersection = function(otherSet){
  3.     let intersection = new Set();
  5.     let values = this.values();
  7.     for(let i=0;i<values.length;i++){
  8.         if(otherSet.has(values[i])){
  9.             intersection.add(values[i]);
  10.         }
  11.     }
  13.     return intersection;
  15. }

差集:

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

子集：

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

4.完整代码

  1. function Set() {
  3.     let items = {};
  5.     this.add = function(value){
  6.         if (!this.has(value)){
  7.             items[value] = value;
  8.             return true;
  9.         }
  10.         return false;
  11.     };
  13.     this.delete = function(value){
  14.         if (this.has(value)){
  15.             delete items[value];
  16.             return true;
  17.         }
  18.         return false;
  19.     };
  21.     this.has = function(value){
  22.         return items.hasOwnProperty(value);
  23.         //return value in items;
  24.     };
  26.     this.clear = function(){
  27.         items = {};
  28.     };
  30.     /**
  31.      * Modern browsers function
  32.      * IE9+, FF4+, Chrome5+, Opera12+, Safari5+
  33.      * @returns {Number}
  34.      */
  35.     this.size = function(){
  36.         return Object.keys(items).length;
  37.     };
  39.     /**
  40.      * cross browser compatibility - legacy browsers
  41.      * for modern browsers use size function
  42.      * @returns {number}
  43.      */
  44.     this.sizeLegacy = function(){
  45.         let count = 0;
  46.         for(let key in items) {
  47.             if(items.hasOwnProperty(key))
  48.                 ++count;
  49.         }
  50.         return count;
  51.     };
  53.     /**
  54.      * Modern browsers function
  55.      * IE9+, FF4+, Chrome5+, Opera12+, Safari5+
  56.      * @returns {Array}
  57.      */
  58.     this.values = function(){
  59.         let values = [];
  60.         for (let i=0, keys=Object.keys(items); i<keys.length; i++) {
  61.             values.push(items[keys[i]]);
  62.         }
  63.         return values;
  64.     };
  66.     this.valuesLegacy = function(){
  67.         let values = [];
  68.         for(let key in items) {
  69.             if(items.hasOwnProperty(key)) {
  70.                 values.push(items[key]);
  71.             }
  72.         }
  73.         return values;
  74.     };
  76.     this.getItems = function(){
  77.       return items;
  78.     };
  80.     this.union = function(otherSet){
  81.         let unionSet = new Set(); //{1}
  83.         let values = this.values(); //{2}
  84.         for (let i=0; i<values.length; i++){
  85.             unionSet.add(values[i]);
  86.         }
  88.         values = otherSet.values(); //{3}
  89.         for (let i=0; i<values.length; i++){
  90.             unionSet.add(values[i]);
  91.         }
  93.         return unionSet;
  94.     };
  96.     this.intersection = function(otherSet){
  97.         let intersectionSet = new Set(); //{1}
  99.         let values = this.values();
  100.         for (let i=0; i<values.length; i++){ //{2}
  101.             if (otherSet.has(values[i])){    //{3}
  102.                 intersectionSet.add(values[i]); //{4}
  103.             }
  104.         }
  106.         return intersectionSet;
  107.     };
  109.     this.difference = function(otherSet){
  110.         let differenceSet = new Set(); //{1}
  112.         let values = this.values();
  113.         for (let i=0; i<values.length; i++){ //{2}
  114.             if (!otherSet.has(values[i])){    //{3}
  115.                 differenceSet.add(values[i]); //{4}
  116.             }
  117.         }
  119.         return differenceSet;
  120.     };
  122.     this.subset = function(otherSet){
  124.         if (this.size() > otherSet.size()){ //{1}
  125.             return false;
  126.         } else {
  127.             let values = this.values();
  128.             for (let i=0; i<values.length; i++){ //{2}
  129.                 if (!otherSet.has(values[i])){    //{3}
  130.                     return false; //{4}
  131.                 }
  132.             }
  133.             return true;
  134.         }
  135.     };
  136. }

ES6版本代码：

  1. let Set2 = (function () {
  3.     const items = new WeakMap();
  5.     class Set2 {
  7.         constructor () {
  8.             items.set(this, {});
  9.         }
  11.         add(value){
  12.             if (!this.has(value)){
  13.                 let items_ = items.get(this);
  14.                 items_[value] = value;
  15.                 return true;
  16.             }
  17.             return false;
  18.         }
  20.         delete(value){
  21.             if (this.has(value)){
  22.                 let items_ = items.get(this);
  23.                 delete items_[value];
  24.                 return true;
  25.             }
  26.             return false;
  27.         }
  29.         has(value){
  30.             let items_ = items.get(this);
  31.             return items_.hasOwnProperty(value);
  32.         }
  34.         clear(){
  35.             items.set(this, {});
  36.         }
  38.         size(){
  39.             let items_ = items.get(this);
  40.             return Object.keys(items_).length;
  41.         }
  44.         values(){
  45.             let values = [];
  46.             let items_ = items.get(this);
  47.             for (let i=0, keys=Object.keys(items_); i<keys.length; i++) {
  48.                 values.push(items_[keys[i]]);
  49.             }
  50.             return values;
  51.         }
  53.         getItems(){
  54.             return items.get(this);
  55.         }
  57.         union(otherSet){
  58.             let unionSet = new Set();
  60.             let values = this.values();
  61.             for (let i=0; i<values.length; i++){
  62.                 unionSet.add(values[i]);
  63.             }
  65.             values = otherSet.values();
  66.             for (let i=0; i<values.length; i++){
  67.                 unionSet.add(values[i]);
  68.             }
  70.             return unionSet;
  71.         }
  73.         intersection(otherSet){
  74.             let intersectionSet = new Set();
  76.             let values = this.values();
  77.             for (let i=0; i<values.length; i++){
  78.                 if (otherSet.has(values[i])){
  79.                     intersectionSet.add(values[i]);
  80.                 }
  81.             }
  83.             return intersectionSet;
  84.         }
  86.         difference(otherSet){
  87.             let differenceSet = new Set();
  89.             let values = this.values();
  90.             for (let i=0; i<values.length; i++){
  91.                 if (!otherSet.has(values[i])){
  92.                     differenceSet.add(values[i]);
  93.                 }
  94.             }
  96.             return differenceSet;
  97.         };
  99.         subset(otherSet){
  101.             if (this.size() > otherSet.size()){
  102.                 return false;
  103.             } else {
  104.                 let values = this.values();
  105.                 for (let i=0; i<values.length; i++){
  106.                     if (!otherSet.has(values[i])){
  107.                         return false;
  108.                     }
  109.                 }
  110.                 return true;
  111.             }
  112.         };
  113.     }
  114.     return Set2;
  115. })();

5.ES6中集合

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

和我们的Set不同，ES6的Set的values方法返回Iterator，而不是值构成的数组。另一个区别是，我们实现的size方法返回set中存储的值的个数，而ES6的Set则有一个size属性:

  1. let set = new Set([1,2,3,2,4,5,6,7])
  3. set.has(1)
  4. true
  6. set.size
  7. 8

在这里插入图片描述

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

  1. set.delete(1)
  2. true

clear方法会重置set数据结构，这跟我们实现的功能一样

  1. set.clear()
  2. undefined
  4. set
  5. Set(0) {}

ES6中的集合

  1. let set = new Set();
  3. //--------- Union ----------
  4. let unionAb = new Set();
  5. for (let x of setA) unionAb.add(x);
  6. for (let x of setB) unionAb.add(x);
  8. //--------- Intersection ----------
  9. let intersection = function(setA, setB){
  10.     let intersectionSet = new Set();
  12.     for (let x of setA){
  13.         if (setB.has(x)){
  14.             intersectionSet.add(x);
  15.         }
  16.     }
  18.     return intersectionSet;
  19. };
  20. let intersectionAB = intersection(setA, setB);
  21. //alternative - works on FF only
  22. //intersectionAb = new Set([x for (x of setA) if (setB.has(x))]);
  24. //--------- Difference ----------
  25. let difference = function(setA, setB){
  26.     let differenceSet = new Set();
  28.     for (let x of setA){
  29.         if (!setB.has(x)){
  30.             differenceSet.add(x);
  31.         }
  32.     }
  34.     return differenceSet;
  35. };
  36. let differenceAB = difference(setA, setB);
  37. //alternative  - works on FF only
  38. //differenceAB = new Set([x for (x of setA) if (!setB.has(x))]);

更详细可以参考上面链接和书籍。

发表评论

表情：
评论列表 （有 0 条评论，345人围观）

还没有评论，来说两句吧...

相关阅读

    相关 算法与数据结构之集合

    重点知识 1. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希查找。 2. 动态查找表和静态查找表的重要区别在于前者包含有插入和删除运算，而后者不包含这

    骑猪看日落骑猪看日落/ 0 赞/ 695 阅读