数据结构与算法之集合
最后更新:
阅读时间: 2
min
前言
集合是一种包含不同元素的数据结构，集合中的元素称之为成员。集合有两个重要的特性，一是集合中的成员是无序的，其次集合中不存在相同的成员。
关于集合
不包含任何成员的集合称为空集，全集则是包含可能一切成员的集合。
如果两个集合的成员完全相等，则两个集合相等。
如果一个集合的所有成员都属于另一个集合，则认为这个集合是另一个集合的子集。
并集-将两个集合的成员合并的操作。
交集-将两个集合共有的成员组成一个新的集合。
补集-属于一个集合而不属于另一个集合的成员。
实现集合
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
| class MySet {
data = <any>[]
get size() {
return this.data.length
}
add(element: any) {
if (this.data.indexOf(element) > -1) {
return false
}
this.data.push(element)
}
remove(element: any) {
const index = this.data.indexOf(element)
if (index > -1) {
this.data.splice(index, 1)
return true
}
return false
}
contains(element: any) {
if (this.data.indexOf(element) > -1) {
return true
}
return false
}
uinon(set: MySet) {
const newSet = new MySet()
this.data.forEach((e: any) => newSet.add(e))
for (let index = 0; index < set.data.length; index++) {
const ele = set.data[index]
if (!newSet.contains(ele)) {
newSet.add(ele)
}
}
return newSet
}
intersect(set: MySet) {
const newSet = new MySet()
this.data.forEach((ele: any) => {
if (set.contains(ele)) {
newSet.add(ele)
}
})
return newSet
}
subset(set: MySet) {
if (this.size > set.size) {
return false
} else {
for (let index = 0; index < this.data.length; index++) {
const element = this.data[index]
if (!set.contains(element)) {
return false
}
}
return true
}
}
difference(set: MySet) {
const newSet = new MySet()
for (let index = 0; index < this.data.length; index++) {
const element = this.data[index]
if (!set.contains(element)) {
newSet.add(element)
}
}
return newSet
}
show() {
return this.data.forEach((e: any) => console.log(e))
}
}
|
测试
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
| const setOne = new MySet()
setOne.add('a')
setOne.add('b')
setOne.add('c')
const setTwo = new MySet()
setTwo.add('c')
setTwo.add('d')
setTwo.add('e')
setTwo.add('f')
const setThree = setOne.uinon(setTwo)
console.log('合集')
setThree.show()
const setFour = setOne.intersect(setTwo)
console.log('交集')
setFour.show()
const isSubset = setOne.subset(setTwo)
console.log('是否是补集', isSubset)
const setSix = setOne.difference(setTwo)
console.log('查看集合中不同的成员')
setSix.show()
|
