数据结构-集合

SegmentFault 发布于2019-08-23 12:15 / 1012人阅读

摘要：集合是一种包含不同元素的数据结构集合中的元素称为成员集合的两个最重要的特性是首先集合中的成员是无序的其次集合中不允许相同成员存在集合在计算机科学中扮演了非常重要的角色然而在很多编程语言中并不把集合当成一种数据类型当你想要创建一个数据结构用来

集合(set)是一种包含不同元素的数据结构. 集合中的元素称为成员. 集合的两个最重要的特性是: 首先, 集合中的成员是无序的; 其次, 集合中不允许相同成员存在. 集合在计算机科学中扮演了非常重要的角色, 然而在很多编程语言中, 并不把集合当成一种数据类型. 当你想要创建一个数据结构, 用来保存一些独一无二的元素时, 比如一段文本中用到的单词, 集合就变得非常有用. 
在ES6中已加入集合Set

集合的定义、操作和属性

集合是由一组无序但彼此之间又有一定相关性的成员构成的, 每个成员在集合中只能出现一次.

集合的定义

下面是一些使用集合必须了解的定义.

不包含任何成员的集合称为 空集_, _全集 则是包含一切可能成员的集合.

如果两个集合的成员完全相同, 则称两个集合相等.

如果一个集合中所有的成员都属于另外一个集合, 则前一集合称为后一集合的子集.

对集合的操作

对集合的基本操作有下面几种:

并集 : 将两个集合中的成员进行合并, 得到一个新的集合.

交集 : 两个集合中共同存在的成员组成一个新的集合.

补集 : 属于一个集合而不属于另一个集合的成员组成的集合.

Set类的实现

Set类的实现基于数组, 数组用来存储数据.

window.log = console.log.bind(console)

class Set {
    constructor() {
        this._dataStore = [];
    }
    add(data) {
        if(!this._dataStore.includes(data)) {
            this._dataStore.push(data);
            return true;
        };
        return false;
    }
    remove(data) {
        const pos = this._dataStore.indexOf(data);
        if(pos > -1) {
            this._dataStore.splice(pos, 1);
            return true;
        };
        return false;
    }
    show() {
        return this._dataStore;
    }
};

add()方法: 因为集合中不能包含相同的元素, 所以, 使用add()方法将数据存储到数组前, 先要确保数组中不存在该数据. 我们使用indexof()检查新加入的元素在数组是否存在. 如果找到, 该方法返回该元素在数组中的位置; 如果没找到, 该方法返回-1. 如果数组中还未包含该元素, add()方法将新加入的元素保存在数组中并返回true; 反之返回false. 将add()方法的返回值定义为布尔类型, 可以明确告诉我们是否将一个元素成功加入到了集合中. 这里使用ES6中的includes()也是可以的.

remove()方法和add()方法的工作原理类似. 首先检查待删除元素是否在数组中, 如何在, 则使用数组的splice()方法删除该元素并返回true; 反之返回false, 表示集合中不存在这样的一个元素.

show()显示集合中的成员.
测试程序:

const s = new Set();
s.add("a");
s.add("b");
s.add("c");
s.add("d");
s.add("e");
s.add("f");
log(s.show());
if(s.add("f")) {
    log("f: 添加成功")
} else {
    log("已存在f, 添加失败")
}

输出:

(6) ["a", "b", "c", "d", "e", "f"]
已存在f, 添加失败

更多集合操作

定义union()、subset()和difference()方法会更有意思. union()方法执行并集操作, 将两个集合合并成一个. 该方法首先将第一个集合里的成员悉数加入一个临时集合, 然后检查第二个集合中的成员, 看它们是否也同时属于第一个集合. 如果属于, 则跳过该成员, 否则就将该成员加入临时集合.

在定义union()方法前, 先定一个辅助方法contains(), 该方法检查一个成员是否属于该集合.

contains(data) {
    return this._dataStore.includes(data);
}
// 并集
union(set) {
    const tempSet = new Set();
    this._dataStore.forEach(i => {
        tempSet.add(i);
    });
    set._dataStore.forEach(i => {
        if(!tempSet.contains(i)) {
            tempSet._dataStore.push(i)
        }
    });

    return tempSet;
}

执行程序:

const s = new Set();
s.add("a");
s.add("b");
s.add("c");
s.add("d");
s.add("e");
s.add("f");
log(s.show());

const s1 = new Set();
s1.add("a");
s1.add("f");
s1.add("g");

let res = new Set();
res = s.union(s1);
log(res.show());

//输出:
// (6) ["a", "b", "c", "d", "e", "f"]
// (7) ["a", "b", "c", "d", "e", "f", "g"]

使用intersect()方法求两个集合的交集. 该方法定义起来相对简单. 每当发现第一个集合的成员也属于第二个集合时, 便将该成员加入一个心机和, 这个心机和即为方法的返回值.

// 交集
intersect(set) {
    const tempSet = new Set();
    this._dataStore.forEach(i => {
        if(set.contains(i)) {
            tempSet.add(i)
        };
    });

    return tempSet;
}

下一个要定义的操作是subset()判断子集. subset()方法首先要确定该集合的长度是否小于带比较集合.
如果该集合比带比较集合还要大, 那么该集合肯定不会是待比较集合的一个子集.
当集合的长度小于待比较集合时, 再判断该集合内的成员是否都属于待比较集合. 如果有任意一个成员不属于待比较集合, 则返回false, 程序终止. 如果一直比较完该集合的最后一个元素, 所有元素都属于待比较集合, 那么该集合就是待比较集合的一个子集, 该方法返回true.
在判断每个元素是否属于待比较集合前, 该方法先使用size()方法对比两个集合的大小.

size() {
    return this._dataStore.length;
}
subSet(set) {
    if(this.size() > set.size()) {
        return false;
    };
    for(let i = 0; i < this._dataStore.length; i++) {
        if(!set.contains(this._dataStore[i])) {
            return false;
        };
    };
    return true;
}

最后一个操作是difference()补集, 该方法返回一个新集合, 该集合包含的是那些属于第一个集合但不属于第二个集合的成员.

difference(set) {
    const tempSet = new Set();
    this._dataStore.forEach(i => {
        if(!set.contains(i)) {
            tempSet.add(i);
        };
    });

    return tempSet;
}

GPU云服务器云服务器数据集合 java集合结构 js 集合数据结构 js存储集合数据

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

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

学习JavaScript数据结构与算法（三）：集合

摘要：至于这三个的具体概念，可以看图中集合的实现首先，创建一个构造函数。前端路漫漫，且行且歌的前端乐园原文链接寒假前端学习学习数据结构与算法三集合本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第四篇文章：学习JavaScript数据结构与...

BDEEFE 2019-08-22 10:59 评论0 收藏0
【前端数据结构基础】集合

摘要：前言集合是一种包含不同元素的数据结构。二构造集合数据结构我们将使用实现集合结构，各部分功能使用注释说明。参考资料数据结构与算法描述第章集合由于书上的源代码出现了错误，因此代码根据实际运行结果做了相应修改。前言集合是一种包含不同元素的数据结构。集合最重要的两个特性是：首先，集合中的成员是无序的；其次，集合中不允许相同成员存在。一、关于集合集合的定义我们必须要了解以下关于集合的定...

wawor4827 2019-08-22 17:58 评论0 收藏0
Java™ 教程（集合介绍）

集合介绍本节介绍Java集合框架，在这里，你将了解集合是什么以及它们如何使你的工作更轻松、程序更好，你将了解构成Java集合框架的核心元素 — 接口、实现、聚合操作和算法。集合 — 有时称为容器 — 只是一个将多个元素组合到一个单元中的对象，集合用于存储、检索、操作和传递聚合数据。通常，它们代表形成自然组的数据项，例如扑克牌（卡片集合）、邮件文件夹（信件集合）或电话目录（名称到电话号码的映射）...

taoszu 2019-08-16 14:34 评论0 收藏0
JavaScript的数据结构与算法（五） —— 集合

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

wangshijun 2019-08-21 17:13 评论0 收藏0
学习javascript数据结构(三)——集合

摘要：前言总括本文讲解了数据结构中的集合概念，并使用实现了集合。原文博客地址学习数据结构三集合知乎专栏简书专题前端进击者知乎前端进击者简书博主博客地址的个人博客人生多风雨，何处无险阻。敬请期待学习数据结构四散列表前言总括：本文讲解了数据结构中的[集合]概念，并使用javascript实现了集合。原文博客地址：学习javascript数据结构(三)——集合知乎专栏&&简书专题：前端...

alphahans 2019-08-22 10:45 评论0 收藏0