Fork me on GitHub

集合

algorithm/set/set-banner

集合(Set)是一种包含不同元素的数据结构。集合中的元素称为成员,集合的两个最重要的特性是:首先,集合中的成员是无序的;其次,集合中不允许相同成员的存在。

集合的定义

  • 不包含任何成员的集合称为空集{},全集则是包含一切可能成员的集合。
  • 如何两个集合的成员完全相同,则称两个集合相等。
  • 如果一个集合中所有的成员都属于另外一个集合,则前一集合称为后一个集合的子集。

集合的操作

对集合的操作基本是下面三种:

  1. 并集: 将两个集合中的成员进行合并,得到一个新的集合。
  2. 交集: 两集合中共同存在的成员组成一个新的集合。
  3. 差集: 属于一个集合而不属于另一个集合的成员组成的集合。
  4. 子集: 验证一个给定集合是否是另一个集合的子集。

创建集合类

这里还是使用构造函数进行创建集合类:

1
2
3
function Set() {
// some code here ...
}

这里我们将使用对象来表示集合var items = {},集合的键-值是相同的。当然,你也可以使用数组来表示,但是不够直观。而使用对象一个好处是,javascript的对象不允许一个键指向两个不同的属性,保证了集合里的元素都是唯一性的。

完整代码

基本的完整代码如下:

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
function Set() {
// 选择对象而不是数组来表示集合
var items = {};

//判断是否存在键-值
this.has = function(value) {
return value in items;
};
// 也可以是使用hasOwmProperty来实现
this.has = function(value) {
return items.hasOwnProperty(value);
};

// 添加元素
this.add = function(value) {
if(!this.has(value)){
items[value] = value;
return true;
}
return false;
};

// 提取items对象,返回所有属性,以数组形式返回
// 下面的实现是在现代浏览器才能使用,当然借助babel可以转换成所有浏览器识别的代码
this.values = function() {
return Object.keys(items);
};
// 下面的实现在任何浏览器上可以运行
this.values = function() {
var keys = [];
for(var key in items){
keys.push(key);
}
return keys;
};

// 移除一个元素
this.remove = function(value) {
if(this.has(value)){
delete items[value];
return true;
}
return false;
};

// 清空集合中所有值
this.clear = function() {
items = {};
};

// 获取集合的数量
// 下面的实现是在现代浏览器才能使用,当然借助babel可以转换成所有浏览器识别的代码
this.size = function() {
return Object.keys(items).length;
};
// 所有浏览器都可以运行
this.size = function() {
var count = 0;
for(var prop in items){
if(items.hasOwnProperty(prop)){
++count;
}
return count;
}
};

// 并集
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;
};

// 交集
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;
};

// 差集
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;
};

// 子集
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;
}
};
}

更多的代码请查看https://github.com/reng99/algorithm

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)