这本书让我回顾了一遍大学时候学的数据结构。数据结构和算法是程序员最喜欢也是最痛苦的部分,这本书很轻松的描述了这部分东西,是一本很不错的书。这篇文章记录书中的重点部分,并不会对书中所有的内容都复述一遍,如果希望了解更多的内容可以去看看这本书。由于ES5和ES6思想基本上是相同的,这里只记录ES6的实现。
1. 栈
栈是一种遵从后进先出(LIFO)原则的有序集合。
新添加的或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。
栈的实现:
1 | let Stack = (function () { |
应用:十进制转换成其他进制。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23function baseConverter(decNumber, base = 2){
var remStack = new Stack(),
rem,
baseString = '',
digits = '0123456789ABCDEF';
while (decNumber > 0){
rem = Math.floor(decNumber % base);
remStack.push(rem);
decNumber = Math.floor(decNumber / base);
}
while (!remStack.isEmpty()){
baseString += digits[remStack.pop()];
}
return baseString;
}
console.log(baseConverter(100345, 2));// 11000011111111001
console.log(baseConverter(100345, 8));// 303771
console.log(baseConverter(100345, 16));// 187F9
2. 队列
队列是遵循FIFO(First In First Out,先进先出,也称为先来先服务)原则的一组有序的项。
队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。
队列的实现:
1 | let Queue = (function () { |
优先队列:给定一个优先级,如果新插入的元素按照优先级高低从栈顶到栈尾插入到第一个优先级比他的小元素的前面。
注:这个实现中值越小优先级越高。
1 | let PriorityQueue = (function () { |
实战:击鼓传花,使用循环队列来实现。
题目描述:在这个游戏中,孩子们围成一个圆圈,把花尽快地传递给旁边的人。某一时刻传花停止,
这个时候花在谁手里,谁就退出圆圈结束游戏。重复这个过程,直到只剩一个孩子(胜者)。
1 | function hotPotato (nameList, num){ |
运行示例图:
3. 列表
列表是为了解决数组插入或移除消耗内存大而出现的数据结构。
链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。
列表的实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170let LinkedList = (function () {
class Node {
constructor(element){
this.element = element;
this.next = null;
}
}
const length = new WeakMap();
const head = new WeakMap();
class LinkedList {
constructor () {
length.set(this, 0);
head.set(this, null);
}
append(element) {
let node = new Node(element),
current;
if (this.getHead() === null) { //first node on list
head.set(this, node);
} else {
current = this.getHead();
//loop the list until find last item
while (current.next) {
current = current.next;
}
//get last item and assign next to added item to make the link
current.next = node;
}
//update size of list
let l = this.size();
l++;
length.set(this, l);
}
insert(position, element) {
//check for out-of-bounds values
if (position >= 0 && position <= this.size()) {
let node = new Node(element),
current = this.getHead(),
previous,
index = 0;
if (position === 0) { //add on first position
node.next = current;
head.set(this, node);
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
//update size of list
let l = this.size();
l++;
length.set(this, l);
return true;
} else {
return false;
}
}
removeAt(position) {
//check for out-of-bounds values
if (position > -1 && position < this.size()) {
let current = this.getHead(),
previous,
index = 0;
//removing first item
if (position === 0) {
head.set(this, current.next);
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
//link previous with current's next - skip it to remove
previous.next = current.next;
}
let l = this.size();
l--;
length.set(this, l);
return current.element;
} else {
return null;
}
}
remove(element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
indexOf(element) {
let current = this.getHead(),
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
}
isEmpty() {
return this.size() === 0;
}
size() {
return length.get(this);
}
getHead() {
return head.get(this);
}
toString() {
let current = this.getHead(),
string = '';
while (current) {
string += current.element + (current.next ? ', ' : '');
current = current.next;
}
return string;
}
print() {
console.log(this.toString());
}
}
return LinkedList;
})();
双向列表
1 | let DoublyLinkedList = (function () { |
4. 集合
集合是由一组无序且唯一(即不能重复)的项组成的。这个数据结构使用了与有限集合相同的数学概念,但应用在计算机科学的数据结构中。
注:这里的名称叫Set但是最好不要用这个名字,因为ES6中本来就有这个全局变量。
1 | let Set = (function () { |
5. 字典
在字典中,存储的是[键,值]对(其实就是我们的Map),其中键名是用来查询特定元素的。字典和集合很相似,集合以[值,值]的形式存储元素,字典则是以[键,值]的形式来存储元素。字典也称作映射。
1 | function Dictionary(){ |
6. 散列表
散列表是散列值(HashCode)和真实值的对应关系,为了避免多个值对应相同HashCode的情况,在存储的时候会存在HashCode所在位置及以后第一个不为空的地方,查找的时候找到hashCode所处的位置,然后从这里开始向后找,知道找到键相同的元素。也可以使用之前开发好的LinkedList和HashCode的对应关系避免。
1 | function HashTable(){ |
7. 树
一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点。
位于树顶部的节点叫作根节点(11)。它没有父节点。树中的每个元素都叫作节点,节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点(7、5、9、15、13和20是内部节点)。没有子元素的节点称为外部节点或叶节点(3、6、8、10、12、14、18和25是叶节点)。
一个节点可以有祖先和后代。一个节点(除了根节点)的祖先包括父节点、祖父节点、曾祖父节点等。一个节点的后代包括子节点、孙子节点、曾孙节点等。
二叉树中的节点最多只能有两个子节点:一个是左侧子节点,另一个是右侧子节点。这些定义有助于我们写出更高效的向/从树中插入、查找和删除节点的算法。二叉树在计算机科学中的应用非常广泛。
二叉搜索树(BST)是二叉树的一种,但是它只允许你在左侧节点存储(比父节点)小的值,在右侧节点存储(比父节点)大(或者等于)的值。
二叉搜索树的实现:
1 | function BinarySearchTree() { |
AVL树
BST(二叉搜索树)存在一个问题:取决于你添加的节点数,树的一条边可能会非常深;也就是说,树的一条分支会有很多层,而其他的分支却只有几层。就比如如果第一次添加的是1(根节点),其他节点添加的都是大于1的数,那么其他的节点都会在根节点的右边而左边就没有左子树了。这种情况下添加、移除和搜索某个节点时引起一些性能问题。为了解决这个问题,有一种树叫作Adelson-Velskii-Landi树(AVL树)。AVL树是一种自平衡二叉搜索树,意思是任何一个节点左右两侧子树的高度之差最多为1。也就是说这种树会在添加或移除节点时尽量试着成为一棵完全树。
1 | function AVLTree() { |
红黑树的实现:
1 | function RedBlackTree() { |
8. 图
图是网络结构的抽象模型。图是一组由边连接的节点(或顶点)。学习图是重要的,因为任何二元关系都可以用图来表示。
一个图G = (V, E)由以下元素组成。
V:一组顶点
E:一组边,连接V中的顶点
由一条边连接在一起的顶点称为相邻顶点。
一个顶点的度是其相邻顶点的数量。
如果图中不存在环,则称该图是无环的。如果图中每两个顶点间都存在路径,则该图是连通的。
图可以分为是无向图(边没有方向)和有向图(有向图)。
图也可以是未加权的(目前为止我们看到的图都是未加权的)或是加权的。
图有的三种表示法
8.1.1 邻接矩阵
8.1.2 邻接表
8.1.3 关联矩阵
图的遍历有两种:
8.2.1 广度优先搜索:
8.2.2 深度优先搜索:
图的实现:
1 | function Graph() { |
9. 排序和查找
1 | function ArrayList(){ |
9. 算法模式
递归实现斐波那契函数1
2
3
4
5
6function fibonacci(num){
if (num === 1 || num === 2){
return 1;
}
return fibonacci(num - 1) + fibonacci(num - 2);
}
最少硬币找零问题
动态规划求解:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27function MinCoinChange(coins){
var coins = coins;
var cache = {};
this.makeChange = function(amount) {
var me = this;
if (!amount) {
return [];
}
if (cache[amount]) {
return cache[amount];
}
var min = [], newMin, newAmount;
for (var i=0; i<coins.length; i++){
var coin = coins[i];
newAmount = amount - coin;
if (newAmount >= 0){
newMin = me.makeChange(newAmount);
}
if (newAmount >= 0 && (newMin.length < min.length-1 || !min.length)
&& (newMin.length || !newAmount) {
min = [coin].concat(newMin);
console.log('new Min ' + min + ' for ' + amount);
}
}
return (cache[amount] = min);
};
}
贪心算法求解:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function MinCoinChange(coins){
var coins = coins;
this.makeChange = function(amount) {
var change = [],
total = 0;
for (var i=coins.length; i>=0; i--){
var coin = coins[i];
while (total + coin <= amount) {
change.push(coin);
total += coin;
}
}
return change;
};
}
使用1
2var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
console.log(minCoinChange.makeChange(36));