数据结构-集合

集合是由一组无序且唯一(即不重复)的项组成的。集合可以看成一个既没有重复元素,又没有顺序概念的数组。

创建一个集合

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
function Set(){
var items = {};
// 如果值在集合中,返回true;否则返回false
this.has = function(value){
return items.hasOwnProperty(value);
};
// 向集合中添加一个新的项
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(){
return Object.keys(items);
};
}

集合操作

并集

并集:x(元素)存在于A中,或存在于B中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function Set(){
// ...
this.union = function(otherSet){
var unionSet = new Set();
var values = this.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
values = otherSet.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
return unionSet;
};
}

交集

并集:x(元素)存在于A中,且存在于B中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function Set(){
// ...
this.intersection = function(otherSet){
var intersectionSet = new Set();
var values = this.values();
for (var i = 0; i < values.length; i++) {
if (otherSet.has(values[i])) {
intersectionSet.add(values[i]);
}
}
return intersectionSet;
};
}

差集

差集:x(元素)存在于A中,且x不存在于B中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function Set() {
// ...
this.difference = function(otherSet){
var differenceSet = new Set();
var values = this.values();
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
differenceSet.add(values[i]);
}
}
return differenceSet;
};
}

子集

子集:集合A中的每一个x(元素),也需要存在于B中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function Set() {
// ...
this.subset = function(otherSet){
if (this.size() > otherSet.size()) {
return false;
} else {
var values = this.values();
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
return false;
}
}
return true;
}
};
}