个人博客

集合

WARNING

集合通常是由一组无序的、不能重复的元素构成，一般用哈希表实现，在 ES6 中的 Set 类就是一个集合类，下面用 JS 的 Object 类实现

集合是特殊的数组

  • 特殊之处在于里面的元素没有顺序，也不能重复
  • 没有顺序意味着不能通过下标值进行访问，不能重复意味着相同的对象在集合中只会存在一份

常用操作

  • add(value)：向集合添加一个新的项
  • remove(value)：从集合中移除一个值
  • has(value)：如果值在集合中，返回 true，否则返回 false
  • clear()：移除集合中的所有项
  • size()：返回集合所包含元素的数量，与数组的 length 属性相似
  • values()：返回一个包含集合中所有值的数组

Set 集合类代码实现

封装

// 封装集合的构造函数
function Set() {
	// 属性
	this.items = {}

	/* 方法 */
	// 1. has方法
	Set.prototype.has = function (value) {
		return this.items.hasOwnProperty(value)
	}

	// 2. add方法
	Set.prototype.add = function (value) {
		// 2.1 判断集合中是否已经包含该元素
		if (this.has(value)) {
			return false
		}
		// 2.2 将元素添加到集合中
		this.items[value] = value // 表示该属性键和值都为value
		return true // 表示添加成功
	}

	// 3. remove方法
	Set.prototype.remove = function (value) {
		// 3.1 判断集合中是否包含该元素
		if (!this.has(value)) {
			return false
		}

		// 3.2 将元素从属性中删除
		delete this.items[value]
		return true
	}

	// 4. clear方法
	Set.prototype.clear = function () {
		// 原来的对象没有引用指向，会被自动回收
		this.items = {}
	}

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

	// 6. values方法：获取集合所有的值
	Set.prototype.values = function () {
		return Object.keys(this.items)
	}
}

测试

// 测试和使用集合类
var set = new Set()

// 1. 测试add方法
console.log(set.add(1)) // true
console.log(set.values()) // ["1"]
set.add(1)
console.log(set.values()) // ["1"]

// 2. 测试values方法
set.add(100)
set.add(200)
console.log(set.values()) // ["1", "100", "200"]

// 3. 测试has方法
console.log(set.has(100)) // true

// 4. 测试remove方法
set.remove(100)
console.log(set.values()) // ["1", "200"]

// 5. 测试size方法
console.log(set.size()) // 2

// 6. 测试clear方法
set.clear()
console.log(set.size()) // 0
console.log(set.values()) // []

集合间的操作

集合间操作汇总

  • 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合
  • 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合
  • 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合
  • 子集：验证一个给定集合是否是另一个集合的子集

set

并集的实现

代码实现

// 7. 并集方法
Set.prototype.union = function (otherSet) {
	// this: 集合对象A
	// otherSet：集合对象B
	// 7.1 创建一个新集合
	var unionSet = new Set()

	// 7.2 将A集合中的所有元素添加到新集合中
	var values = this.values()
	for (var i = 0; i < values.length; i++) {
		unionSet.add(values[i])
	}

	// 7.3 取出B集合中的元素,判断是否需要加到新集合中
	values = otherSet.values()
	for (var i = 0; i < values.length; i++) {
		// 由于集合的add方法已经对重复的元素进行了判断,所以这里可以直接添加
		unionSet.add(values[i])
	}

	// 7.4 返回新集合
	return unionSet
}

过程详解

  • 首先，需要创建一个新的集合 C，用于存储两个集合的并集
  • 其次，遍历集合 A 中所有的值，并添加到新集合中
  • 再次，遍历集合 B 中所有的值，并添加到新集合中
  • 最后，将最终的新集合 C 返回

测试代码

// 7. 测试union方法：求两个集合的并集
// 7.1 创建两个集合，并且添加元素
var setA = new Set()
setA.add("aaa")
setA.add("bbb")
setA.add("ccc")
var setB = new Set()
setB.add("aaa")
setB.add("ddd")
setB.add("eee")
// 7.2 求两个集合的并集
var unionSet = setA.union(setB)
console.log(unionSet.values()) // ["aaa", "bbb", "ccc", "ddd", "eee"]

交集的实现

代码实现

// 8. 交集方法
Set.prototype.intersection = function (otherSet) {
	// this: 集合对象A
	// otherSet：集合对象B
	// 8.1 创建一个新集合
	var intersectionSet = new Set()

	// 8.2 从A中取出一个一个元素，判断是否同时存在于集合B中，存在就放入新集合中
	var values = this.values()
	for (var i = 0; i < values.length; i++) {
		var item = values[i]
		if (otherSet.has(item)) {
			intersectionSet.add(item)
		}
	}

	// 8.3 返回新集合
	return intersectionSet
}

过程详解

  • 首先，创建一个新的集合 C，用于存储两个集合的交集
  • 其次，遍历集合 A 中所有的值，然后判断是否存在于集合 B 中，如果存在就加入到新集合中
  • 最后，将最终的新集合 C 返回

测试代码

// 8. 测试intersection方法：求两个集合的交集
var intersectionSet = setA.intersection(setB)
console.log(intersectionSet.values()) // ["aaa"]

差集的实现

代码实现

// 9. 差集方法
Set.prototype.difference = function (otherSet) {
	// this: 集合对象A
	// otherSet：集合对象B
	// 9.1 创建一个新集合
	var differenceSet = new Set()

	// 9.2 从A中取出一个一个元素，判断是否同时存在于集合B中，不存在B中，就放入新集合中
	var values = this.values()
	for (var i = 0; i < values.length; i++) {
		var item = values[i]
		if (!otherSet.has(item)) {
			differenceSet.add(item)
		}
	}

	// 9.3 返回新集合
	return differenceSet
}

过程详解

  • 首先，创建一个新的集合 C，用于存储两个集合的差集
  • 其次，遍历集合 A 中所有的值，然后判断是否存在于集合 B 中，如果不存在就加入到新集合中
  • 最后，将最终的新集合 C 返回

测试代码

// 9. 测试difference方法：求两个集合的差集
var differenceSet = setA.difference(setB)
console.log(differenceSet.values()) // ["bbb", "ccc"]

子集的实现

代码实现

// 10. 子集
Set.prototype.subset = function (otherSet) {
	// this：集合A
	// otherSet：集合B
	// 遍历集合A中的所有元素，如果发现，集合A中的元素，在集合B中不存在，那么返回false
	// 如果遍历完整个集合A，依然没有返回false，那么就返回true
	let values = this.values()
	for (var i = 0; i < values.length; i++) {
		var item = values[i]
		if (!otherSet.has(item)) {
			return false
		}
	}
	return true
}

过程详解

  • 判断集合 A 中的元素是否都存在于集合 B 中，存在就是子集，返回 true，只要有一个不存在就不是子集，返回 false

测试代码

// 10. 测试subset方法：求两个集合的子集
console.log(setA.subset(setB)) // false
var setC = new Set()
setC.add("aaa")
setC.add("bbb")
console.log(setC.subset(setA)) // true

完整代码

// 封装集合的构造函数
function Set() {
	// 属性
	this.items = {}

	/* 方法 */
	// 1. has方法
	Set.prototype.has = function (value) {
		return this.items.hasOwnProperty(value)
	}

	// 2. add方法
	Set.prototype.add = function (value) {
		// 2.1 判断集合中是否已经包含该元素
		if (this.has(value)) {
			return false
		}
		// 2.2 将元素添加到集合中
		this.items[value] = value // 表示该属性键和值都为value
		return true // 表示添加成功
	}

	// 3. remove方法
	Set.prototype.remove = function (value) {
		// 3.1 判断集合中是否包含该元素
		if (!this.has(value)) {
			return false
		}

		// 3.2 将元素从属性中删除
		delete this.items[value]
		return true
	}

	// 4. clear方法
	Set.prototype.clear = function () {
		// 原来的对象没有引用指向，会被自动回收
		this.items = {}
	}

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

	// 6. values方法：获取集合所有的值
	Set.prototype.values = function () {
		return Object.keys(this.items)
	}

	// 7. 并集方法
	Set.prototype.union = function (otherSet) {
		// this: 集合对象A
		// otherSet：集合对象B
		// 7.1 创建一个新集合
		var unionSet = new Set()

		// 7.2 将A集合中的所有元素添加到新集合中
		var values = this.values()
		for (var i = 0; i < values.length; i++) {
			unionSet.add(values[i])
		}

		// 7.3 取出B集合中的元素,判断是否需要加到新集合中
		values = otherSet.values()
		for (var i = 0; i < values.length; i++) {
			// 由于集合的add方法已经对重复的元素进行了判断,所以这里可以直接添加
			unionSet.add(values[i])
		}

		// 7.4 返回新集合
		return unionSet
	}

	// 8. 交集方法
	Set.prototype.intersection = function (otherSet) {
		// this: 集合对象A
		// otherSet：集合对象B
		// 8.1 创建一个新集合
		var intersectionSet = new Set()

		// 8.2 从A中取出一个一个元素，判断是否同时存在于集合B中，存在就放入新集合中
		var values = this.values()
		for (var i = 0; i < values.length; i++) {
			var item = values[i]
			if (otherSet.has(item)) {
				intersectionSet.add(item)
			}
		}

		// 8.3 返回新集合
		return intersectionSet
	}

	// 9. 差集方法
	Set.prototype.difference = function (otherSet) {
		// this: 集合对象A
		// otherSet：集合对象B
		// 9.1 创建一个新集合
		var differenceSet = new Set()

		// 9.2 从A中取出一个一个元素，判断是否同时存在于集合B中，不存在B中，就放入新集合中
		var values = this.values()
		for (var i = 0; i < values.length; i++) {
			var item = values[i]
			if (!otherSet.has(item)) {
				differenceSet.add(item)
			}
		}

		// 9.3 返回新集合
		return differenceSet
	}

	// 10. 子集
	Set.prototype.subset = function (otherSet) {
		// this：集合A
		// otherSet：集合B
		// 遍历集合A中的所有元素，如果发现，集合A中的元素，在集合B中不存在，那么返回false
		// 如果遍历完整个集合A，依然没有返回false，那么就返回true
		let values = this.values()
		for (var i = 0; i < values.length; i++) {
			var item = values[i]
			if (!otherSet.has(item)) {
				return false
			}
		}
		return true
	}
}

// 测试和使用集合类
var set = new Set()

// 1. 测试add方法
console.log(set.add(1)) // true
console.log(set.values()) // ["1"]
set.add(1)
console.log(set.values()) // ["1"]

// 2. 测试values方法
set.add(100)
set.add(200)
console.log(set.values()) // ["1", "100", "200"]

// 3. 测试has方法
console.log(set.has(100)) // true

// 4. 测试remove方法
set.remove(100)
console.log(set.values()) // ["1", "200"]

// 5. 测试size方法
console.log(set.size()) // 2

// 6. 测试clear方法
set.clear()
console.log(set.size()) // 0
console.log(set.values()) // []

// 7. 测试union方法：求两个集合的并集
// 7.1 创建两个集合，并且添加元素
var setA = new Set()
setA.add("aaa")
setA.add("bbb")
setA.add("ccc")
var setB = new Set()
setB.add("aaa")
setB.add("ddd")
setB.add("eee")
// 7.2 求两个集合的并集
var unionSet = setA.union(setB)
console.log(unionSet.values()) // ["aaa", "bbb", "ccc", "ddd", "eee"]

// 8. 测试intersection方法：求两个集合的交集
var intersectionSet = setA.intersection(setB)
console.log(intersectionSet.values()) // ["aaa"]

// 9. 测试difference方法：求两个集合的差集
var differenceSet = setA.difference(setB)
console.log(differenceSet.values()) // ["bbb", "ccc"]

// 10. 测试subset方法：求两个集合的子集
console.log(setA.subset(setB)) // false
var setC = new Set()
setC.add("aaa")
setC.add("bbb")
console.log(setC.subset(setA)) // true