集合 | zbs's Blog

集合的定义

集合是由一组无序且唯一（即不能重复）的项组成的。这个数据结构使用了与有限集合相同的数学概念。

与集合相关的数学概念

空集，不包含任何元素的集合
并集：对于给定的两个集合，返回包含两个集合中所有元素的新集合。
交集：对于给定的两个集合，返回包含两个集合中公有元素的新集合。
差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。
子集：验证一个给定集合是否是另外集合的子集。

集合的方法

add(value)：向集合添加一个新的项。

remove(value)：从集合移除一个值。

has(value)：如果值在集合中，返回true，否则返回false。

clear()：移除集合中的所有项。

size()：返回集合所包含元素的数量。与数组的length属性类似。

values()：返回一个包含集合中所有值的数组。

union(otherSet): 返回两个集合的并集

intersection(otherSet): 返回两个集合的交集

difference(otherSet): 返回两个集合的差集

subset(otherSet): 判断该集合是否为传入集合的子集

集合的创建（觉得这个实现有错误）

function Set () {
	// 使用对象来表示集合
	var items = {} ;

	// 方法
	this.has = function ( value ) {
		return items.hasOwnProperty ( value ) ;
	} ;

	this.add = function ( value ) {
		if ( ! this.has ( value ) ) {
			items [ value ] = value ;
			// 【疑惑】items[value] 有错误
			// 例如 
			//		var set = new Set();
			// 		var num = 23;
			// 		var str = "23";
			// 		set.add(num);
			// 		set.add(str);
			//	str 会覆盖 num，可是 str、num 是两个不同的值
			//  如果 value 是对象时，更容易出现覆盖了，
			//	因为items[value],会把value转变成字符串，
			//  如果 value 是一个对象，会调用对象的 toString()方法。
			// 而对象的 toString() 的结果很多时候都是一样的。 
			// 这会导致冲突
			return true ;
		}
	} ;

	this.remove = function ( value ) {
		if ( this.has ( value ) ) {
			delete items [ value ] ;
			return true ;
		}
		return false ;
	} ;

	this.clear = function ( ) {
		items = { } ;
	} ;

	this.size = function ( ) {
		return Object.keys( items ).length ;
	} ;

	this.values = function ( ) {
		rturn Object.keys ( items ) ;
	} ; 

	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 ;
		}
	};
}

网上看到的另一个实现（感觉这个才是正确的）

/*js集合set类的实现*/
function Set() {
    this.dataStore = [];
    this.add = add;//新增元素
    this.remove = remove;//删除元素
    this.size = size;//集合的元素个数
    this.union = union;//求并集
    this.contains = contains;//判断一个集合中是否包含某个元素
    this.intersect = intersect;//交集
    this.subset = subset;//判断一个集合是否是另一个的子集
    this.difference = difference;//求补集
    this.show = show;//将集合元素显示出来
}

function add(data) {
    if (this.dataStore.indexOf(data) < 0) {
        this.dataStore.push(data);
        return true;
    }
    else {
        return false;
    }
}

function remove(data) {
    var pos = this.dataStore.indexOf(data);
    if (pos > -1) {
        this.dataStore.splice(pos,1);
        return true;
    }
    else {
        return false;
    }
}

function size() {
    return this.dataStore.length;
}

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 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;
}

/*测试例子：求补集。属于集合cis,不属于集合it*/

var cis = new Set();
var it = new Set();
cis.add("Clayton");
cis.add("Jennifer");
cis.add("Danny");
it.add("Bryan");
it.add("Clayton");
it.add("Jennifer");
var diff = new Set();
diff = cis.difference(it);
console.log(cis.show() + " difference " + it.show() + " -> " + diff.show());