学习数据结构与算法之集合

fai1017 发布于2019-08-21 11:51 / 3360人阅读

本系列所有文章：
第一篇文章：学习数据结构与算法之栈与队列
第二篇文章：学习数据结构与算法之链表
第三篇文章：学习数据结构与算法之集合
第四篇文章：学习数据结构与算法之字典和散列表
第五篇文章：学习数据结构与算法之二叉搜索树

集合简介

记得高一数学第一节课学的就是集合，现在快大四了再看到它有种见了老朋友的感觉。哈哈，闲话不多扯，进入正题。

集合是由一组无序且不重复的项组成的数据结构。这里集合的概念和高中数学类似，也有空集，交集，并集，子集等概念，只不过在这里就没有那么复杂的证明题了。那么接下来就用JavaScript实现一下集合。

用JavaScript实现集合

老规矩，先弄一个构造函数出来

function Set () {
  // 这里用对象来模拟集合
  var items = {}
}

集合要实现以下方法：

add(value)：向集合添加新的项

remove(value)：从集合删除一项

has(value)：如果集合中存在该项则返回true，否则返回false

clear()：清除集合中的所有项

size()：返回集合包含元素的数量

values()：返回集合中所有值的数组

实现has

根据hasOwnProperty判断该元素是否属于集合，注意：hasOwnProperty可以检查属性是否属于对象，对于原型链上的属性hasOwnProperty会返回false

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
}

实现values

Object.keys的作用是返回对象中所有可枚举属性组成的数组（不包括原型链上的属性）。当然，你也可以用for...in 来实现。

this.values = function () {
  return Object.keys(items)
}

实现clear和size

比较简单，就直接贴源码了

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

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

实现集合操作

集合有以下操作：

并集

交集

差集

子集

具体的就不多解释了，请看代码

实现并集

创建一个新集合unionSet表示两个集合的并集，之后分别遍历两个集合添加进unionSet，最后返回集合

this.union = function (otherSet) {
  var unionSet = new Set()
  
  var values = this.values()
  for (var i = 0; i < values.length; i++) {
    unionSet.add(values[i])
  }
  
  values = otherSet.values()
  for (var i = 0; i < values.length; i++) {
    unionSet.add(values[i])
  }
  return unionSet
}

实现交集

交集是两者都有的属性的集合，实现思路与上面类似，只要判断元素是否同时存在与两个集合就行了

this.intersection = function (otherSet) {
  var intersectionSet = new Set()

  var values = this.values()
  for (var i = 0; i < values.length; i++) {
    if (otherSet.has(values[i])) {
      intersectionSet.add(values[i])
    }
  }

  return intersectionSet
}

实现差集

差集A-B的意思是：元素只在集合A中存在，集合B中不存在，因此实现也很简单。

this.difference = function (otherSet) {
  var differenceSet = new Set()
  
  var values = this.values()
  for (var i = 0; i < values.length; i++) {
    if (!otherSet.has(values[i])) {
      differenceSet.add(values[i])
    }
  }
  
  return differenceSet
}

实现子集

数学中A是B的子集意味着A中的所有元素都存在于B中，按照这个思路实现代码如下

this.subSet = function (otherSet) {
  if (this.size() > otherSet.size()) {
    return false
  } else {
    var values = this.values()

    for (var i = 0; i < values.length; i++) {
      if (!otherSet.has(values[i])) {
        return false
      }
    }
    return true
  }
}

放上源代码，有兴趣的可以看看：

集合的实现－源代码

小结

到目前为止，比较简单的数据结构基本都掌握了，后面就是字典、散列表、树、图以及排序算法了，都是难啃的骨头，但是必须要啃下来。继续加油～

专线服务私有云二分图集合算法最小集合覆盖贪心算法最小集合覆盖遗传算法 webrtc之vad算法

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

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

我的阿里之路+Java面经考点

摘要：我的是忙碌的一年，从年初备战实习春招，年三十都在死磕源码，三月份经历了阿里五次面试，四月顺利收到实习。因为我心理很清楚，我的目标是阿里。所以在收到阿里之后的那晚，我重新规划了接下来的学习计划，将我的短期目标更新成拿下阿里转正。我的2017是忙碌的一年，从年初备战实习春招，年三十都在死磕JDK源码，三月份经历了阿里五次面试，四月顺利收到实习offer。然后五月怀着忐忑的心情开始了蚂蚁金...

姘搁『 2019-08-15 14:42 评论0 收藏0
学习数据结构与算法之链表

摘要：本系列所有文章第一篇文章学习数据结构与算法之栈与队列第二篇文章学习数据结构与算法之链表第三篇文章学习数据结构与算法之集合第四篇文章学习数据结构与算法之字典和散列表第五篇文章学习数据结构与算法之二叉搜索树简单介绍链表链表一种常见的数据结构，可本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数...

jerryloveemily 2019-08-21 11:50 评论0 收藏0
学习数据结构与算法之字典和散列表

摘要：小结实现了字典和哈希表感觉没有想象中那么困难，当然这还是开始。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算法之二叉搜索树字典不是新华字典哦，这里的字典也称作_映射_，是一种数据结构，跟set集合很相似的一种数据结构，都可以用来...

Heier 2019-08-21 11:52 评论0 收藏0
一文掌握关于Java数据结构所有知识点（欢迎一起完善）

摘要：是栈，它继承于。满二叉树除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。没有键值相等的节点。这是数据库选用树的最主要原因。在我们学习Java的时候，很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况（我本人之前就很迷茫）。所以，我决定通过这个开源平台来帮助一些有需要的人，通过下面的内容，你会掌握系统的Java学习以及面试的相关知识。本来是想通过Gitbook的...

keithxiaoy 2019-08-15 15:54 评论0 收藏0