在Javascript中学习数据结构与算法

这是一本5万字符(中文约2w)的小书,可能需要几个小时阅读,需要几天或更多时间去消化。部分代码还不能正确地跑起来,有错别字,有不准确的概念...,但这不妨碍它作为你一个野生前端学习数据结构与算法的启蒙文章,期待你的一针见血、刀刀致命😐

对任何专业技术人员来说,理解数据结构都非常重要。作为软件开发者,我们要能够用编程语言和数据结构来解决问题。编程语言和数据结构是这些问题解决方案中不可或缺的一部分。如果选择了不恰当的数据结构,可能会影响所写程序的性能。因此,了解不同数据结构和它们的适用范围十分重要。

一句话:算法即原力,即正义

https://static.surmon.me/nodepress/image/Tips-to-Leverage-LinkedIn%E2%80%99s-Algorithm-for-Results.jpg

本文主要讲述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) 原则的有序集合;新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端为栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

通俗来讲,一摞叠起来的书或盘子都可以看做一个栈,我们想要拿出最底下的书或盘子,一定要现将上面的移走才可以。

https://static.surmon.me/17-5-11/37139672-file_1494437180630_c25d.png

栈也被用在编程语言的编译器和内存中保存变变量、方法调用。

在 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) 原则的一组有序的项;队列在尾部添加新元素,并从头部移除元素。最新添加的元素必须排在队列的末尾。

在现实中,最常见的例子就是排队,吃饭排队、银行业务排队、公车的前门上后门下机制...,前面的人优先完成自己的事务,完成之后,下一个人才能继续。

https://static.surmon.me/17-5-11/70402575-file_1494514892168_a3fe.png

在计算机科学中,一个常见的例子就是打印队列。比如说我们需要打印五份文档。我们会打开每个文档,然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印,以此类推,直到打印完所有文档。

同样的,我们在 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类方法可以帮我们做这些事,但背后的处理机制同样如此。

链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个 元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了链表的结构:

https://static.surmon.me/17-5-12/74150654-file_1494522059825_6a96.png

相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。

数组的另一个细节是可以直接访问任何位置的任何元素,而要想访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。

现实中有许多链表的例子:一列火车是由一系列车厢/车皮组成的,每节车厢/车皮都相互连接,你很容易分离一节车皮,改变它的位置,添加或移除它。下图演示了一列火车,每节车皮都是列表的元素,车皮间的连接就是指针:

https://static.surmon.me/17-5-12/95462143-file_1494522338758_bc84.png

下面我们使用 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))

双向链表

链表有多种不同的类型,这一节介绍双向链表。双向链表和普通链表的区别在于,在链表中, 一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素, 另一个链向前一个元素,如下图所示:

双向链表提供了两种迭代列表的方法:从头到尾,或者反过来。我们也可以访问一个特定节 点的下一个或前一个元素。在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表 起点,重新开始迭代。这是双向链表的一个优点。

https://static.surmon.me/17-5-13/80847886-file_1494664593287_12e95.png

我们继续来实现一个双向链表类:

              
  • 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),如下图所示。

https://static.surmon.me/17-7-10/29012202.jpg

双向循环链表有指向head元素的tail.next,和指向tail元素的head.prev。

https://static.surmon.me/17-7-10/929585.jpg

链表相比数组最重要的优点,那就是无需移动链表中的元素,就能轻松地添加和移除元素。因此,当你需要添加和移除很多元素 时,最好的选择就是链表,而非数组。

本文于 2017/5/11 上午 发布在 Code 分类下,当前已被围观 1642 次

相关标签:算法Web开发Javascript

永久地址:https://surmon.me/article/55

版权声明:自由转载-署名-非商业性使用  |  Creative Commons BY-NC 3.0 CN