7-集合结构

集合结构

什么是集合结构，集合结构的特点：

• 首先几乎现在每种编程语言中，都有集合结构。
  
• 集合结构比较常见的实现方式是哈希表（后续就学到），我们目前自己实现一个封装的集合类。
  
• 集合通常是由一组无序的，不能重复的元素构成。
  
  • 和数学中的集合名词比较相似，但是数学中的集合范围更大一些，也允许集合中的元素重复。
    
  • 在计算机中，集合通常表示的结构中元素是不允许重复的。
    
• 特殊的数组
  
  • 特殊之处在于里面的元素没有顺序，也不能重复。
    
  • 没有顺序意味着不能通过下标值进行访问，不能重复意味着相同的对象在集合中只会存在一份。
    
• 学习集合还是和之前一样，封装一个集合类。
  
  • 2011年6月份发布的ES5中已经包含了Array类。
    
  • 2015年6月份发布的ES6中包含了Set类，所以其实我们可以不封装，直接使用它。
    
  • 但是这里，为了明确集合的内部实现机制，我们还是自己封装一个Set类。
    

创建集合类
封装一个Set类
// 封装集合的构造函数
function Set(){
// 使用一个对象来保存集合的元素
this.items ={}

// 集合的操作方法
…
}**

代码解析：

• 代码就是封装一个集合的构造函数。
  
• 在集合中，添加了一个items属性，用于保存之后添加到集合中的元素，因为Object的keys本身就是一个集合。
  

集合常见操作方法：

• add（value）：向集合添加一个新的项。
  
• remove（value）：从集合移除一个值。
  
• has（values）：如果在集合中返回true，否则返回false。
  
• clear（）：移除集合中所有的项。
  
• size（）：返回集合所包含元素的数量，于数组的length属性类似。
  
• values（）：返回一个包含集合中所有值得数组。
  
• 还有一些集合其它相关得操作，暂时不用。
  

方法代码

添加方法：
Set.prototype.add = function (value) {
// 判断是否存在
if (this.has(value)) return false;
// 将元素添加到集合中
this.items[value] = value
return true
}

删除方法：
Set.prototype.remove = function (value) {
// 判断是否包含
if (!this.has(value)) return false;
// 删除元素
delete this.items[value];
return true;
}

判断元素是否存在：
Set.prototype.has = function (value) {
return this.items.hasOwnProperty(value)
}

清空方法：
Set.prototype.clear = function () {
this.items = {};
}

判断长度方法：
Set.prototype.Size = function () {
return Object.keys(this.items).length;
}

转换成数组方法：
Set.prototype.values = function () {
return Object.keys(this.items);
}

集合之间的操作
集合间通常有如下操作：

• 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
  

• 交集：对于给定的两个集合，返回一个包含两个集合共有元素的新集合。
  

• 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合，且不存在于第二个集合的元素的新集合。存在于A且不存在于B。
  

以A为基础排除A集合里在存在于B集合的元素。

• 子集：验证一个给定集合是否是另一个集合的子集。
  

A集合里所有的元素包含在B集合，B集合里的元素不一定包含在A集合。

集合操作代码实现

并集：

• 并集其实对应就是数学中并集的概念
  

• 集合A和B的并集， 并集是将不同集合的所有元素合并在一起组成的集合，其符号为“∪”。，表示为 A U B，定义如下：
  

        A∪B={x|x∈A,或x∈B}

• 意思是 x（元素）存在于A中，或x存在于B中。
  

代码解析：

• 首先需要创建一个新的集合，代表两个集合的并集。
  
• 遍历集合1中所有的值，并且添加到新集合中。
  
• 遍历集合2中所有的值，并且添加到新集合中。
  
• 将最终的新集合返回。
  

代码实现：
// 集合间的操作
// 并集
Set.prototype.union = function (otherSet) {
// 1. 创建一个新集合
let unionSet = new Set();
// 2. 将A集合中所有的元素添加到新集合中
let values = this.values();
console.log(values);
for (let i = 0; i < values.length; i++) {
unionSet.add(values[i])
}
// 3. 将B集合中所有的元素添加到新集合中
values = otherSet.values();
console.log(values);
for (let i = 0; i < values.length; i++) {
unionSet.add(values[i])
}
return unionSet;
}

交集：

• 交集其实对应的就是数学中交集的概念。
  
• 集合 A 和 B 的交集，表示为 A n B，定义如下：
  

A n B = { x|x ∈ A ʌ x ∈ B }

• 意思是 x（元素）存在于A中，且 x 存在于 B 中。
  

代码解析：

• 创建一个新的集合。
  
• 遍历集合 1 中的所有元素，判断是否该元素在集合 2 中。
  
• 同时在集合 2 中，将该元素加入到新集合中。
  
• 将最终的新集合返回。
  

代码实现：
Set.prototype.insersection = function (otherSet) {
// 1. 创建一个新的集合
let insersection = new Set();


// 2. 将 A 集合中的所有元素以数组形式接受
let values = this.values();


// 3. 声明一个局部变量，记录枚举单位。
let item = null;
for (let i = 0; i < values.length; i++) {
item = values[i];
if (otherSet.has(item)) {
insersection.add(item)
}
}
return insersection;
}

差集：

• 差集其实对应的就是数学中差集的概念。
  
• 集合 A 和 B 的差集，表示为 A-B，定义如下：
  

B - A = { x| x∈ A ʌ x ∉ B}

• 意思是 x（元素）存在于 A中，而且 x 不存在于 B中。
  

代码解析：

• 创建一个新的集合。
  
• 遍历集合1中所有的元素，判断是否在集合2中。
  
• 不存在于集合2中，将该元素添加到新集合中。
  
• 将新集合返回。
  

代码实现：
Set.prototype.difference = function (otherSet) {
let difference = new Set();
let values = this.values();
let item = null;
for (let i = 0; i < values.length; i++) {
let item = values[i];
if (!otherSet.has(item)) {
difference.add(item);
}
}
return difference;
}

子集：

• 子集其实对应就是数学中子集的概念。
  
• 集合 A 是 B 的子集（或集合 B 包含了 A）。
  
• 意思是集合A中的每一个 x（元素），也需要存在于 B 中。
  

代码解析：

• 判断集合1是否大于2，如果大于那么肯定不是集合2的子集。
  
• 不大于的情况下：
  
  • 判断集合1中的元素是否都在集合2中存在。
    
  • 存在，那么是集合2的子集。
    
  • 有一个不存在，那么不是集合2的子集。
    

代码实现：
Set.prototype.isSubset = function (otherSet) {
let values = this.values();
let item = null;
for (let i = 0; i < values.length; i++) {
item = values[i]
if (!otherSet.has(item)) {
return false;
}
}
return true;
}**