数据结构之集合

集合

集合(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;
}
}
有用就打赏一下作者吧!