Gitlib

Enjoy Yourself, Enjoy Life.

0%

数据结构之集合

发表于 分类于

集合

集合（Set)是一种无序的、不重复的元素序列。常用方法:

  • 添加元素
  • 删除元素
  • 判断元素是否在集合中
  • 集合长度
  • 子集判断
  • 求并集
  • 求交集
  • 求补集

定义集合

1
2
3
function Set() {
	this.data = [];
}

添加元素

1
2
3
4
5
6
7
8
9
// 添加元素
this.add = function(data) {
	// 判断元素是否存在，集合的元素是不重复的
	if (this.data.indexOf(data) < 0) {
		this.data.push(data);
		return true;
	}
	return false;
}

删除元素

1
2
3
4
5
6
7
8
9
// 删除元素
this.remove = function(data) {
	var pos = this.data.indexOf(data);
	if (pos > -1) {
		this.data.splice(pos, 1);
		return true;
	}
	return false;
}

判断元素是否在集合中

1
2
3
4
5
6
7
8
// 判断元素是否在集合中
this.contains = function(data) {
	if (this.data.indexOf(data) > -1) {
		return true;
	} else {
		return false;
	}
}

集合长度

1
2
3
4
// 集合长度
this.size = function() {
	return this.data.length;
}

子集判断

如果集合A的任意一个元素都是集合B的元素，那么集合A称为集合B的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
this.subset = function(set) {
	if (this.size() > set.size()) {
		return false;
	} else {
		for (var i=0; i < this.data.length; i++) {
			if (!set.contains(this.data[i])) {
				return false;
			}
		}
	}

	return true;
}

求并集

给定两个集合A，B，把他们所有的元素合并在一起组成的集合，叫做集合A与集合B的并集，记作A∪B，读作A并B。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 求合集
this.union = function(set) {
	// 定义一个临时空集合
	var tempSet = new Set();

	for (var i = 0; i < this.data.length; i++) {
		tempSet.add(this.data[i]);
	}

	for (var i = 0; i < set.data.length; i++) {
		if (!tempSet.contains(set.data[i])) {
			tempSet.add(set.data[i]);
		}
	}

	return tempSet;
}

求交集

集合论中，设A，B是两个集合，由所有属于集合A且属于集合B的元素所组成的集合，叫做集合A与集合B的交集（intersection），记作A∩B。

1
2
3
4
5
6
7
8
9
this.intersect = function(set) {
	var tempSet = new Set();
	for (var i = 0; i < this.data.length; i++) {
		if (set.contains(this.data[i])) {
			tempSet.add(this.data[i]);
		}
	}
	return tempSet;
}

求补集

1
2
3
4
5
6
7
8
9
this.difference = function(set) {
	var tempSet = new Set();
	for (var i = 0; i < this.data.length; i++) {
		if (!set.contains(this.data[i])) {
			tempSet.add(this.data[i]);
		}
	}
	return tempSet;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 集合

function Set() {
	this.data = [];

	// 添加元素
	this.add = function(data) {
		if (this.data.indexOf(data) < 0) {
			this.data.push(data);
			return true;
		}

		return false;
		
	}	

	// 删除元素
	this.remove = function(data) {
		var pos = this.data.indexOf(data);
		if (pos > -1) {
			this.data.splice(pos, 1);
			return true;
		}
		return false;
	}

	// 判断元素是否在集合中
	this.contains = function(data) {
		if (this.data.indexOf(data) > -1) {
			return true;
		} else {
			return false;
		}
	}

	// 集合长度
	this.size = function() {
		return this.data.length;
	}

	this.toString = function() {
		return this.data.join(',');
	}

	// 求合集
	this.union = function(set) {
		// 定义一个临时空集合
		var tempSet = new Set();

		for (var i = 0; i < this.data.length; i++) {
			tempSet.add(this.data[i]);
		}

		for (var i = 0; i < set.data.length; i++) {
			if (!tempSet.contains(set.data[i])) {
				tempSet.add(set.data[i]);
			}
		}

		return tempSet;
	}

	// 求交集
	this.intersect = function(set) {
		var tempSet = new Set();
		for (var i = 0; i < this.data.length; i++) {
			if (set.contains(this.data[i])) {
				tempSet.add(this.data[i]);
			}
		}
		return tempSet;
	}

	// 是否是子集
	this.subset = function(set) {
		if (this.size() > set.size()) {
			return false;
		} else {
			for (var i=0; i < this.data.length; i++) {
				if (!set.contains(this.data[i])) {
					return false;
				}
			}
		}

		return true;
	}

	// 求补集
	// 由属于A而不属于B的元素组成的集合，称为B关于A的相对补集
	this.difference = function(set) {
		var tempSet = new Set();
		for (var i = 0; i < this.data.length; i++) {
			if (!set.contains(this.data[i])) {
				tempSet.add(this.data[i]);
			}
		}
		return tempSet;
	}
}