集合(set)是一种包含不同元素的数据结构。集合中的元素称为成员。集合具有两个重要特性: (1)集合中的成员是无序的 (2)集合中不允许相同成员存在 当想创建一个数据结构,用来保存一些独一无二的元素时,比如一段文本中用到的单词,集合就变得非常有用。
集合是由一组无序但彼此之间有一定相关性的成员构成的,每个成员在集合中只能出现一次。在数学上,用大括号将一组成员括起来表示集合,比如:{0,1,2,3}
。其成员的顺序是任意的,因此上述集合也可写为:{0,2,1,3}
(1)不包含任何成员的集合称为空集,全集则是包含一切可能成员的集合; (2)如果两个集合的成员完全相同,则称两个集合相等; (3)如果一个集合中所有的成员都属于另外一个集合,则前一集合称为后一集合的子集。
并集: 将两个集合中的成员进行合并,得到一个新集合。 交集: 两个集合中共同存在的成员组成一个新的集合。 补集: 属于一个集合而不属于另一个集合的成员组成的集合。
Set类的实现基于数组,数组用来存储数据。
/**
* 构造函数
* 基于数组存储数据
* @constructor
*/
function Set(){
this.dataList = [];
}
Set.prototype = {
/* 修正constructor */
constructor: Set,
/* 显示当前集合 */
show: function(){
return this.dataList;
},
/* 返回集合元素个数 */
size: function(){
return this.dataList.length;
},
/* 判断集合中是否存在某成员 */
contains: function(data){
return this.dataList.indexOf(data) > -1 ? true : false;
},
/* 添加元素 */
add: function(data){
if(!this.contains(data)){
// 不存在,插入元素,并返回true
this.dataList.push(data);
return true;
}
// 存在,返回false
return false;
},
/* 删除元素 */
remove: function(data){
var index = this.dataList.indexOf(data);
if(index > -1){
// 存在当前数据,则删除并返回true
this.dataList.splice(index, 1);
return true;
}
// 不存在返回false
return false;
}
};
测试:
var set = new Set();
set.add("ligang"); // true
set.add("lg"); // true
set.add("ligang"); // false
set.size(); // 2
set.remove("lg"); // true
set.show(); // ["ligang"]
补充:关于修正construtor问题,请查看–面向对象的程序设计
首先将第一个集合的成员加入到一个临时集合,然后检查第二个集合的成员是否也同时属于第一个集合。如果属于,则跳过该成员,否则插入临时集合。注意这里不能简单的使用Array的concat方法,因为集合要保证成员的唯一性!!!
/* 并集 */
Set.prototype.union = function(set){
// 临时集合,确保类型
var tempSet = new Set();
for(var i = 0, len = this.size(); i < len; i++){
tempSet.add(this.dataList[i]);
}
for(var i = 0, len = set.size(); i < len; i++){
var data = set.dataList[i];
if(!tempSet.contains(data)){
tempSet.add(data);
}
}
return tempSet;
};
测试:
var set1 = new Set();
set1.add("ligang");
set1.add("lee");
var set2 = new Set();
set2.add("ligang");
set2.add("gang");
var newSet = set1.union(set2);
newSet.show(); // ["ligang", "lee", "gang"]
补充:上述将第一个集合添加到临时集合没有基于存储数据的数组做类似this.dataList.concat()
的深拷贝,是为了使tempSet为Set类型,继承其相应的方法。
当第一个集合的成员也属于第二个集合时,编将该成员加入一个新集合。
/* 交集 */
Set.prototype.intersect = function(set){
var tempSet = new Set();
for(var i = 0, len = this.size(); i < len; i++){
var data = this.dataList[i];
if(set.contains(data)){
tempSet.add(data);
}
}
return tempSet;
};
测试:
var set1 = new Set();
set1.add("ligang");
set1.add("lee");
var set2 = new Set();
set2.add("ligang");
set2.add("gang");
set1.intersect(set2).show(); // ["ligang"]
首先判断该集合的长度是否小于待比较集合,若大于直接返回false;当该集合小于待比较集合时,再判断该集合成员是否都属于待比较集合。
Set.prototype.subset = function(set){
if(this.size() > set.size()) {
return false;
}
for(var i = 0, len = this.size(); i < len; i++){
// 如果存在不包含的成员,直接结束循环,返回false
if(!set.contains(this.dataList[i])){
return false;
}
}
return true;
};
测试:
var set1 = new Set();
set1.add("ligang");
set1.add("lee");
var set2 = new Set();
set2.add("ligang");
set2.add("gang");
set1.subset(set2); // false
set.subset(set1.union(set2)); // true
set1.intersect(set2).subset(set1); // true
补充:一个集合是其与任何集合并集的子集;与任何集合的交集都是该集合的子集。
返回包含在第一个集合,但是不属于第二个集合的成员
/* 补集 */
Set.prototype.difference = function(set){
var tempSet = new Set();
for(var i = 0, len = this.size(); i < len; i++){
var data = this.dataList[i];
if(!set.contains(data)){
tempSet.add(data);
}
}
return tempSet;
};
测试:
var set1 = new Set();
set1.add("ligang");
set1.add("lee");
var set2 = new Set();
set2.add("ligang");
set2.add("gang");
set1.difference(set2).show(); // ["lee"]
至此,JavaScript实现数据结构“集合”所有方法都列举完善!!!