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

wangshijun 发布于2019-08-21 17:13 / 2870人阅读

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

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

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

简单实现集合类

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

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

服务器托管云服务器 javascript的集合描述的数据结构与算法二分图集合算法 javascript集合

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/89270.html

前端面试总结--数据结构与算法五

摘要：结构的实例的方法，用于对每个成员执行某种操作，没有返回值。参考和数据结构推荐一个找组件的轮子工厂前端面试总结数据结构与算法一前端面试总结数据结构与算法二前端面试总结数据结构与算法三前端面试总结数据结构与算法四集合集合是由一组无序且唯一的项组成。这个数据结构使用了与有限集合相同的数学概念。创建一个集合 function Set(){ var items = {}; } ...

xuexiangjys 2019-08-21 16:25 评论0 收藏0
CSS技巧

摘要：技巧使你的更加专业这是上关于技巧的一篇译文，另外你也可以在本项目看到原文。列举了一些很实用的技巧，比如给空内容的标签添加内容，逗号分隔列表等等。排序算法看源码，把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。成为专业程序员路上用到的各种优秀资料、神器及框架成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 Java...

DangoSky 2019-08-22 11:15 评论0 收藏0
CSS技巧

摘要：技巧使你的更加专业这是上关于技巧的一篇译文，另外你也可以在本项目看到原文。列举了一些很实用的技巧，比如给空内容的标签添加内容，逗号分隔列表等等。排序算法看源码，把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。成为专业程序员路上用到的各种优秀资料、神器及框架成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 Java...

zgbgx 2019-08-29 14:01 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

Jonathan Shieber 2019-08-29 12:33 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

SHERlocked93 2019-08-22 11:04 评论0 收藏0