读【数据结构与算法】之集合
集合是一种包含不同元素的数据结构。集合中元素称为成员。集合的两个最重要的特性：
-
首先，集合中的成员是无序的；
-
其次，集合中不允许存在相同成员。
集合是由一组无序但彼此又有一定相关性的成员构成的，每一个成员在集合中只能出现一次。
这里列出需要了解的定义：
-
不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。
-
如果两个集合的成员完全相同，那么就称两个集合相等。
-
如果一个集合中所有的成员都属于另外一个集合，那么前一集合称为后一集合的子集。
对集合主要有三种操作：并集、交集以及补集。
下边是集合的基本实现：
/**
* Class Set
* 集合 Set
*/
function Set() {
this.data = []; // 用于存储数据的数组
}
Set.prototype = {
constructor: Set,
/**
* 添加成员
* @param {Any} data 成员
* @return {Boolean} 是否添加成功
*/
add: function add(data) {
if (this.data.indexOf(data) < 0) {
this.data.push(data);
return true;
} else {
return false;
}
},
/**
* 移除成员
* @param {Any} data 成员
* @return {Boolean} 是否移除成功
*/
remove: function remove(data) {
var p = this.data.indexOf(data);
if (p > -1) {
this.data.splice(p, 1);
return true;
} else {
return false;
}
},
/**
* 显示
* @return {Array} 数据
*/
show: function show() {
return this.data;
},
/**
* 是否包含成员
* @param {Any} data 成员
* @return {Boolean} 是否包含
*/
contains: function contains(data) {
return this.data.indexOf(data) > -1 ? true : false;
},
/**
* 两个集合的并集
* @param {Set} set 另一个集合
* @return {Set} 新集合
*/
union: function union(set) {
var retSet = new Set();
for (var i = 0, len = this.data.length; i < len; i++) {
retSet.add(this.data[i]);
}
for (i = 0, len = set.data.length; i < len; i++) {
if (!retSet.contains(set.data[i])) {
retSet.data.push(set.data[i]);
}
}
return retSet;
},
/**
* 两个集合的交集
* @param {Set} set 另一个集合
* @return {Set} 新集合
*/
intersect: function intersect(set) {
var retSet = new Set();
for (var i = 0, len = this.data.length; i < len; i++) {
if (set.contains(this.data[i])) {
retSet.add(this.data[i]);
}
}
return retSet;
},
/**
* 本集合是否是另一个集合的子集
* @param {Set} set 另一个集合
* @return {Boolean} 是否是子集
*/
subset: function subset(set) {
if (this.size() > set.size()) {
return false;
}
for (var i = 0, len = this.data.length; i < len; i++) {
if (!set.contains(this.data[i])) {
return false;
}
}
return true;
},
/**
* 两个集合的补集
* @param {Set} set 另一个集合
* @return {Set} 属于本集合，但是不属于
* 另一个集合的成员组成的集合
*/
difference: function difference(set) {
var retSet = new Set();
for (var i = 0, len = this.data.length; i < len; i++) {
if (!set.contains(this.data[i])) {
retSet.add(this.data[i]);
}
}
return retSet;
},
/**
* 集合大小
* @return {Number} 集合长度
*/
size: function() {
return this.data.length;
}
};
具体运行例子请看demojs实现集合