数据结构—集合 - Githubissues

集合

集合是由一组无序且唯一（即不能重复）的项组成的。这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。

在深入学习集合的计算机科学实现之前，我们先看看它的数学概念。在数学中，集合是一组不同的对象（的集）。

比如说，一个由大于或等于0的证书组成的自然数集合N = {0, 1, 2, 3, 4, 5, 6...}。集合中的对象列表用{}包围

还有一个概念叫空集。空集就是不包含任何元素的集合。用{}表示

你也可以把集合想象成一个既没有重复元素，也没有顺序概念的数组。

在数学中，集合也有并集、交集、差集等基本操作。后续会介绍这些操作。

创建集合

function Set () {
    let items = {};

    // 向集合添加一个新的项
    this.add = value => {};

    // 从集合移除一个值
    this.delete = value => {};

    // 判断值是否在集合中
    this.has = value => {};

    // 移除集合中的所有项
    this.clear = () => {};

    // 返回集合所包含元素的数量。与数组的length属性类似
    this.size = () => {};

    // 返回一个包含集合中所有的数组
    this.values = () => {};
}

has

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

add

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

remove

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

clear

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

size

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

values

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

集合操作

对于集合可以进行如下操作

并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合
差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合
子集：验证一个给定集合是否是另一集合的子集。

并集

this.union = function (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;
}

交集

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

差集

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

子集

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

ECMAScript6 支持了Set类，可以自行去看相关的实现

EmberYu / vic-blog

数据结构—集合 #11

集合