JavaScript数据结构与算法——集合

1.集合数据结构

集合是一组无序且唯一（不能重复）的项组成的。这个数据结构使用了和有限集合相同的数学概念。

2.创建集合

function Set() {
    // 这里使用对象而不是数组来表示集合 
    // js对象中不允许一个键值指向两个不同属性，也保证了集合中的元素都是唯一的
    let items = {};
    //1.首先实现has(value)方法
    this.has = function(value) {
        return value in items;
        //return items.hasOwnProperty(value);
    }
    //2.向集合添加一个项
    this.add = function(value) {
        if (!this.has(value)) {
            items[value] = value;
            return true;
        } else{
            return false;
        }
    }
    //3.移除某一项和清空集合
    this.remove = function(value) {
        if (this.has(value)) {
            delete items[value];
            return true;
        } else{
            return false;
        }
    }
    this.clear = function() {
        items = {};
    }
    //4.返回集合长度
    this.size = function() {
        return Object.keys(items).length;
    }
    // 兼容性更好
    this.sizeLegacy = function() {
        let count = 0;
        for(let key in items) {
            if(items.hasOwnProperty(key)) 
                ++count;
        }
        return count;
    }
    //5.返回一个包含集合中所有值的数组
    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[keys)
            }
        };
        return values;
    }
}

集合的使用

let 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.remove(1);
console.log(set.values()); // ['2']
console.log(set.has(1)); // false
console.log(set.size()); // 1

3.集合的操作

集合有：并集、交集、差集、子集

// 1.实现并集
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;
}
// 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;
}
// 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;
}
// 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 true
            }
        }
        return true;
    }
}

在es6中新增了set类，我们也可以使用其中自带的方法。