JavaScript的数据结构与算法（五） —

集合是由一组无序且唯一的项组成的。这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。在数学中，集合也有并集、交集、差集等基本操作。

集合的基本性质有一条: 集合中元素是不重复的。因为这种性质，所以我们选用了对象来作为集合的容器，而非数组。

简单实现集合类

下面我们先来简单实现一个集合类，并包含以下的方法：

has(value): 检测集合内是否有某个元素

add(value): 给集合内添加某个元素

remove(value): 移除集合中某个元素

clear(value): 清空集合

size(): 返回集合长度

values(): 返回集合转换的数组

代码如下：

function Set() {    var items = {};    /**     * 检测集合内是否存在某个元素     *      * @param {any} value 检测的元素     * @returns 存在则返回true     */    this.has = function (value) {        return items.hasOwnProperty(value);    }    /**     * 给集合添加某个元素     *      * @param {any} value 要添加的元素     * @returns 添加成功返回true     */    this.add = function (value) {        if (this.has(value)) {        // 如果集合中已存在该元素            return false;        }        items[value] = value;        return true;    }    /**     * 移除集合中的某个元素     *      * @param {any} value 要移除的元素     * @returns 移除成功返回true     */    this.remove = function (value) {        if (!this.has(value)) {            // 如果集合中不存在该元素            return false;        }        delete items[value];        return true;    }    /**     * 清空集合     */    this.clear = function () {        items = {};    }    /**     * 返回集合长度     */    this.size = function () {        return Object.keys(size).length    }        /**     * 返回集合转换成的数组     * @returns {Array} 转换后的数组     */    this.values = function () {        var arr = [];        for (var key in items) {            var item = items[key];            arr.push(item)        }        return arr;    }}复制代码

为集合类添加交、并、差集方法

在以上代码基础上进行添加

交集方法

/** * 返回两个集合的交集 * @param {any} otherSet 要进行交集操作的集合 * @returns 两个集合的交集 */this.intersection = function (otherSet) {    // 初始化一个新集合，用于表交集    var interSectionSet = new Set();    // 把当前集合转换成数组    var values = this.values();    // 遍历数组，如果另外一个集合也有该元素，则interSectionSet加入该元素。    for (var i = 0; i < values.length; i++) {        if (otherSet.has(values[i])) {            interSectionSet.add(values[i]);        }    }    return interSectionSet;}复制代码

并集方法

/** * 返回两个集合的并集 * @param {any} otherSet 要进行并集操作的集合 * @returns 两个集合的并集 */this.union = function (otherSet) {    // 初始化一个新集合，用于表示并集    var unionSet = new Set();    // 把当前集合依次添加进unionSet    var values = this.values();    for (var i = 0; i < values.length; i++) {        unionSet.add(values[i]);    }    // 将其他集合转换成数组，依次加添进unionSet    values = otherSet.values();    for (var i = 0; i < values.length; i++) {        unionSet.add(values[i]);    }    return unionSet}复制代码

差集方法

/** * 返回两个集合的差集 *  * @param {any} otherSet 要进行差集操作的集合 * @returns 两个集合的差集 */this.difference = function (otherSet) {    var differenceSet = new Set();    var values = this.values();    // 遍历数组，如果另外一个集合不存在该元素，则differenceSet加入该元素。    for (var i = 0; i < values.length; i++) {        if (!otherSet.has(values[i])) {            differenceSet.add(values[i]);        }    }    return differenceSet;}复制代码

子集方法

/**  * 判断该集合是否为传入集合的子集  * @param {any} otherSet 传入的集合  * @returns 如果为子集则返回true  */ this.subset = function (otherSet) {     // 如果该集合长度大于传入集合的长度，直接返回false，表示不是子集     if (this.size() > otherSet.size()) {         return false     }     var values = this.values();     // 遍历数组, 只要该集合中存在一个传入集合没有的元素，则返回false，表示不是子集     for (var i = 0; i < values.length; i++) {         if (!otherSet.has(values[i])) {             return false;         }     }     return true; }复制代码