第五章 集合
5.1 创建数据集合
????????集合是由一组无序且唯一（即不能重复）的项组成的。这个数据结构使用了与有限集合相同
的数学概念，但应用在计算机科学的数据结构中。
????????在深入学习集合的计算机科学实现之前，我们先看看它的数学概念。在数学中，集合是一组
不同的对象（的集）。
????????比如说，一个由大于或等于0的整数组成的自然数集合：N = {0, 1, 2, 3, 4, 5, 6, …}。集合中
的对象列表用“{}”（大括号）包围。
????????还有一个概念叫空集。空集就是不包含任何元素的集合。比如24和29之间的素数集合。由于
24和29之间没有素数（除了1和自身，没有其他正因数的大于1的自然数），这个集合就是空集。
空集用“{ }”表示。
????????你也可以把集合想象成一个既没有重复元素，也没有顺序概念的数组。
5.2 创建集合
5.2.1 has(value)方法
this.has = function(value){
return value in items
}还有一种更好的实现方法：
this.has = function(value){
return items.hasOwnProperty(value)
}5.2.2 add方法
this.add = function(value){
if(!this.has(value)){
items[value]=value
return true
}
return false
}????????对于给定的value，可以检查它是否存在于集合中。如果不存在，就把value添加到集合中，返回true，表示添加了这个值。如果集合中已经有这个值，就返回false，表示没有添加它。
5.2.3 remove和clear方法
this.remove = function(value){
if(this.has(value)){
delete items[value]
return true
}
return false
}
this.clear = function(){
items={}
}5.2.4 size方法
????????第一种方法是使用一个length变量，每当使用add或remove方法时控制它，就像在上一章
中使用LinkedList类一样。
????????第二种方法，使用JavaScript内建的Object类的一个内建函数（ECMAScript 5以上版本）：
????????JavaScript的Object类有一个keys方法，它返回一个包含给定对象所有属性的数组。在这种
情况下，可以使用这个数组的length属性（行{4}）来返回items对象的属性个数。以上代码只
能在现代浏览器中运行（比如IE9以上版本、Firefox 4以上版本、Chrome 5以上版本、Opera 12以
上版本、Safari 5以上版本，等等）。
this.size = function(){
return Object.keys(items).length
}????????第三种方法是手动提取items对象的每一个属性，记录属性的个数并返回这个数字。这个方
法可以在任何浏览器上运行，和之前的代码是等价的：
this.sizeLegacy = function(){
let count = 0
for(let key in items){
if(items.hasOwnProperty(key))
++count
}
return count
}5.2.5? values方法
values方法也有两种实现方式，第一种方法只能在现代浏览器中使用，第二种可以在所以浏览器中执行：
this.values = function(){
let values=[]
for(let i=0,keys=Object.keys(items);i<keys.length;i++){
values.push(items[keys[i]])
}
return values
}
this.valuesLegacy = function(){
let values=[]
for(let key in items){
if(items.hasOwnProperty(key)){
values.push(items[key])
}
}
return values
}5.2.6 使用Set类
5.3 集合操作
对集合可以进行如下操作。
? 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
? 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
? 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集
合的元素的新集合。
? 子集：验证一个给定集合是否是另一集合的子集。
5.3.1 并集
this.union = function(otherSet){
let unionSet = new Set()
let values = this.values()
for(let i=0;i<values.length;i++){
unionSet.add(values[i])
}
values=otherSet.values()
for(let i=0;i<values.length;i++){
unionSet.add(values[i])
}
return unionSet
}
5.3.2 交集
this.intersection = function(otherSet){
let intersectionSet = new Set()
let values=this.values()
for(let i=0;i<values.length;i++){
if(otherSet.has(values[i])){
intersectionSet.add(values[i])
}
}
return intersectionSet
}
5.3.3 差集
this.difference = function(otherSet){
let differenceSet = new Set()
let values = this.values()
for(let i=0;i<values.length;i++){
if(!otherSet.has(values[i])){
differenceSet.add(values[i])
}
}
return differenceSet
}
5.3.4 子集
this.subset = function(otherSet){
if(this.size()>otherSet.size()) return false
else{
let values=this.values()
for(let i=0;i<values.length;i++){
if(!otherSet.has(values[i])) return false
}
return true
}
}
5.4 ES6——set类
????????和我们的Set不同，ES6的Set的values方法返回Iterator（第2章提到过），而不是值构成
的数组。另一个区别是，我们实现的size方法返回set中存储的值的个数，而ES6的Set则有一
个size属性。
????????可以用delete方法删除set中的元素：
????????set.delete(1);
????????clear方法会重置set数据结构，这跟我们实现的功能一样。
5.5小结
function Set(){
let items = {}
// this.has = function(value){
// return value in items
// }
this.has = function(value){
return items.hasOwnProperty(value)
}
this.add = function(value){
if(!this.has(value)){
items[value]=value
return true
}
return false
}
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.sizeLegacy = function(){
let count = 0
for(let key in items){
if(items.hasOwnProperty(key))
++count
}
return count
}
this.values = function(){
let values=[]
for(let i=0,keys=Object.keys(items);i<keys.length;i++){
values.push(items[keys[i]])
}
return values
}
this.valuesLegacy = function(){
let values=[]
for(let key in items){
if(items.hasOwnProperty(key)){
values.push(items[key])
}
}
return values
}
this.union = function(otherSet){
let unionSet = new Set()
let values = this.values()
for(let i=0;i<values.length;i++){
unionSet.add(values[i])
}
values=otherSet.values()
for(let i=0;i<values.length;i++){
unionSet.add(values[i])
}
return unionSet
}
this.intersection = function(otherSet){
let intersectionSet = new Set()
let values=this.values()
for(let i=0;i<values.length;i++){
if(otherSet.has(values[i])){
intersectionSet.add(values[i])
}
}
return intersectionSet
}
this.difference = function(otherSet){
let differenceSet = new Set()
let values = this.values()
for(let 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{
let values=this.values()
for(let i=0;i<values.length;i++){
if(!otherSet.has(values[i])) return false
}
return true
}
}
}
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！