数据结构与算法 javascript描述-集合

543 阅读1分钟

生活中的集合

比如数学中的集合

集合的特征与概念

  • 无重复性

  • 空集

  • 子集

集合操作方法

代码实现



/** 
 * @description 集合由一组无序且唯一的项组成
*/
const assert = require("assert");

class CustomSet {
    constructor() {
        this.items = {};
    }
    // 添加元素
    add(value) {
        if (this.has(value)) {
            return false;
        }
        this.items[value] = value;
        return true;
    }
    // 移除元素
    remove(value) {
        if (this.has(value)) {
            delete this.items[value];
            return true;
        }
        return false;
    }
    // 是否存在某元素
    has(value) {
        return this.items.hasOwnProperty(value);
    }
    // 清空
    clear() {
        this.items = {};
    }
    // 元素个数
    size() {
        return Object.keys(this.items).length;
    }
    // 返回集合内所有元素的值的集合
    values() {
        let values = [];
        for (let key in this.items) {
            if (this.has(this.items[key])) {
                values.push(this.items[key]);
            }
        }
        return values;
    }
    // 并集
    union(otherSet = new CustomSet()) {
        const unionSet = new CustomSet();
        const values = this.values();
        const otherValues = otherSet.values();
        values.forEach(item => {
            unionSet.add(item);
        });
        otherValues.forEach(item => {
            unionSet.add(item);
        });
        return unionSet;
    }
    // 交集
    intersection(otherSet = new CustomSet()) {
        const intersectionSet = new CustomSet();
        const values = this.values();
        values.forEach(item => {
            if (otherSet.has(item)) {
                intersectionSet.add(item);
            }
        });
        return intersectionSet;
    }
    // 差集
    difference(otherSet = new CustomSet()) {
        const differenceSet = new CustomSet();
        const values = this.values();
        values.forEach(item => {
            if (!otherSet.has(item)) {
                differenceSet.add(item);
            }
        });
        return differenceSet;
    }
    // 子集
    subset(otherSet = new CustomSet()) {
        if (this.size() > otherSet.size()) {
   return false
        }
        const values = this.values();
        return values.every(item => otherSet.has(item));
    }
}

// test case
const set = new CustomSet();
const otherSet = new CustomSet();
otherSet.add("apple");
otherSet.add("sumsing");
otherSet.add("xm");
set.add("xm");
set.add("xh");
assert.strictEqual(set.size(), 2);
// console.log(set.values())
// console.log(set.union(otherSet))
// console.log(set.intersection(otherSet));
// console.log(set.difference(otherSet));
console.log(set.subset(otherSet));
otherSet.add("xh");
console.log(set.subset(otherSet));

ES6中的Set与WeakSet