集合的定义与实现
我们先来看看集合的几个定义:
• 不包含任何成员的集合称为空集,全集则是包含一切可能成员的集合。
• 如果两个集合的成员完全相同,则称两个集合相等。
• 如果一个集合中所有的成员都属于另外一个集合,则前一集合称为后一集合的子集。
我们再来看看集合的操作:
• 并集将两个集合中的成员进行合并,得到一个新集合。
• 交集两个集合中共同存在的成员组成一个新的集合。
• 补集属于一个集合而不属于另一个集合的成员组成的集合。
好了,现在我们要开始实现集合了。Set类依然基于数组,数组用来存储数据。
function Set() {
this.dataStore = [];
this.add = add;
this.remove = remove;
this.size = size;
this.union = union;
this.intersect = intersect;
this.subset = subset;
this.difference = difference;
this.show = show;
}
//我们知道set中不能存在重复值,所以add函数需要首先检查数组中是否已存在该元素
function add(data) {
if (this.dataStore.indexOf(data) < 0) {
this.dataStore.push(data);
return true;
}
else {
return false;
}
}
//remove则要先检查是否存在,存在再删除
function remove(data) {
var pos = this.dataStore.indexOf(data);
if (pos > -1) {
this.dataStore.splice(pos,1);
return true;
}
else {
return false;
}
}
function show() {
return this.dataStore;
}
function contains(data) {
if (this.dataStore.indexOf(data) > -1) {
return true;
}
else {
return false;
}
}
//并集
function union(set) {
var tempSet = new Set();
for (var i = 0; i < this.dataStore.length; ++i) {
tempSet.add(this.dataStore[i]);
}
for (var i = 0; i < set.dataStore.length; ++i) {
if (!tempSet.contains(set.dataStore[i])) {
tempSet.dataStore.push(set.dataStore[i]);
}
}
return tempSet;
}
//交集
function intersect(set) {
var tempSet = new Set();
for (var i = 0; i < this.dataStore.length; ++i) {
if (set.contains(this.dataStore[i])) {
tempSet.add(this.dataStore[i]);
}
}
return tempSet;
}
//子集
function subset(set) {
if (this.size() > set.size()) {
return false;
}
else {
for (var member in this.dataStore) {
if (!set.contains(member)) {
return false;
}
}
}
return true;
}
function size() {
return this.dataStore.length;
}
//属于第一个集合,但不属于第二个集合
function difference(set) {
var tempSet = new Set();
for (var i = 0; i < this.dataStore.length; ++i) {
if (!set.contains(this.dataStore[i])) {
tempSet.add(this.dataStore[i]);
}
}
return tempSet;
}