原著： 数据结构与算法JavaScript描述 原著中代码存在很多问题，本文中的代码都有进行修改
一、列表
列表的抽象数据类型定义
列表是一组有序的数据。每个列表中的数据项称为元素。在 JavaScript 中，列表中的元素可以是任意数据类型。列表中可以保存多少元素并没有事先限定，实际使用时元素的数量受到程序内存的限制。
不包含任何元素的列表称为空列表。列表中包含元素的个数称为列表的 length 。在内部实现上，用一个变量 listSize 保存列表中元素的个数。可以在列表末尾 append 一个元素，也可以在一个给定元素后或列表的起始位置 insert 一个元素。使用 remove 方法从列表中删除元素，使用 clear 方法清空列表中所有的元素。
还可以使用 show() 方法显示列表中所有的元素，使用 getElement() 方法显示当前元素。
列表拥有描述元素位置的属性。列表有前有后（分别对应 front 和 end）。使用 next() 方法可以从当前元素移动到下一个元素，使用 prev() 方法可以移动到当前元素的前一个元素。还可以使用 moveTo(n) 方法直接移动到指定位置，这里的 n 表示要移动到第 n 个位置。currPos 属性表示列表中的当前位置。
列表的抽象数据类型并未指明列表的存储结构，在本章的实现中，我们使用一个数组dataStore 来存储元素
下表：列表的抽象数据类型定义
| listSize （属性） | 列表的元素个数 |
| pos （属性） | 列表的当前位置 |
| length （属性） | 返回列表中元素的个数 |
| clear （方法） | 清空列表中的所有元素 |
| show （方法） | 返回列表的字符串形式 |
| getElement （方法） | 返回当前位置的元素 |
| insert （方法） | 在现有元素后插入新元素 |
| append （方法） | 在列表的末尾添加新元素 |
| remove （方法） | 从列表中删除元素 |
| front （方法） | 将列表的当前位置设移动到第一个元素 |
| end （方法） | 将列表的当前位置移动到最后一个元素 |
| prev （方法） | 将当前位置后移一位 |
| next （方法） | 将当前位置前移一位 |
| currPos （方法） | 返回列表的当前位置 |
| moveTo （方法） | 将当前位置移动到指定位置 |
实现列表类
let List = (() => {
let listSize = 0,
dataStore = [];
pos = 0;
return class List {
constructor() {
}
clear() {
dataStore = [];
listSize = pos = 0;
}
find(el) {
for (let i in dataStore) {
if (el === dataStore[i]) return i;
}
return -1;
}
show() {
return dataStore;
}
insert(el, after) {
let insertPos = this.find(after);
if (insertPos > -1) {
listSize += 1;
dataStore.splice(insertPos, 0, el);
return true;
}
return false;
}
append(el) {
dataStore[listSize++] = el;
}
remove(el) {
let foundAt = this.find(el);
if (foundAt > -1) {
dataStore.splice(foundAt, 1);
listSize -= 1;
return true;
}
return false;
}
front() {
pos = 0;
}
end() {
pos = listSize - 1;
}
prev() {
if (pos > 0) {
--pos;
}
}
next() {
if (pos < listSize - 1) {
++pos
}
}
length() {
return listSize;
}
currPos() {
return pos;
}
moveTo(p) {
pos = p;
}
getElement() {
return dataStore[pos];
}
contains(el) {
for (let i in dataStore) {
if (el === dataStore[i]) return true;
}
return false;
}
}
})()
let aList = new List();
aList.append('1')
aList.append('2')
aList.append('3')
aList.append('4')
aList.append('5')
aList.append('6')
aList.remove('3')
aList.insert('3', '4')
console.log(aList.contains('2')) // true
console.log(aList.show()) // [ '1', '2', '3', '4', '5', '6' ]
//移动到列表的第一个元素
aList.front();
console.log(aList.getElement()); //1
aList.next();// 第二个元素
aList.next();
aList.next();// 第四个元素
console.log(aList.getElement()); // 4
使用迭代器访问列表
使用迭代器的一些优点。
- 访问列表元素时不必关心底层的数据存储结构。 •
- 当为列表添加一个元素时，索引的值就不对了，此时只用更新列表，而不用更新迭代器。 •
- 可以用不同类型的数据存储方式实现 • cList 类，迭代器为访问列表里的元素提供了一种统一的方式
for(aList.front(); aList.currPos() < aList.length(); aList.next()) {
console.log(aList.getElement());
}
迭代器只是用来在列表上随意移动，而不应该和任何为列表增加或删除元素的方法一起使用。
二、栈
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
对栈的操作
对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用 push() 方法，出栈使用 pop() 方法。
另一个常用的操作是预览栈顶的元素。 pop() 方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。 peek() 方法则只返回栈顶元素，而不删除它。
为了记录栈顶元素的位置，同时也为了标记哪里可以加入新元素，我们使用变量 top ，当向栈内压入元素时，该变量增大；从栈内弹出元素时，该变量减小。
push() 、 pop() 和 peek() 是栈的 3 个主要方法，但是栈还有其他方法和属性。 clear() 方法清除栈内所有元素， length 属性记录栈内元素的个数。我们还定义了一个 empty 属性，用以表示栈内是否含有元素，不过使用 length 属性也可以达到同样的目的。
栈的实现
let Stack = (() => {
let dataStore = [],
top = 0;
return class Stack {
push(el) {
dataStore[top++] = el;
}
pop() { // 它返回栈顶元素，同时将变量 top 的值减 1
if (top <= 0) {
return '出栈失败,空栈顶'
}
return dataStore[--top];
}
peek() { // 返回数组的第 top-1 个位置的元素，即栈顶元素
return dataStore[top - 1];
}
length() {
return top;
}
clear() {
top = 0;
}
}
})()
let aStack = new Stack();
aStack.push('栈1');
aStack.push('栈2');
aStack.push('栈3');
aStack.push('栈4');
console.log(aStack.peek())
aStack.pop();
aStack.pop();
aStack.pop();
console.log(aStack.peek())
使用栈
将数字转换为二进制和八进制
function mulBase(num, base) {
let s = new Stack();
do {
s.push(num % base);
num = Math.floor(num / base);
} while (num > 0);
let converted = "";
while(s.length() > 0){
converted += s.pop();
}
return converted;
}
console.log(mulBase(21, 2)); // 10101
回文
function isPalindrome(word) {
let s = new Stack();
for (let i in word) {
s.push(word[i]);
}
var result = "";
while(s.length() > 0) {
result += s.pop()
}
return result === word;
}
console.log(isPalindrome("ht"))
三、队列
队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出
对队列的操作
队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。
队列的另外一项重要操作是读取队头的元素。这个操作叫做 peek() 。我们还想知道队列中存储了多少元素，可以使用 length 属性满足该需求；要想清空队列中的所有元素，可以使用 clear() 方法来实现。
队列的实现
let Queue = (() => {
let dataStore = [];
return class Queue {
enqueue(el) { // 入队
dataStore.push(el)
}
dequeue() { // 出队
return dataStore.shift();
}
front(){
return dataStore[0];
}
back(){
return dataStore[dataStore.length-1];
}
show(){
return dataStore;
}
}
})()
aQueue.enqueue('1')
aQueue.enqueue('2')
aQueue.enqueue('3')
aQueue.enqueue('4')
console.log(aQueue.show()) // [ '1', '2', '3', '4' ]
aQueue.dequeue();
console.log(aQueue.show()) // [ '2', '3', '4' ]
优先队列
在一般情况下，从队列中删除的元素，一定是率先入队的元素。但是也有一些使用队列的应用，在删除元素时不必遵守先进先出的约定。这种应用，需要使用一个叫做优先队列的数据结构来进行模拟。
从优先队列中删除元素时，需要考虑优先权的限制。比如医院急诊科（EmergencyDepartment）的候诊室，就是一个采取优先队列的例子。当病人进入候诊室时，分诊护士会评估患者病情的严重程度，然后给一个优先级代码。高优先级的患者先于低优先级的患者就医，同样优先级的患者按照先来先服务的顺序就医。
class Patient {
constructor(name, code) {
this.name = name;
this.code = code; // 病人严重程度
}
}
let aqueue = new Queue();
let aP1 = aqueue.enqueue(new Patient('张三', 3));
let aP2 = aqueue.enqueue(new Patient('李四', 2));
let aP3 = aqueue.enqueue(new Patient('王五', 1));
console.log(aqueue.show()) // 张三3,李四2,王五1,
console.log(aqueue.dequeue()) // [ Patient { name: '王五', code: 1 } ]
四、链表
数组不总是组织数据的最佳数据结构，原因如下。在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加或删除操作。然而，JavaScript 的数组并不存在上述问题，因为使用 split() 方法不需要再访问数组中的其他元素了。
JavaScript 中数组的主要问题是，它们被实现成了对象，与其他语言（比如 C++ 和 Java）的数组相比，效率很低
如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是更好的选择。
定义链表
链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链，链表的尾元素指向一个 null 节点
链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点（前驱），使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点。
从链表中删除一个元素也很简单。将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null ，元素就删除成功了。图 下 演示了从链表中删除“bacon”的过程。
设计一个基于对象的链表
Node 类用来表示节点， LinkedList 类提供了插入节点、删除节点、显示列表元素的方法，以及其他一些辅助方法。
head 节点的 next 属性被初始化为 null ，当有新元素插入时， next 会指向新的元素
插入新的节点
在一个已知的节点后面加入新元素时，先要找到后面的新节点。为此创建一个find来查找。
一旦找到“后面”的节点，就可以将新节点插入链表了。首先，将新节点的 next 属性设置为“后面”节点的 next 属性对应的值。然后设置“后面”节点的 next 属性指向新节点。就可以用inser方法加入
通过画图来让大家容易理解一点
之后定义一个 display() 方法，该方法用来显示链表中的元素
最后定义一个remove方法来删除连边中的元素。从链表中删除节点时，需要先找到待删除节点前面的节点。找到这个节点后，修改它的next 属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点。定义findPrevious方法来查找待删除元素之前的元素。
class Node {
constructor(el) {
this.element = el;
this.next = null;
}
}
let LinkedList = (() => {
let head = new Node("head");
return class LinkedList {
find(item){
let currNode = head;
while (currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
findPrevious(item) {
let currNode = head;
while ((currNode.next != null) && (currNode.next.element != item)) {
currNode = currNode.next;
}
return currNode;
}
insert(el, item){
let newNode = new Node(el);
let currNode = this.find(item);
newNode.next = currNode.next;
currNode.next = newNode;
}
remove(item){
let currNode = this.findPrevious(item);
let preNode = this.find(item);
currNode.next = preNode.next;
}
display(){
let node = head;
while( node.next != null) {
console.log(node.next.element);
node = node.next;
}
}
}
})()
let aList = new LinkedList();
aList.insert("1", "head")
aList.insert("2", "1")
aList.insert("3", "2")
aList.display(); // 1 2 3
aList.remove('3')
aList.display();// 1 2
双向链表
尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。
首当其冲的是要为 Node 类增加一个 previous 属性
class Node {
constructor(el) {
this.element = el;
this.next = null;
this.previous = null;
}
}
insert() 方法延申,需要设置新节点的 previous 属性
insert(el, item) {
let newNode = new Node(el);
let currNode = this.find(item);
newNode.previous = currNode;
newNode.next = currNode.next;
currNode.next = newNode;
}
remove 方法 就不用查找前一个节点了
remove(item) {
let currNode = this.find(item);
if (currNode.next == null) {
currNode.previous.next = null
currNode.previous = null;
} else {
currNode.next.previous = currNode.previous;
currNode.previous.next = currNode.next;
currNode.next = null;
currNode.previous = null;
}
}
dispReverse() 方法 反序显示双向链表中的元素
dispReverse() {
let currNode = head;
currNode = this.findLast();
while (!(currNode.previous == null)) {
console.log(currNode.element);
currNode = currNode.previous;
}
}
循环链表
循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身
如果你希望可以从后向前遍历链表，但是又不想付出额外代价来创建一个双向链表，那么就需要使用循环链表。从循环链表的尾节点向后移动，就等于从后向前遍历链表
创建循环链表，只需要修改 LList 类的构造函数
let LinkedList = (() => {
let head = new Node("head");
head.next = head;
return class LinkedList {
//...
}
}
)()
只需要修改一处，就将单向链表变成了循环链表。但是其他一些方法需要修改才能工作正常,之前判断.next != null 的都需要稍加修改
5、字典
字典是一种以键 - 值对形式存储数据的数据结构，就像电话号码簿里的名字和电话号码一样。要找一个电话时，先找名字，名字找到了，紧挨着它的电话号码也就找到了。这里的键是指你用来查找的东西，值是查找得到的结果。
javascript Object类就是以字典的形式来设计的。
字典类
字典类的基础是 Array 类，而不是 Object 类。
从字典中删除键 - 值对需要使用 JavaScript 中的一个内置函数： delete 。
class Dictionary {
constructor() {
this.dataStore = new Array()
}
add(key, val) {
this.dataStore[key] = val;
}
find(key) {
return this.dataStore[key]
}
remove(key) {
delete this.dataStore[key]
}
show() {
console.log(this.dataStore)
for (let i in this.dataStore) {
console.log(`key : ${i} ===> value : ${this.dataStore[i]}`)
}
}
}
let aD = new Dictionary();
aD.add('name', "hongtao")
aD.add('age', "22")
aD.remove('name')
aD.show(); // key : age ===> value : 22
拓展
查看字典里元素的个数
length() {
return Object.keys(this.dataStore).length;
}
清空
clear() {
this.dataStore = new Array()
}
排序
Object.keys(this.datastore).sort()
散列(hash)
散列是一种常用的数据存储技术，散列后的数据可以快速地插入或取用。
下图 以一个小型电话号码簿为例，阐释了散列的概念
定义散列类
class HashTable {
constructor() {
this.table = new Array(137);
}
}
选择一个散列函数
散列函数的选择依赖于键值的数据类型，如果键是整型，最简单的散列函数就是以数组的长度对键取余。在一些情况下，比如数组的长度是 10，而键值都是 10 的倍数时，就不推荐使用这种方式了。这也是数组的长度为什么要是质数的原因之一，就像我们在上个构造函数中，设定数组长度为 137 一样。如果键是随机的整数，则散列函数应该更均匀地分布这些键。这种散列方式称为除留余数法。
将字符串中每个字符的 ASCII 码值相加似乎是一个不错的散列函数。这样散列值就是 ASCII 码值的和除以数组长度的余数。
put() 和 showDistro() ，一个用来将数据存入散列表，一个用来显示散列表中的数据
class HashTable {
constructor() {
this.table = new Array(137);
}
simpleHash(data) {
let total = 0;
for (let i = 0; i < data.length; i++) {
total += data.charCodeAt(i);
}
return total % this.table.length;
}
put(data) {
let pos = this.simpleHash(data);
this.table[pos] = data;
}
showDistro() {
for (let i in this.table) {
if(this.table[i] != undefined) {
console.log(`${i} : ${this.table[i]}`);
}
}
}
}
let ht = new HashTable();
let names = ["David", "Jennifer", "Donnie", "Raymond","Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
for(let i in names) {
ht.put(names[i]);
}
ht.showDistro();
/*
35 : Cynthia
45 : Clayton
57 : Donnie
77 : David
95 : Danny
116 : Mike
132 : Jennifer
134 : Jonathan
*/
很显然，数据并不是均匀分布的，人名向数组的两端集中。而且上面打印出来的只有8个，可是我们的names里有9个名字，这就是碰撞的问题，什么时候发生了碰撞呢。往下看
simpleHash(data) {
let total = 0;
for (let i = 0; i < data.length; i++) {
total += data.charCodeAt(i);
}
console.log('hash 列表 :' + data + "---->" + total)
return total % this.table.length;
}
// 打印结果
/*
hash 列表 :David---->488
hash 列表 :Jennifer---->817
hash 列表 :Donnie---->605
hash 列表 :Raymond---->730
hash 列表 :Cynthia---->720
hash 列表 :Mike---->390
hash 列表 :Clayton---->730
hash 列表 :Danny---->506
hash 列表 :Jonathan---->819
*/
我们发现 经过hash算法转换过的 Clayton 和 Raymond 都是730 这就发生了碰撞的问题，所以Clayton会将 Raymond给覆盖了。
一个更好的散列函数
为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数。这一点很关键，这和计算散列值时使用的取余运算有关。
为了避免碰撞，在给散列表一个合适的大小后，接下来要有一个计算散列值的更好方法。霍纳算法很好地解决了这个问题。在此算法中，新的散列函数仍然先计算字符串中各字符的 ASCII 码值，不过求和时每次要乘以一个质数。大多数算法书建议使用一个较小的质数
betterHash(string) {
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {
total += this.table.length - 1;
}
return parseInt(total);
}
这次所有的人名都显示出来了，而且没有碰撞
散列化整型键
此处介绍如何散列化整型键，使用的数据集是学生的成绩。我们将随机产生一个 9 位数的键，用以识别学生身份和一门成绩。下面是产生学生数据（包含 ID 和成绩）的函数：
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function genStuData(arr) {
for (var i = 0; i < arr.length; ++i) {
var num = "";
for (var j = 1; j <= 9; ++j) {
num += Math.floor(Math.random() * 10);
}
num += getRandomInt(50, 100);
arr[i] = num;
}
}
使用 getRandomInt() 函数时，可以指定随机数的最大值和最小值。拿学生的成绩来说，最低分是 50，最高分是 100。
genStuData() 函数生成学生的数据。里层的循环用来生成学生的 ID，紧跟在循环后面的代码生成一个随机的成绩，并把成绩缀在 ID 的后面。主程序会把 ID 和成绩分离。散列函数将学生 ID 里的数字相加，使用 simpleHash() 函数计算出散列值。
完整代码
class HashTable {
constructor() {
this.table = new Array(137);
}
simpleHash(data) {
var total = 0;
for (var i = 0; i < data.length; ++i) {
total += data.charCodeAt(i);
}
console.log("Hash value: " + data + " -> " + total);
return total % this.table.length;
}
betterHash(string) {
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {
total += this.table.length - 1;
}
return parseInt(total);
}
put(data) {
let pos = this.betterHash(data);
this.table[pos] = data;
}
showDistro() {
for (let i in this.table) {
if (this.table[i] != undefined) {
console.log(`${i} : ${this.table[i]}`);
}
}
}
}
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function genStuData(arr) {
for (var i = 0; i < arr.length; ++i) {
var num = "";
for (var j = 1; j <= 9; ++j) {
num += Math.floor(Math.random() * 10);
}
num += getRandomInt(50, 100);
arr[i] = num;
}
}
var numStudents = 10;
var arrSize = 97;
var idLen = 9;
var students = new Array(numStudents);
genStuData(students);
console.log("Student data: \n");
for (var i = 0; i < students.length; ++i) {
console.log(students[i].substring(0, 8) + " " +
students[i].substring(9));
}
console.log("\n\nData distribution: \n");
var hTable = new HashTable();
for (var i = 0; i < students.length; ++i) {
hTable.put(students[i]);
}
对散列表排序、从散列表中取值
class HashTable {
constructor() {
this.table = new Array(137);
}
betterHash(string) {
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {
total += this.table.length - 1;
}
return parseInt(total);
}
put(data) {
let pos = this.simpleHash(data);
this.table[pos] = data;
}
showDistro() {
for (let i in this.table) {
if (this.table[i] != undefined) {
console.log(`${i} : ${this.table[i]}`);
}
}
}
}
定义 get() 方法，用以读取存储在散列表中的数据。该方法同样需要对键值进行散列化，然后才能知道数据到底存储在数组的什么位置。
get(key){
return this.table[this.betterHash(key)]
}
碰撞处理
当散列函数对于多个输入产生同样的输出时，就产生了碰撞。散列算法的第二部分就将介绍如何解决碰撞，使所有的键都得以存储在散列表中。本节将讨论两种碰撞解决办法：开链法和线性探测法。
开链法
当碰撞发生时，我们仍然希望将键存储到通过散列算法产生的索引位置上，但实际上，不可能将多份数据存储到一个数组单元中。开链法是指实现散列表的底层数组中，每个数组元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了。使用这种技术，即使两个键散列后的值相同，依然被保存在同样的位置，只不过它们在第二个数组中的位置不一样罢了。如下图
线性探测法
第二种处理碰撞的方法是线性探测法。线性探测法隶属于一种更一般化的散列技术：开放寻址散列。当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。该技术是基于这样一个事实：每个散列表都会有很多空的单元格，可以使用它们来存储数据。
修改put方法:
put(data) {
let pos = this.betterHash(data);
let index = 0;
if (this.table[pos] == undefined) {
this.table[pos] = data;
} else {
while (this.table[++pos] != undefined) {}
this.table[pos] = data;
}
}
当存储数据使用的数组特别大时，选择线性探测法要比开链法好。这里有一个公式，常常可以帮助我们选择使用哪种碰撞解决办法：如果数组的大小是待存储数据个数的 1.5 倍，那么使用开链法；如果数组的大小是待存储数据的两倍及两倍以上时，那么使用线性探测法。
集合
集合（set）是一种包含不同元素的数据结构。集合中的元素称为成员。集合的两个最重要特性是：首先，集合中的成员是无序的；其次，集合中不允许相同成员存在。
当你想要创建一个数据结构，用来保存一些独一无二的元素时，比如一段文本中用到的单词，集合就变得非常有用。
集合的定义
- 空集，全集则是包含一切可能成员的集合。
- 如果两个集合的成员完全相同，则称两个集合相等。
- 如果一个集合中所有的成员都属于另外一个集合，则前一集合称为后一集合的 子集。
对集合的操作
- 并集 ： 将两个集合中的成员进行合并，得到一个新集合。
- 交集 ： 两个集合中共同存在的成员组成一个新的集合。
- 补集 ： 属于一个集合而不属于另一个集合的成员组成的集合。
Set 类的实现
Set类 中有
add()方法：我们添加一个data进入集合，如果集合中没有data则添加成功，如果有，则添加失败。
remove方法：删除集合中的data，如果集合中有data就删除，返回ture，否则返回ture。
union()方法：执行并集操作。返回新的集合
intersect()方法：交集 ∩,返回新的集合
subset()方法： 该集合是否是比较集合的子集。 首先要确定该集合的长度是否小于待比较集合。如果该集合比待比较集合还要大，那么该集合肯定不会是待比较集合的一个子集。当该集合的长度小于待比较集合时，再判断该集合内的成员是否都属于待比较集合。如果有任意一个成员不属于待比较集合，则返回 false ，程序终止。如果一直比较完该集合的最后一个元素，所有元素都属于待比较集合，那么该集合就是待比较集合的一个子集，该方法返回 true 。
difference()方法：补集。该方法返回一个新集合，该集合包含的是那些属于第一个集合但不属于第二个集合的成员。
class Set {
constructor() {
this.dataStore = [];
}
show() {
return this.dataStore;
}
add(data) {
if (this.dataStore.indexOf(data) < 0) {
this.dataStore.push(data);
return true;
}
return false;
}
remove(data) {
let pos = this.dataStore.indexOf(data);
if (pos < 0) {
this.dataStore.splice(pos, 1);
return true;
}
return false;
}
contains(data) {
if (this.dataStore.indexOf(data) > -1) {
return true
}
return false
}
union(set) {
let tempSet = new Set();
for (let i in this.dataStore) {
tempSet.add(this.dataStore[i]);
}
for (let i in set.dataStore) {
if (!tempSet.contains(set.dataStore[i])) {
tempSet.dataStore.push(set.dataStore[i]);
}
}
return tempSet;
}
intersect(set) {
let tempSet = new Set();
for (let i in set.dataStore) {
if (this.dataStore.indexOf(set.dataStore[i]) > -1) {
tempSet.add(set.dataStore[i])
}
}
return tempSet;
}
size() {
return this.dataStore.length;
}
subset(set) {
if (this.size() > set.size()) {
return false;
} else {
for (let i in this.dataStore) {
if (!set.contains(this.dataStore[i])) {
return false;
}
}
return true;
}
}
difference(set){
let tempSet = new Set();
for(let i in this.dataStore) {
if(set.dataStore.indexOf(this.dataStore[i]) < 0) {
tempSet.add(this.dataStore[i])
}
}
return tempSet;
}
}
