我们已经学习了数组（列表）、栈、队列和链表（及其变种）等顺序数据结构，接下来我们再学习集合这一数据结构。
集合是由一组无序且唯一（即不能重复）的项组成，这种数据结构使用了与有限集合相同的数学概念，应用在计算机科学的数据结构中。
ES6已经提供了集合这种数据结构Set，接下来我们也实现这一数据结构，这次我们换一种思路，使用JS中的对象而不是数组来表示集合。
function Set() {
let items = {}
this.has = function (value) {
return value in items
}
this.add = function (value) {
if (!this.has(value)) {
items[value] = value
return true
}
return false
}
this.remove = function (value) {
if (this.has(value)) {
delete items[value]
return true
}
return false
}
this.clear = function () {
items = []
}
this.size = function () {
return Object.keys(items).length
}
this.values = function () { // 提取items对象的所有属性，以数组形式返回
return Object.keys(items)
}
}
let set = new Set()
set.add(1)
console.log(set.values()) // ['1']
console.log(set.has(1)) // true
console.log(set.size()) // 1
set.add(2)
console.log(set.values()) // ['1' '2']
console.log(set.has(2)) // true
console.log(set.size()) // 2
set.remove(1)
console.log(set.values()) // ['2']
set.remove(2)
console.log(set.values()) // []
集合操作
对集合可以进行并集、交集、差集、子集等操作。
this.union = function (otherSet) { // 并集
let unionSet = new Set()
let values = this.values()
for (let i = 0; i < values.length; i++) {
unionSet.add(values[i])
}
values = otherSet.values()
for (let i = 0; i < values.length; i++) {
unionSet.add(values[i])
}
return unionSet
}
我们来测试一下：
let set1 = new Set()
set1.add(1)
set1.add(2)
set1.add(3)
let set2 = new Set()
set2.add(3)
set2.add(4)
set2.add(5)
set2.add(6)
console.log(set1.union(set2).values()) // [ '1', '2', '3', '4', '5', '6' ]
this.intersection = function (otherSet) { // 交集
let intersectionSet = new Set()
let values = this.values()
for (let i = 0; i < values.length; i++) {
if (otherSet.has(values[i])) {
intersectionSet.add(values[i])
}
}
return intersectionSet
}
let set1 = new Set()
set1.add(1)
set1.add(2)
set1.add(3)
let set2 = new Set()
set2.add(2)
set2.add(3)
set2.add(4)
console.log(set1.intersection(set2).values()) // [ '2', '3' ]
this.difference = function (otherSet) { // 差集
let differenceSet = new Set()
let values = this.values()
for (let i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
differenceSet.add(values[i])
}
}
return differenceSet
}
et set1 = new Set()
set1.add(1)
set1.add(2)
set1.add(3)
let set2 = new Set()
set2.add(2)
set2.add(3)
set2.add(4)
console.log(set1.difference(set2).values()) // [ '1' ]
this.subset = function (otherSet) { // 是否为子集
if (this.size() > otherSet.size()) {
return false
} else {
let values = this.values()
for (let i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
return false
}
}
return true
}
}
let set1 = new Set()
set1.add(1)
set1.add(2)
let set2 = new Set()
set2.add(1)
set2.add(2)
set2.add(3)
let set3 = new Set()
set3.add(2)
set3.add(3)
set3.add(4)
console.log(set1.subset(set2)) // true
console.log(set1.subset(set3)) // false
完整代码：
function Set() {
let items = {}
this.has = function (value) {
return value in items
}
this.add = function (value) {
if (!this.has(value)) {
items[value] = value
return true
}
return false
}
this.remove = function (value) {
if (this.has(value)) {
delete items[value]
return true
}
return false
}
this.clear = function () {
items = []
}
this.size = function () {
return Object.keys(items).length
}
this.values = function () { // 提取items对象的所有属性，以数组形式返回
return Object.keys(items)
}
this.union = function (otherSet) { // 并集
let unionSet = new Set()
let values = this.values()
for (let i = 0; i < values.length; i++) {
unionSet.add(values[i])
}
values = otherSet.values()
for (let i = 0; i < values.length; i++) {
unionSet.add(values[i])
}
return unionSet
}
this.intersection = function (otherSet) { // 交集
let intersectionSet = new Set()
let values = this.values()
for (let i = 0; i < values.length; i++) {
if (otherSet.has(values[i])) {
intersectionSet.add(values[i])
}
}
return intersectionSet
}
this.difference = function (otherSet) { // 差集
let differenceSet = new Set()
let values = this.values()
for (let i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
differenceSet.add(values[i])
}
}
return differenceSet
}
this.subset = function (otherSet) { // 是否为子集
if (this.size() > otherSet.size()) {
return false
} else {
let values = this.values()
for (let i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
return false
}
}
return true
}
}
}
let set1 = new Set()
set1.add(1)
set1.add(2)
let set2 = new Set()
set2.add(1)
set2.add(2)
set2.add(3)
let set3 = new Set()
set3.add(2)
set3.add(3)
set3.add(4)
console.log(set1.subset(set2))
console.log(set1.subset(set3))
