周亚博的个人博客

  • 首页
  • 盛夏光年
  • 陪风去荡
  • 布响丸啦
我频繁记录着 因为生活值得
  1. 首页
  2. 陪风去荡
  3. 正文

数据结构——集合

2022-08-17 56点热度 0人点赞 0条评论

一、集合结构

集合中比较常见的实现方式就是哈希表,集合通常是由一组无序的,不能重复的元素构成

集合可以看作一个特殊的数组,没有顺序意味着不能通过下标进行访问,不能重复说明相同的对象集合中只能存在一份

二、集合中常见的方法

add(value):向集合添加一个新的项。

remove(value):从集合移除一个值。

has(value):如果值在集合中,返回true,否则返回false。

clear():移除集合中的所有项。

size():返回集合所包含元素的数量。与数组的length属性类似。

values():返回一个包含集合中所有值的数组。

三、集合的封装

// 封装一个集合类
function Set() {
  // 属性
  this.items = {}
  // add方法
  Set.prototype.add = function (value) {
    // 如果集合中已经存在该元素,拒绝添加
    if (this.has(value)) return false
    this.items[value] = value
    return true
  }
  // has方法
  Set.prototype.has = function (value) {
    return this.items.hasOwnProperty(value)
  }
  // remove方法
  Set.prototype.remove = function (value) {
    // 判断集合中是否包含该元素
    if (!this.has(value)) return false
    delete this.items[value]
    return true
  }

  // clear方法
  Set.prototype.clear = function () {
    this.items = {}
  }
  // size方法
  Set.prototype.size = function () {
    return Object.keys(this.items).length
  }

  // values方法,获取集合中所有的值,返回数组
  Set.prototype.values = function () {
    return Object.keys(this.items)
  }
}

let set = new Set()
console.log(set.add('a'))   // true
console.log(set.add('a'))   // false
console.log(set.add('b'))   // true
console.log(set.add('c'))   // true

console.log(set.remove('c'))  // true
console.log(set.values())     // [ 'a', 'b' ]
console.log(set.remove('c'))  // false

console.log(set.has('c'))   // false

console.log(set.size())     // 2

set.clear()
console.log(set.size())   // 0

四、集合间的操作

  • 并集:返回包含两个集合所有元素的新集合
  • 交集:返回包含两个集合共有元素的新集合
  • 差集:返回包含第一个集合不包含第二个集合的所有元素的集合
  • 子集:一个集合所有元素包含在另一个集合中

image-20220817122731857

代码实现

  // 集合并集操作
  Set.prototype.union = function (otherSet) {
    // 创建一个新的集合
    let unionSet = new Set()
    // 将A集合所有的元素放入新集合中
    let values = this.values()
    for (let i = 0; i < values.length; i++) {
      unionSet.add(values[i])
    }
    // 将B集合中的元素放入新集合中(A中不存在的)
    values = otherSet.values()
    for (let i = 0; i < values.length; i++) {
      unionSet.add(values[i])
    }
    return unionSet
  }

  // 集合交集操作
  Set.prototype.intersection = function (otherSet) {
    // 新建一个空集合
    let intersectionSet = new Set()
    // 逐个取出集合A中的元素,判断B中是否存在
    let values = this.values()
    for (let i = 0; i < values.length; i++) {
      let item = values[i]
      if (otherSet.has(item)) {// 存在则加入新集合
        intersectionSet.add(item)
      }
    }
    return intersectionSet
  }

  // 集合差集操作
  Set.prototype.difference = function (otherSet) {
    // 新建一个空集合
    let differenceSet = new Set()
    // 逐个取出集合A中的元素,判断B中是否存在
    let values = this.values()
    for (let i = 0; i < values.length; i++) {
      let item = values[i]
      if (!otherSet.has(item)) {// 不存在则加入新集合
        differenceSet.add(item)
      }
    }
    return differenceSet
  }

  // 集合的子集判断
  Set.prototype.subSet = function (otherSet) {
    let values = this.values()
    for (let i = 0; i < values.length; i++) {
      if (!otherSet.has(values[i])) return false
    }
    return true
  }

结果验证

let setA = new Set()
setA.add('A')
setA.add('B')
setA.add('C')
let setB = new Set()
setB.add('C')
setB.add('D')
setB.add('E')

// 集合的并集操作
let unionSet = setA.union(setB)
console.log(unionSet.values())    // [ 'A', 'B', 'C', 'D', 'E' ]
// 集合的交集操作
let intersectionSet = setA.intersection(setB)
console.log(intersectionSet.values())   // [ 'C' ]
// 集合的差集操作
let differenceSet = setA.difference(setB)
console.log(differenceSet.values())   // [ 'A', 'B' ]
// 子集的判断
console.log(setA.subSet(setB))   // false
setA.remove('A')
setA.remove('B')
console.log(setA.subSet(setB))    // true
标签: 数据结构 集合
最后更新:2022-08-17

粥呀Bo

所谓惊喜,就是苦苦等候的兔子来了,后面却跟着狼

点赞
< 上一篇
下一篇 >

文章评论

取消回复
目录
  • 一、集合结构
  • 二、集合中常见的方法
  • 三、集合的封装
  • 四、集合间的操作

COPYRIGHT © 2022 zhouyaker.cn. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

陕ICP备2022009272号