在Javascript中学习数据结构与算法
这是一本5万字符(中文约2w)的小书,可能需要几个小时阅读,需要几天或更多时间去消化。部分代码还不能正确地跑起来,有错别字,有不准确的概念...,但这不妨碍它作为你一个野生前端学习数据结构与算法的启蒙文章,期待你的一针见血、刀刀致命😐
对任何专业技术人员来说,理解数据结构都非常重要。作为软件开发者,我们要能够用编程语言和数据结构来解决问题。编程语言和数据结构是这些问题解决方案中不可或缺的一部分。如果选择了不恰当的数据结构,可能会影响所写程序的性能。因此,了解不同数据结构和它们的适用范围十分重要。
一句话:算法即原力,即正义
本文主要讲述Javascript中实现栈、队列、链表、集合、字典、散列表、树、图等数据结构,以及各种排序和搜索算法,包括冒泡排序、选择排序、插入排序、归并排序、快速排序、顺序搜索、二分搜索,最后还介绍了动态规划和贪心算法等常用的高级算法及相关知识。
在阅读之前假设你已了解并可以熟练使用Javascript编写应用程序。
概览
数据结构
- 栈:一种遵从先进后出 (LIFO) 原则的有序集合;新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端为栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。
- 队列:与上相反,一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项;队列在尾部添加新元素,并从头部移除元素。最新添加的元素必须排在队列的末尾。
- 链表:存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的;每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(指针/链接)组成。
- 集合:由一组无序且唯一(即不能重复)的项组成;这个数据结构使用了与有限集合相同的数学概念,但应用在计算机科学的数据结构中。
- 字典:以 [键,值] 对为数据形态的数据结构,其中键名用来查询特定元素,类似于 Javascript 中的
Object
。 - 散列:根据关键码值(Key value)直接进行访问的数据结构;它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度;这个映射函数叫做散列函数,存放记录的数组叫做散列表。
- 树:由 n(n>=1)个有限节点组成一个具有层次关系的集合;把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的,基本呈一对多关系,树也可以看做是图的特殊形式。
- 图:图是网络结构的抽象模型;图是一组由边连接的节点(顶点);任何二元关系都可以用图来表示,常见的比如:道路图、关系图,呈多对多关系。
算法
排序算法
- 冒泡排序:比较任何两个相邻的项,如果第一个比第二个大,则交换它们;元素项向上移动至正确的顺序,好似气泡上升至表面一般,因此得名。
- 选择排序:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,以此循环,直至排序完毕。
- 插入排序:将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,此算法适用于少量数据的排序,时间复杂度为 O(n^2)。
- 归并排序:将原始序列切分成较小的序列,只到每个小序列无法再切分,然后执行合并,即将小序列归并成大的序列,合并过程进行比较排序,只到最后只有一个排序完毕的大序列,时间复杂度为 O(n log n)。
- 快速排序:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行上述递归排序,以此达到整个数据变成有序序列,时间复杂度为 O(n log n)。
搜索算法
- 顺序搜索:让目标元素与列表中的每一个元素逐个比较,直到找出与给定元素相同的元素为止,缺点是效率低下。
- 二分搜索:在一个有序列表,以中间值为基准拆分为两个子列表,拿目标元素与中间值作比较从而再在目标的子列表中递归此方法,直至找到目标元素。
其他
贪心算法:在对问题求解时,不考虑全局,总是做出局部最优解的方法。
动态规划:在对问题求解时,由以求出的局部最优解来推导全局最优解。
复杂度概念:一个方法在执行的整个生命周期,所需要占用的资源,主要包括:时间资源、空间资源。
数据结构
栈
栈是一种遵从先进后出 (LIFO) 原则的有序集合;新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端为栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。
通俗来讲,一摞叠起来的书或盘子都可以看做一个栈,我们想要拿出最底下的书或盘子,一定要现将上面的移走才可以。
栈也被用在编程语言的编译器和内存中保存变变量、方法调用。
在 Javascript 中我们可以使用数组的原生方法实现一个栈/队列的功能,鉴于学习目的,我们使用类来实现一个栈。
- 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
class Stack {
constructor() {
this.items = []
}
// 入栈
push(element) {
this.items.push(element)
}
// 出栈
pop() {
return this.items.pop()
}
// 末位
get peek() {
return this.items[this.items.length - 1]
}
// 是否为空栈
get isEmpty() {
return !this.items.length
}
// 尺寸
get size() {
return this.items.length
}
// 清空栈
clear() {
this.items = []
}
// 打印栈数据
print() {
console.log(this.items.toString())
}
}
使用栈类:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
// 实例化一个栈
const stack = new Stack()
console.log(stack.isEmpty) // true
// 添加元素
stack.push(5)
stack.push(8)
// 读取属性再添加
console.log(stack.peek) // 8
stack.push(11)
console.log(stack.size) // 3
console.log(stack.isEmpty) // false
队列
与栈相反,队列是一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项;队列在尾部添加新元素,并从头部移除元素。最新添加的元素必须排在队列的末尾。
在现实中,最常见的例子就是排队,吃饭排队、银行业务排队、公车的前门上后门下机制...,前面的人优先完成自己的事务,完成之后,下一个人才能继续。
在计算机科学中,一个常见的例子就是打印队列。比如说我们需要打印五份文档。我们会打开每个文档,然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印,以此类推,直到打印完所有文档。
同样的,我们在 Javascript 中实现一个队列类。
- 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
class Queue {
constructor(items) {
this.items = items || []
}
enqueue(element){
this.items.push(element)
}
dequeue(){
return this.items.shift()
}
front(){
return this.items[0]
}
clear(){
this.items = []
}
get size(){
return this.items.length
}
get isEmpty(){
return !this.items.length
}
print() {
console.log(this.items.toString())
}
}
使用队列类:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
const queue = new Queue()
console.log(queue.isEmpty) // true
queue.enqueue('John')
queue.enqueue('Jack')
queue.enqueue('Camila')
console.log(queue.size) // 3
console.log(queue.isEmpty) // false
queue.dequeue()
queue.dequeue()
queue.print() // 'Camila'
优先队列
队列大量应用在计算机科学以及我们的生活中,我们在之前话题中实现的默认队列也有一些修改版本。
其中一个修改版就是优先队列。元素的添加和移除是基于优先级的。一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。在有些国家,老年人和孕妇(或 带小孩的妇女)登机时也享有高于其他乘客的优先级。
另一个现实中的例子是医院的(急诊科)候诊室。医生会优先处理病情比较严重的患者。通常,护士会鉴别分类,根据患者病情的严重程度放号。
实现一个优先队列,有两种选项:设置优先级,然后在正确的位置添加元素;或者用入列操作添加元素,然后按照优先级移除它们。在下面示例中,我们将会在正确的位置添加元素,因此可以对它们使用默认的出列操作:
- 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
class PriorityQueue {
constructor() {
this.items = []
}
enqueue(element, priority){
const queueElement = { element, priority }
if (this.isEmpty) {
this.items.push(queueElement)
} else {
const preIndex = this.items.findIndex((item) => queueElement.priority < item.priority)
if (preIndex > -1) {
this.items.splice(preIndex, 0, queueElement)
} else {
this.items.push(queueElement)
}
}
}
dequeue(){
return this.items.shift()
}
front(){
return this.items[0]
}
clear(){
this.items = []
}
get size(){
return this.items.length
}
get isEmpty(){
return !this.items.length
}
print() {
console.log(this.items)
}
}
优先队列的使用:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
const priorityQueue = new PriorityQueue()
priorityQueue.enqueue('John', 2)
priorityQueue.enqueue('Jack', 1)
priorityQueue.enqueue('Camila', 1)
priorityQueue.enqueue('Surmon', 3)
priorityQueue.enqueue('skyRover', 2)
priorityQueue.enqueue('司马萌', 1)
priorityQueue.print()
console.log(priorityQueue.isEmpty, priorityQueue.size) // false 6
循环队列
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表、队列的方式来在实际编程应用中来实现。
下面我们基于首次实现的队列类,简单实现一个循环引用的示例:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
class LoopQueue extends Queue {
constructor(items) {
super(items)
}
getIndex(index) {
const length = this.items.length
return index > length ? (index % length) : index
}
find(index) {
return !this.isEmpty ? this.items[this.getIndex(index)] : null
}
}
访问一个循环队列:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
const loopQueue = new LoopQueue(['Surmon'])
loopQueue.enqueue('SkyRover')
loopQueue.enqueue('Even')
loopQueue.enqueue('Alice')
console.log(loopQueue.size, loopQueue.isEmpty) // 4 false
console.log(loopQueue.find(26)) // 'Evan'
console.log(loopQueue.find(87651)) // 'Alice'
链表
要存储多个元素,数组(或列表)可能是最常用的数据结构。
每种语言都实现了数组。这种数据结构非常方便,提供了一个便利的[]
语法来访问它的元素。
然而,这种数据结构有一个缺点:在大多数语言中,数组的大小是固定的,从数组的起点或中间插入或移除项的成本很高,因为需要移动元素;
尽管 JavaScript 中的Array
类方法可以帮我们做这些事,但背后的处理机制同样如此。
链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个 元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了链表的结构:
相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。
数组的另一个细节是可以直接访问任何位置的任何元素,而要想访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。
现实中有许多链表的例子:一列火车是由一系列车厢/车皮组成的,每节车厢/车皮都相互连接,你很容易分离一节车皮,改变它的位置,添加或移除它。下图演示了一列火车,每节车皮都是列表的元素,车皮间的连接就是指针:
下面我们使用 Javascript 创建一个链表类:
- 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
// 链表节点
class Node {
constructor(element) {
this.element = element
this.next = null
}
}
// 链表
class LinkedList {
constructor() {
this.head = null
this.length = 0
}
// 追加元素
append(element) {
const node = new Node(element)
let current = null
if (this.head === null) {
this.head = node
} else {
current = this.head
while(current.next) {
current = current.next
}
current.next = node
}
this.length++
}
// 任意位置插入元素
insert(position, element) {
if (position >= 0 && position <= this.length) {
const node = new Node(element)
let current = this.head
let previous = null
let index = 0
if (position === 0) {
this.head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
this.length++
return true
}
return false
}
// 移除指定位置元素
removeAt(position) {
// 检查越界值
if (position > -1 && position < length) {
let current = this.head
let previous = null
let index = 0
if (position === 0) {
this.head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
}
return null
}
// 寻找元素下标
findIndex(element) {
let current = this.head
let index = -1
while (current) {
if (element === current.element) {
return index + 1
}
index++
current = current.next
}
return -1
}
// 删除指定文档
remove(element) {
const index = this.indexOf(element)
return this.removeAt(index)
}
isEmpty() {
return !this.length
}
size() {
return this.length
}
// 转为字符串
toString() {
let current = this.head
let string = ''
while (current) {
string += ` ${current.element}`
current = current.next
}
return string
}
}
链表类的使用:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
const linkedList = new LinkedList()
console.log(linkedList)
linkedList.append(2)
linkedList.append(6)
linkedList.append(24)
linkedList.append(152)
linkedList.insert(3, 18)
console.log(linkedList)
console.log(linkedList.findIndex(24))
双向链表
链表有多种不同的类型,这一节介绍双向链表。双向链表和普通链表的区别在于,在链表中, 一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素, 另一个链向前一个元素,如下图所示:
双向链表提供了两种迭代列表的方法:从头到尾,或者反过来。我们也可以访问一个特定节 点的下一个或前一个元素。在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表 起点,重新开始迭代。这是双向链表的一个优点。
我们继续来实现一个双向链表类:
- 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
// 链表节点
class Node {
constructor(element) {
this.element = element
this.prev = null
this.next = null
}
}
// 双向链表
class DoublyLinkedList {
constructor() {
this.head = null
this.tail = null
this.length = 0
}
// 任意位置插入元素
insert(position, element) {
if (position >= 0 && position <= this.length){
const node = new Node(element)
let current = this.head
let previous = null
let index = 0
// 首位
if (position === 0) {
if (!head){
this.head = node
this.tail = node
} else {
node.next = current
this.head = node
current.prev = node
}
// 末位
} else if (position === this.length) {
current = this.tail
current.next = node
node.prev = current
this.tail = node
// 中位
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
current.prev = node
node.prev = previous
}
this.length++
return true
}
return false
}
// 移除指定位置元素
removeAt(position) {
if (position > -1 && position < this.length) {
let current = this.head
let previous = null
let index = 0
// 首位
if (position === 0) {
this.head = this.head.next
this.head.prev = null
if (this.length === 1) {
this.tail = null
}
// 末位
} else if (position === this.length - 1) {
this.tail = this.tail.prev
this.tail.next = null
// 中位
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
this.length--
return current.element
} else {
return null
}
}
// 其他方法...
}
循环链表
循环链表可以像链表一样只有单向引用,也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于,最后一个元素指向下一个元素的指针(tail.next)不是引用null, 而是指向第一个元素(head),如下图所示。
双向循环链表有指向head元素的tail.next,和指向tail元素的head.prev。
链表相比数组最重要的优点,那就是无需移动链表中的元素,就能轻松地添加和移除元素。因此,当你需要添加和移除很多元素 时,最好的选择就是链表,而非数组。
😃😃😃
BUG测试💊
代理评论测试💊
回复 #259 @jooger:
测你大爷
回复 #261 @Surmon:
😜
有个地方写错了:后序遍历:左侧子节点 => 右侧子节点 => 节点本身
你手机端的说说广播📢会导致文章列表重绘,一直抖。可以点点上下箭头shi shi
回复 #264 @zangxd:
谢谢,实际上这篇文章还没彻底整理好...🌹🌹🌹
回复 #265 @幾米:
🌻🌻🌻谢谢
回复 #267 @Surmon:
看错了,是轮播图导致的。评论的表单,iPhone 的输入法有自动补全提示,自动填入之后,你的验证不能通过。你去看看 input 的 compositionstart 和 compositionend 事件。不知道什么原因,我Safari访问,如果不打开vpn,提示无法连接到服务器😂
哥,看你的文章一下午,听了一下午歌,发现了 京东热,是不是罪过啊
回复 #310 @like:
东京到底热不热
回复 #311 @Surmon:
很躁😂,哈哈
😍
请问博主,本网站web端,可以加一个放宽文章页面的按钮吗,好窄
🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏💪
回复 #377 @zgj233:
好主意,很快加上
回复 #378 @Surmon:
哈哈哈, 匿名聊天真开心。请问用户的头像能设置么?
回复 #379 @zgj233:
gravatar
回复 #377 @zgj233:
加上了
回复 #389 @Surmon:
感谢博主加上全屏浏览的功能, 看文章更方便了
回复 #465 @zgj233:
🌹
博主好强 👍👍👍 向你学习
创建图类的时候不需要加 ()吧
class Graph {}
我想请教一下哈,为什么数组前面加个;就不会导致报错呢 😃
回复 #539 @lihaozecq:
看这里: JavaScript 语句后应该加分号么? - 尤雨溪的回答 - 知乎 https://www.zhihu.com/question/20298345/answer/49551142
可以可以
好