lazysheep 10 X 10
Last updated: 2017-07-18
lazysheep:~ Desktop$ node 《数据结构与算法JavaScript描述》学习笔记(三)—-—集合.js

> Post.tags
JavaScript数据结构

> Post.prev
background对被覆盖元素视觉上的影响

> Post.next
《数据结构与算法JavaScript描述》学习笔记(二)—--—散列
《数据结构与算法JavaScript描述》学习笔记(三)—-—集合

集合

集合是从高中数学就开始学起的东西,应该不会太陌生。比如{0,1,2,3,4}就是一个集合。当然集合是无序的如:{2,4,0,1,3}就与
之前那个集合一样,但是集合中是不允许重复的元素(成员)出现。
所以总结一下:集合(set)是由一组无序但彼此之间又有一定相关性且不重复的元素(成员)构成 集合中的元素称为成员。

集合的定义

  1. 不包含任何成员的集合称为空集,全集是包含一切可能成员的集合。
  2. 如果两个集合的成员完全相同,则称两个集合相等。
  3. 如果一个集合中所有的成员都属于另一个集合,则前一集合称为后一集合的子集。

集合的操作

如图所示
project

集合的实现

主要是通过一个Set类来实现集合的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 集合构造函数
* @class
*/
function Set() {
//集合中储存成员的容器,用数组来表示
this.dataStore = [];
this.add = add;
this.remove = remove;
this.size = size;
this.contains = contains;
this.union = union;
this.intersect = intersect;
this.subset = subset;
this.difference = difference;
this.show = show;
}

下面是核心方法的一些解释:

  • add(data) 向集合中添加成员
  • remove(data) 从集合中删除成员
  • size() 返回集合的长度
  • contains(data) 判断集合是否含有某个成员
  • union(set) 返回两个集合的并集
  • intersect(set) 返回两个集合的交集
  • subset(set) 判断集合是否为所传集合的子集
  • difference(set) 返回两个集合的差集
  • show(set) 返回储存集合中成员的容器

方法的实现

add方法

添加成员

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 添加成员
* @param {*} data 待添加的成员
* @return {boolean} 返回布尔值
*/
function add(data) {
//当检查到现有成员不包括准备添加的成员时
//添加成员并返回true 否则返回false
if (this.dataStore.indexOf(data) < 0) {
this.dataStore.push(data);
return true;
} else {
return false;
}
}

remove方法

删除成员

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 删除成员
* @param {*} data 待删除的成员
* @return {boolean} 返回布尔值
*/
function remove(data) {
//如果在集合中检查到待删除成员
//删除成员并返回true 否则返回false
var pos = this.dataStore.indexOf(data);
if (pos > -1) {
this.dataStore.splice(pos, 1);
console.log("删除成功!");
return true;
}
else {
console.log("删除失败!");
return false;
}
}

size方法
1
2
3
4
5
6
7
/**
* 返回集合长度
* @return {number}
*/
function size() {
return this.dataStore.length;
}
show方法
1
2
3
4
5
6
7
/**
* 返回储存集合成员的容器
* @return {Set} 集合
*/
function show() {
return this.dataStore;
}
contains方法
1
2
3
4
5
6
7
8
9
10
11
12
/**
* 判断集合中是否含有成员
* @param {*} data
* @return {boolean}
*/
function contains(data) {
if (this.dataStore.indexOf(data) > -1) {
return true;
} else {
return false;
}
}
union方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 返回两个集合的并集
* @param {Set} set 待合并的集合
* @return {Set} 合并后的集合
*/
function union(set) {
//临时集合
var tempSet = new Set();
for (var i = 0; i < this.size(); i++) {
tempSet.add(this.dataStore[i]);
}
for (var i = 0; i < set.size(); i++) {
if (!tempSet.contains(set.dataStore[i])) {
tempSet.dataStore.push(set.dataStore[i]);
}
}
return tempSet;
}
intersect方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 返回两个集合的交集
* @param {Set} set 待交的集合
* @return {Set} 两个集合的交集
*/
function intersect(set) {
var tempSet = new Set();
for (var i = 0; i < this.size(); i++) {
if (set.contains(this.dataStore[i])) {
tempSet.dataStore.push(this.dataStore[i]);
}
}
return tempSet;
}
difference方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 返回两个集合的差集
* @param {Set} set 待差的集合
* @return {Set} 两个集合的差集
*/
function difference(set) {
var tempSet = new Set();
for (var i = 0; i < this.size(); i++) {
if (!set.contains(this.dataStore[i])) {
tempSet.dataStore.push(this.dataStore[i]);
}
}
return tempSet;
}
subset方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 判读集合是否为传入集合的子集
* @param {Set} set 传入的集合
* @return {boolean} 是则返回true
*/
function subset(set) {
if (this.size() > set.size()) {
return false;
}
for (var i = 0; i < this.size(); i++) {
if (!set.contains(this.dataStore[i])) {
return false;
}
}
return true
}

源码在这里

ES6中的集合

另外ES6也新增了集合这一数据结构

ES6中的Set跟Map