详解编程语言中的集合结构
集合
几乎每种编程语言中, 都有集合结构.
几乎比较常见的实现方式时哈希表(后续会学习), 我们这里来实现一个封装的集合类.
dee2ad3a3bf74ba99bcc31beb588866e.jpg
一. 集合介绍
我们先来简单认识一下集合的特点.
集合的特点
· 集合通常是由一组无序的, 不能重复的元素构成.
i. 和数学中的集合名词比较相似, 但是数学中的集合范围更大一些, 也允许集合中的元素重复.
ii. 在计算机中, 集合通常表示的结构中元素是不允许重复的.
· 看成一种特殊的数组
i. 其实集合你可以将它看成一种特殊的数组.
ii. 特殊之处在于里面的元素没有顺序, 也不能重复.
iii. 没有顺序意味着不能通过下标值进行访问, 不能重复意味着相同的对象在集合中只会存在一份.
集合的实现
· 我们要像之前学习其他数据结构一样, 来学习一下集合.
· 最主要的学习方式就是封装一个属于自己的集合类, 并且可以通过该类进行集合相关的操作.
· 2011年6月份发布的ES5中已经包含了Array类
· 2015年6月份发布的ES6中包含了Set类, 所以其实我们可以不封装, 直接使用它.
· 但是这里, 为了明确集合的内部实现机制, 我们这里还是自己来封装一下这个Set类.
二. 封装集合
像前面封装其他数据类型一样, 我们也来封装一下集合类(Set类)
创建集合类
·
我们先来封装一个Set类
·
·
i. // 封装集合的构造函数
ii. function Set() {
iii. // 使用一个对象来保存集合的元素
iv. this.items = {}
v.
vi. // 集合的操作方法
vii. }
·
代码解析:
·
· 代码就是封装了一个集合的构造函数.
· 在集合中, 添加了一个items属性, 用于保存之后添加到集合中的元素. 因为Object的keys本身就是一个集合.
· 后续我们给集合添加对应的操作方法.
操作的方法
·
集合有哪些常见的操作方法呢?
·
· add(value)：向集合添加一个新的项。
· remove(value)：从集合移除一个值。
· has(value)：如果值在集合中，返回true，否则返回false。
· clear()：移除集合中的所有项。
· size()：返回集合所包含元素的数量。与数组的length属性类似。
· values()：返回一个包含集合中所有值的数组。
· 还有一些集合其他相关的操作, 暂时用不太多, 这里暂不封装.
·
我们来一个个实现这些方法, 相对都比较简单.
·
·
has(value)方法
·
·
i. // 判断集合中是否有某个元素
ii. Set.prototype.has = function (value) {
iii. return this.items.hasOwnProperty(value)
iv. }
·
add方法
·
·
i. // 向集合中添加元素
ii. Set.prototype.add = function (value) {
iii. // 1.判断集合中是否已经包含了该元素
iv. if (this.has(value)) return false
v.
vi. // 2.将元素添加到集合中
vii. this.items[value] = value
viii. return true
ix. }
·
remove方法
·
·
i. // 从集合中删除某个元素
ii. Set.prototype.remove = function (value) {
iii. // 1.判断集合中是否包含该元素
iv. if (!this.has(value)) return false
v.
vi. // 2.包含该元素, 那么将元素删除
vii. delete this.items[value]
viii. return true
ix. }
·
clear方法
·
·
i. // 清空集合中所有的元素
ii. Set.prototype.clear = function () {
iii. this.items = {}
iv. }
·
size方法
·
·
i. // 获取集合的大小
ii. Set.prototype.size = function () {
iii. return Object.keys(this.items).length
iv.
v. /*
vi. 考虑兼容性问题, 使用下面的代码
vii. var count = 0
viii. for (var value in this.items) {
ix. if (this.items.hasOwnProperty(value)) {
x. count++
xi. }
xii. }
xiii. return count
xiv. */
xv. }
·
values方法
·
·
i. // 获取集合中所有的值
ii. Set.prototype.values = function () {
iii. return Object.keys(this.items)
iv.
v. /*
vi. 考虑兼容性问题, 使用下面的代码
vii. var keys = []
viii. for (var value in this.items) {
ix. keys.push(value)
x. }
xi. return keys
xii. */
xiii. }
集合的使用
·
我们来简单使用和测试一下封装的集合类
·
·
i. // 测试和使用集合类
ii. var set = new Set()
iii.
iv. // 添加元素
v. set.add(1)
vi. alert(set.values()) // 1
vii. set.add(1)
viii. alert(set.values()) // 1
ix.
x. set.add(100)
xi. set.add(200)
xii. alert(set.values()) // 1,100,200
xiii.
xiv. // 判断是否包含元素
xv. alert(set.has(100)) // true
xvi.
xvii. // 删除元素
xviii. set.remove(100)
xix. alert(set.values()) // 1, 200
xx.
xxi. // 获取集合的大小
xxii. alert(set.size()) // 2
xxiii. set.clear()
xxiv. alert(set.size()) // 0
三. 完整代码
最后, 我们还是给出集合的完整代码
完整代码
·
·
i. // 封装集合的构造函数
ii. function Set() {
iii. // 使用一个对象来保存集合的元素
iv. this.items = {}
v.
vi. // 集合的操作方法
vii. // 判断集合中是否有某个元素
viii. Set.prototype.has = function (value) {
ix. return this.items.hasOwnProperty(value)
x. }
xi.
xii. // 向集合中添加元素
xiii. Set.prototype.add = function (value) {
xiv. // 1.判断集合中是否已经包含了该元素
xv. if (this.has(value)) return false
xvi.
xvii. // 2.将元素添加到集合中
xviii. this.items[value] = value
xix. return true
xx. }
xxi.
xxii. // 从集合中删除某个元素
xxiii. Set.prototype.remove = function (value) {
xxiv. // 1.判断集合中是否包含该元素
xxv. if (!this.has(value)) return false
xxvi.
xxvii. // 2.包含该元素, 那么将元素删除
xxviii. delete this.items[value]
xxix. return true
xxx. }
xxxi.
xxxii. // 清空集合中所有的元素
xxxiii. Set.prototype.clear = function () {
xxxiv. this.items = {}
xxxv. }
xxxvi.
xxxvii. // 获取集合的大小
xxxviii. Set.prototype.size = function () {
xxxix. return Object.keys(this.items).length
xl.
xli. /*
xlii. 考虑兼容性问题, 使用下面的代码
xliii. var count = 0
xliv. for (var value in this.items) {
xlv. if (this.items.hasOwnProperty(value)) {
xlvi. count++
xlvii. }
xlviii. }
xlix. return count
l. */
li. }
lii.
liii. // 获取集合中所有的值
liv. Set.prototype.values = function () {
lv. return Object.keys(this.items)
lvi.
lvii. /*
lviii. 考虑兼容性问题, 使用下面的代码
lix. var keys = []
lx. for (var value in this.items) {
lxi. keys.push(value)
lxii. }
lxiii. return keys
lxiv. */
lxv. }
lxvi. }
