输入对话框

输出对话框

集合(Set)

李艳生

湖北师范大学

物理与电子科学学院

2020年春季

回顾

  • 数组:随机访问
  • 栈:后进先出
  • 队列:先进先出
  • 链表:增删效率高

引入

请大家思考我们要存储一组值不重复的有序数据，可以用什么数据结构？

内容

集合(重点)

集合运算(重点)

原生集合

任务

集合

  • 集合实例：自然数集合 N = {0, 1, 2, 3, ...}
  • 集合是一组不同对象的集
  • 集合特征：无序性、确定性、唯一性
  • 集合是一个没有重复元素，也没有顺序概念的数组
  • 集合运算：并、交、差、子

集合操作

  • 创建集合
  • 查找
  • 添加
  • 删除
  • 清空
  • 长度
  • 转数组

算法演示

创建集合

  • JavaScript 的对象不允许一个键指向两个不同的属性，也保证了集合里的元素都是唯一的。
  • 使用对象而不是数组来表示集合
  • 键和值都用元素来表示，方便查找

创建集合


    class Set{
        constructor(){
            this.items = {};
        }
        add(element){} //添加
        delete(element){} //删除
        has(element) //查找
        clear() //清空
        size() // 长度
        values() //转数组
    }

查找元素

  • 如果元素在集合中，返回true，否则返回false。
  • 用来检验某个元素是否存在于集合中

has(element){
    return element in this.items;
    // return Object.prototype.hasOwnProperty.call(this.items, element);
}

添加元素

  • 对于给定的element，可以检查它是否存在于集合中。
  • 如果不存在，就把element 添加到集合中,返回true，表示添加了该元素
  • 如果集合中已经有了这个元素，就返回false，表示没有添加它。

添加元素


add(element) {
    if (!this.has(element)) {
        this.items[element] = element; 
        return true;
    }
    return false;
}

删除元素

  • 首先，验证给定的element 是否存在于集合中
  • 如果存在，就从集合中移除element，返回true，表示元素被移除；否则返回false

删除元素


delete(element) {
    if (this.has(element)) {
        delete this.items[element]; 
        return true;
    }
    return false;
}

获取长度

  • 返回集合中有多少元素

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

清空

  • 清空集合

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

转数组


values(){
    return Object.values(this.items);
}

集合使用

  • 用new创建Set对象

const set = new Set();
set.add(1);
console.log(set.values()); // 输出[1]
console.log(set.has(1)); // 输出true
console.log(set.size()); // 输出1
set.add(2);
console.log(set.values()); // 输出[1, 2]
console.log(set.has(2)); // 输出true
console.log(set.size()); // 输出2
set.delete(1);
console.log(set.values()); // 输出[2]
set.delete(2);
console.log(set.values()); // 输出[]

集合运算

  • 并集：返回一个包含两个集合中所有元素的新集合。
  • 交集：返回一个包含两个集合中共有元素的新集合。
  • 差集：返回一个包含所有存在于第一个集合且不存在于第二个集 合的元素的新集合。
  • 子集：验证一个给定集合是否是另一集合的子集。
## 并集 #### 并集表示 $ A \bigcup B $ #### 并集定义 $ A \bigcup B = \\{ x | x \in A \bigvee x \in B \\} $ ![并集图示](img/6/1.png)

并集


union(otherSet) {
    const unionSet = new Set(); 
    this.values().forEach(value => unionSet.add(value));
    otherSet.values().forEach(value => unionSet.add(value));
    return unionSet;
}

并集


const setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);
const unionAB = setA.union(setB);
console.log(unionAB.values());
## 交集 #### 交集表示 $ A \bigcap B $ #### 交集定义 $ A \bigcap B = \\{ x | x \in A \bigwedge x \in B \\} $ ![并集图示](img/6/2.png)

交集


intersection(otherSet) {
    const intersectionSet = new Set(); 
    const values = this.values();
    for (let i = 0; i < values.length; i++) {
        if (otherSet.has(values[i])) {
            intersectionSet.add(values[i]); 
        }
    }
    return intersectionSet;
}

交集


const setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);
const intersectionAB = setA.intersection(setB);
console.log(intersectionAB.values());
## 差集 #### 差集表示 $ A - B $ #### 差集定义 $ A - B = \\{ x | x \in A \bigwedge x \notin B \\} $ ![并集图示](img/6/3.png)

差集


difference(otherSet) {
    const differenceSet = new Set(); 
    this.values().forEach(value => { 
        if (!otherSet.has(value)) { 
            differenceSet.add(value); 
        }
    });
    return differenceSet;
}

差集


const setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);
const differenceAB = setA.difference(setB);
console.log(differenceAB.values());
## 子集 #### 子集表示 $ A \subseteq B $ #### 子集定义 $ A \subseteq B = \\{ x | \forall x \in A \Rightarrow x \in B \\} $ ![并集图示](img/6/4.png)

子集


isSubsetOf(otherSet) {
    if (this.size() > otherSet.size()) { 
        return false;
    }
    let isSubset = true; 
    this.values().every(value => { 
        if (!otherSet.has(value)) { 
            isSubset = false; 
            return false;
        }
        return true; 
    });
    return isSubset; 
}

子集


const setA = new Set();
setA.add(1);
setA.add(2);
const setB = new Set();
setB.add(1);
setB.add(2);
setB.add(3);
const setC = new Set();
setC.add(2);
setC.add(3);
setC.add(4);
console.log(setA.isSubsetOf(setB));
console.log(setA.isSubsetOf(setC));

原生集合

  • ECMAScript 2015 新增了Set 类作为JavaScript API
  • ES2015 原生的Set 并没有实现了并集、交集、差集、子集

原生集合


const set = new Set();
set.add(1);
console.log(set.values()); // 输出@Iterator
console.log(set.has(1)); // 输出true
console.log(set.size); // 输出1
set.delete(1);
set.clear();

原生集合运算


const setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

并集


const union = (setA, setB) => {
    const unionAb = new Set();
    setA.forEach(value => unionAb.add(value));
    setB.forEach(value => unionAb.add(value));
    return unionAb;
};
console.log(union(setA, setB)); // 输出[1, 2, 3, 4]

交集


const intersection = (setA, setB) => {
    const intersectionSet = new Set();
    setA.forEach(value => {
        if (setB.has(value)) {
            intersectionSet.add(value);
        }
    });
    return intersectionSet;
};
console.log(intersection(setA, setB)); // 输出[2, 3]

差集


const difference = (setA, setB) => {
    const differenceSet = new Set();
    setA.forEach(value => {
        if (!setB.has(value)) { 
            differenceSet.add(value);
        }
    });
    return differenceSet;
};
console.log(difference(setA, setB)); //输出[1]

扩展运算符


console.log(new Set([...setA, ...setB])); //并集
console.log(new Set([...setA].filter(x => setB.has(x)))); //交集
console.log(new Set([...setA].filter(x => !setB.has(x)))); //差集

任务

随机产生100个1000以内的随机数加入集合A中，再随机产生50个1000以内的随机数加入集合B中，求解A和B的并、交、差。