前端数据结构之集合

jiezi

5 年前

集合、字典和散列表可以存储不重复的值。
在集合中，我们感兴趣的是每个值本身，并把它当作主要元素。
在字典中，我们用 [键，值] 的形式来存储数据。
在散列表中也是一样（也是以 [键，值] 对的形式来存储数据）。

集合是由一组无序且唯一的项组成的。（即不能重复的）
集合是一组不同的对象（的集）。比如说，一个由大于或等于 0 的整数组成的自然数集合：N={0,1,2,3,4,5,6,…}。
集合也有并集、交集、差集等基本操作。下面将介绍这些操作

创建集合（实现的类与 es6 的 set 类类似）

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

接下来，需要声明一些集合可用的方法

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

has(value)：如果值在集合中，返回 true，否则返回 false。

/**
* @description 定义一个集合是否有该值的方法
* @param {string} 值
* @return {boolean}
*/
this.has = value => value in items;

add(value)：向集合添加一个新的项。

/**
* @description 添加
*/
this.add = value => {if (!this.has(value)) {items[value] = value;

  return true;
}

return false;
}

delete(value)：从集合移除一个值。

/**
* @description 删除
*/
this.delete = value => {if (this.has(value)) {delete items[value];

  return true;
}

return false;
}

clear()：移除集合中的所有项。

/**
* @description 清除
*/
this.clear = () => {items = {};

return true;
}

size()：返回集合所包含元素的数量。与数组的 length 属性类似。

/**
* @description 求集合长度
*/
this.size = () => Object.keys(items).length;

values()：返回一个包含集合中所有值的数组。

/**
* @description 返回集合中值的数组
*/
this.values = () => Object.values(items);

测试我们的 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.delete(1); 
console.log(set.values()); // 输出["2"]
console.log(set.has(2)); //false
console.log(set.size()); //1
set.delete(2); 
console.log(set.values()); // 输出[]
console.log(set.has(2)); //false
console.log(set.size()); //0

集合操作

对集合可以进行如下操
1、并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合

实现 Set 类的 union 方法

/**
* @description 并集
*/
this.union = setB => {let unionSet = new Set();
const values = this.values();

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

const setBValues = setB.values();

for (let i = 0; i < setBValues.length; i++) {if (!unionSet.has(setBValues[i])) {unionSet.add(setBValues[i]);
  }
}

return unionSet;
}

输出为[1, 2, 3, 4, 5, 6]。注意元素 3 同时存在于 A 和 B 中，它在结果的集合中只出现一次。
2、交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合

现在来实现 Set 类的 intersection 方法：

/**
* @description 交集
*/
this.intersection = setB => {let intersectionSet = new Set();
const values = this.values();


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

return intersectionSet;
}

3、差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合

/**
* @description 差集
*/
this.difference = setB => {let differenceSet = new Set();
const values = this.values();

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

return differenceSet;
}

4、子集：验证一个给定集合是否是另一集合的子集

  /**
   * @description 子集
   */
  this.subset = setB => {if (this.size > setB.size) {return false;}

    const values = this.values();

    for (let i = 0; i < values.length; i++) {if (!setB.has(values[i])) {return false;}
    }
    return true;
  }
}

完整代码

function Set() {let items = {}; // 定义一个集合

  /**
   * @description 定义一个集合是否有该值的方法
   * @param {string} 值
   * @return {boolean}
   */
  this.has = value => value in items;

  /**
   * @description 添加
   */
  this.add = value => {if (!this.has(value)) {items[value] = value;

      return true;
    }

    return false;
  }

  /**
   * @description 删除
   */
  this.delete = value => {if (this.has(value)) {delete items[value];

      return true;
    }

    return false;
  }

  /**
   * @description 清除
   */
  this.clear = () => {items = {};

    return true;
  }

  /**
   * @description 求集合长度
   */
  this.size = () => Object.keys(items).length;

  /**
   * @description 返回集合中值的数组
   */
  this.values = () => Object.values(items);

  /**
   * @description 并集
   */
  this.union = setB => {let unionSet = new Set();
    const values = this.values();

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

    const setBValues = setB.values();

    for (let i = 0; i < setBValues.length; i++) {if (!unionSet.has(setBValues[i])) {unionSet.add(setBValues[i]);
      }
    }

    return unionSet;
  }

  /**
   * @description 交集
   */
  this.intersection = setB => {let intersectionSet = new Set();
    const values = this.values();


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

    return intersectionSet;
  }

  /**
   * @description 差集
   */
  this.difference = setB => {let differenceSet = new Set();
    const values = this.values();

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

    return differenceSet;
  }

  /**
   * @description 子集
   */
  this.subset = setB => {if (this.size() > setB.size()) {return false;}

    const values = this.values();

    for (let i = 0; i < values.length; i++) {if (!setB.has(values[i])) {return false;}
    }
    return true;
  }
}

验证

   // 合集
    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('合集');
    console.log(setA.values());
    console.log(setB.values());
    console.log(unionAB.values()); // [1,2,3,4,5,6]

    // 交集
    let setC = new Set();
    setC.add(1);
    setC.add(2);
    setC.add(3);

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

    let intersectionCD = setC.intersection(setD);
    console.log('交集');
    console.log(setC.values());
    console.log(setD.values());
    console.log(intersectionCD.values()); // [2,3]

    // 差集
    let setE = new Set();
    setE.add(1);
    setE.add(2);
    setE.add(3);

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

    let differenceEF = setA.difference(setF);
    console.log('差集');
    console.log(setE.values());
    console.log(setF.values());
    console.log(differenceEF.values()); // [1]

    // 子集
    let setH = new Set();
    setH.add(1);
    setH.add(2);

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

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

    console.log('子集');
    console.log(setH.values());
    console.log(setI.values());
    console.log(setG.values());
    console.log(setH.subset(setI)); // true
    console.log(setI.subset(setG)); // false

应用 es6 Set

数组去重

let arr = [3, 5, 2, 2, 5, 5];
let unique = [...new Set(arr)];
console.log(unique)// [3, 5, 2]

并集（Union）、交集（Intersect）和差集（Difference）

let a = new Set([1, 2, 3]);
let b = new Set([4, 3, 2]);

// 并集
let union = new Set([...a, ...b]);
console.log(union)// Set {1, 2, 3, 4}

// 交集
let intersect = new Set([...a].filter(x => b.has(x)));
console.log(intersect)// set {2, 3}

// 差集
let difference = new Set([...a].filter(x => !b.has(x)));
console.log(difference)// Set {1}

集合，字典，散列表又称哈希表

集合

创建集合（实现的类与 es6 的 set 类类似）

集合操作

应用 es6 Set