# 简易数据结构译自：[https://github.com/thejameskyle/itsy-bitsy-data-structures](https://github.com/thejameskyle/itsy-bitsy-data-structures) ```javascript 'use strict'; /** * ███████████████═╗ ███████████████═╗ █████████████═╗ █████═╗ █████═╗ * ███████████████ ║ ███████████████ ║ ███████████████ ║ █████ ║ █████ ║ * ╚═══█████ ╔════╝ ╚═══█████ ╔════╝ █████ ╔═════════╝ █████ ║ █████ ║ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * █████ ║ █████ ║ █████████████═╗ ███████████████ ║ * █████ ║ █████ ║ ╚█████████████═╗ ╚███████████ ╔═╝ * █████ ║ █████ ║ ╚══════█████ ║ ╚═█████ ╔══╝ * █████ ║ █████ ║ █████ ║ █████ ║ * ███████████████═╗ █████ ║ ███████████████ ║ █████ ║ * ███████████████ ║ █████ ║ █████████████ ╔═╝ █████ ║ * ╚══════════════╝ ╚════╝ ╚════════════╝ ╚════╝ * * █████████████═══╗ ███████████████═╗ ███████████████═╗ █████████████═╗ █████═╗ █████═╗ * ███████████████ ║ ███████████████ ║ ███████████████ ║ ███████████████ ║ █████ ║ █████ ║ * █████ ╔═══█████ ║ ╚═══█████ ╔════╝ ╚═══█████ ╔════╝ █████ ╔═════════╝ █████ ║ █████ ║ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * █████████████ ╔═╝ █████ ║ █████ ║ █████████████═╗ ███████████████ ║ * ███████████████═╗ █████ ║ █████ ║ ╚█████████████═╗ ╚███████████ ╔═╝ * █████ ╔═══█████ ║ █████ ║ █████ ║ ╚══════█████ ║ ╚═█████ ╔══╝ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * ███████████████ ║ ███████████████═╗ █████ ║ ███████████████ ║ █████ ║ * █████████████ ╔═╝ ███████████████ ║ █████ ║ █████████████ ╔═╝ █████ ║ * ╚════════════╝ ╚══════════════╝ ╚════╝ ╚════════════╝ ╚════╝ * * █████████████═══╗ ███████████═══╗ ███████████████═╗ ███████████═══╗ * ███████████████ ║ ███████████████ ║ ███████████████ ║ ███████████████ ║ * █████ ╔═══█████ ║ █████ ╔═══█████ ║ ╚═══█████ ╔════╝ █████ ╔═══█████ ║ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * █████ ║ █████ ║ ███████████████ ║ █████ ║ ███████████████ ║ * █████ ║ █████ ║ ███████████████ ║ █████ ║ ███████████████ ║ * █████ ║ █████ ║ █████ ╔═══█████ ║ █████ ║ █████ ╔═══█████ ║ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * ███████████████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * █████████████ ╔═╝ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * ╚════════════╝ ╚════╝ ╚════╝ ╚════╝ ╚════╝ ╚════╝ * * █████████████═╗ ███████████████═╗ █████████████═══╗ █████═╗ █████═╗ █████████████═╗ ███████████████═╗ * ███████████████ ║ ███████████████ ║ ███████████████ ║ █████ ║ █████ ║ ███████████████ ║ ███████████████ ║ * █████ ╔═════════╝ ╚═══█████ ╔════╝ █████ ╔═══█████ ║ █████ ║ █████ ║ █████ ╔═════════╝ ╚═══█████ ╔════╝ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * █████████████═╗ █████ ║ █████████████ ╔═╝ █████ ║ █████ ║ █████ ║ █████ ║ * ╚█████████████═╗ █████ ║ ███████████████═╗ █████ ║ █████ ║ █████ ║ █████ ║ * ╚══════█████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * ███████████████ ║ █████ ║ █████ ║ █████ ║ ███████████████ ║ ███████████████═╗ █████ ║ * █████████████ ╔═╝ █████ ║ █████ ║ █████ ║ ╚███████████ ╔═╝ ╚█████████████ ║ █████ ║ * ╚════════════╝ ╚════╝ ╚════╝ ╚════╝ ╚══════════╝ ╚════════════╝ ╚════╝ * * █████═╗ █████═╗ █████████████═══╗ ████████████████═╗ ██████████████═╗ * █████ ║ █████ ║ ███████████████ ║ ████████████████ ║ ████████████████ ║ * █████ ║ █████ ║ █████ ╔═══█████ ║ █████ ╔══════════╝ █████ ╔══════════╝ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * █████ ║ █████ ║ █████████████ ╔═╝ ████████████████═╗ ██████████████═╗ * █████ ║ █████ ║ ███████████████═╗ ████████████████ ║ ╚██████████████═╗ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ╔══════════╝ ╚═══════█████ ║ * █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ * ███████████████ ║ █████ ║ █████ ║ ████████████████═╗ ████████████████ ║ * ╚███████████ ╔═╝ █████ ║ █████ ║ ████████████████ ║ ██████████████ ╔═╝ * ╚══════════╝ ╚════╝ ╚════╝ ╚═══════════════╝ ╚═════════════╝ * * ══════════════════════════════════════════════════════════════════════ * ████ By James Kyle (@thejameskyle) █████████████████████████████████████████ * ══════════════════════════════════════════════════════════════════════ */ /** * 今天我们将要了解并学习数据结构。 * * "OOooooOOOooh *soo* exciting" right? * * 没错，它不是最有内容的话题，但它很重要。并非为了向计算机输入奇怪的101，而是让自己成为一名 * 更好的程序员。 * * 理解数据结构可以让你： * * - 管理复杂的系统，并使你的代码更易维护。 * - 构建高性能，高效率的应用。 * * 我认为前者更重要一些。使用正确的数据结构可以大幅简化本来很复杂的逻辑。 * * 当然后者同样重要。如果关心性能和内存，应用正确的数据机构比通常的解决方案更重要。 * * 为了了解数据结构，我们准备尝试一起实现它们中的一部分。别怕，我们将保持代码的简洁。 * 实际上，注释要比代码多。 */ /** * ============================================================================ * ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-' * ============================================================================ */ /** * 什么是数据结构？ * * 实际上，他们是一些不同的存储和组织数据的方法，供若干不同的需求使用。 * * 数据总可以以很多不同的方式表现。然而，基于数据的具体内容与它的用途，总有一种表现方式更优一些。 * * 想要理解为什么，让我们先简单聊一聊算法。 */ /*** ===================================================================== ***\ ** - 算法 ---------------------------------------------------------------- ** * ========================================================================= * * * * ,--,--. ,--,--. * * ,----------. | | | | | | _____ * * |`----------'| | | | | | | | | ,------. * * | | | | | | | | ,--. | o o | |`------'| * * | | ,| +-|-+ | | +-|-+ |` | | |_____| | | * * | | ,:==| | |###|======|###| | |====#==#====#=,, | | * * | | || `| +---+ | | +---+ |' ,,=#==#====O=`` ,| | * * | | || | | | | | | ``=#==#====#=====|| | * * `----------' || | | | | | | |__| `| | * * | | ``=| |===`` `--,',--` `--,',--` /||\ `------' * ** \_/ \_/ / / \ \ / / \ \ //||\\ |_| |_| ** \*** ===================================================================== ***/ /** * 算法，是一系列操作被一步步执行的美称。 * * 数据结构由算法实现，而算法又基于数据结构。数据结构与算法一直往下，直到你看见一群使用打 * 孔卡操作计算机的小人儿。（额- Intel奴役这这群小人儿。醒醒别睡了！！） * * 任何任务都可以有无数的实现方法。所以对于相同的任务，人们会想出很多不同的算法。 * * 比如，有非常庞大的数量的算法可以用来给乱序的事物排序： * * Insertion Sort(插入排序), Selection Sort(选择排序), Merge Sort(归并排序), * Bubble Sort(冒泡排序), Heap Sort(堆排序), Quick Sort(快速排序), * Shell Sort(希尔排序), Timsort, Bucket Sort(桶排序), Radix Sort(基数排序), ... * * 它们之间有一些明显比其他的速度快。有一些使用更少的内存。有一些更容易实现。 * 有一些基于数据集的某些前提。 * * 任何一个都比其他的在 *某方面* 有优势。所以你需要根据你的需求做选择，因此你需要一个考量和 * 比较算法的方法。 * * 我们使用对算法的平均与最差性能进行粗略测量，来比较算法的性能。它被称为"大O"。 */ /*** ===================================================================== ***\ ** - 大O 符号 ------------------------------------------------------------- ** * ========================================================================= * * a b d * * a b O(N^2) d * * O(N!) a b O(N log N) d c * * a b d c * * a b d c O(N) * * a b d c * * a b d c * * a b d c * * ab c O(1) * * e e e e ec d e e e e e e e e * * ba c d * * ba c d f f f f f f f * ** cadf f d f f f f f O(log N) ** \*** ===================================================================== ***/ /** * 大O 符号是粗略测量算法性能的一种方法，以至于可以在讨论的时候对两个算法进行比较。 * * 大O 是计算机科学中借来的一个数学符号。根据算法对给予它元素的数目(N)而表现结果，将算法分类。 * * 你主要可以用大O测量两个东西： * * - **时间复杂度** 表示对于给予一系列元素(N)，算法需要操作的总次数。 * * - **空间复杂度** 表示对于给予一系列元素(N)，算法运行所需要的总内存。 * * 我们在在对比其中一项指标是一定要独立于另一个。因为一个算法可能比另一个需要的操作次数少。 * 它通常需要更多的内存。依照你的需求，选出更好的那一个。 * * 这是一些常见的大O: * * 名称符号当用到它时你的感觉 * ------------------------------------------------------------------------ * 常数 O(1) 爽!! * 对数 O(log N) 不错哦! * 线性 O(N) 还行. * 对数线性 O(N log N) 额... * 平方 O(N ^ 2) 不好 * 指数 O(2 ^ N) 可怕 * 阶乘 O(N!) 艹！ * * 为了给大家一个具体的印象，具体的需要进行多少次操作。我们看一下具体元素数(N)对应的操作数。 * * N = 5 10 20 30 * ----------------------------------------------------------------------- * O(1) 1 1 1 1 * O(log N) 1.6094... 2.3025... 2.9957... 3.4011... * O(N) 5 10 20 30 * O(N log N) 8.0471... 23.0258... 59.9146... 102.0359... * O(N ^ 2) 25 100 400 900 * O(2 ^ N) 32 1024 1,048,576 1,073,741,824 * O(N!) 120 3,628,800 2,432,902,0... 265,252,859,812,191,058,636,308,480,000,000 * * 正如你看到的，即使对于较小的数据集你也可能做*很多*额外的工作。 * * 通过数据结构，你可以进行四种主要的操作： * 访问，查询，插入，和删除。 * * 需要提醒的是，数据结构可能在某方面表现不错，但在另一方面表现很差。 * * Accessing Searching Inserting Deleting * ------------------------------------------------------------------------- * 数组 O(1) O(N) O(N) O(N) * 链表 O(N) O(N) O(1) O(1) * 二叉搜索树 O(log N) O(log N) O(log N) O(log N) * * 或者... * * Accessing Searching Inserting Deleting * ------------------------------------------------------------------------- * 数组爽!! 还行! 还行! 还行! * 链表还行! 还行! 爽!! 爽!! * 二叉搜索树不错哦! 不错哦! 不错哦! 不错哦! * * 设置，一些操作可能会有不同的"平均"性能和"最差"性能。 * * 没有最完美的数据结构，你选择某个数据结构应基于你正在做的东西，和你将要做的事情。 * 这也是为什么了解一系列不同的常见数据结构很重要。你可以从中选择你需要的。 */ /*** ===================================================================== ***\ ** - 内存 -------------------------------------------------------------- ** * ========================================================================= * * _.-.. * * ,'9 )\)`-.,.--. * * `-.| `. * * \, , \) * * `. )._\ (\ * * |// `-,// * * ]|| //" * ** hjw "" "" ** \*** ===================================================================== ***/ /** * 计算机的内存很无聊，它只是一堆可以存放信息的有序的插槽。根据内存地址就可以找到信息。 * * * 让我们把一块内存想象成这个样子： * * 值： |1001|0110|1000|0100|0101|1010|0010|0001|1101|1011... * 地址： 0 1 2 3 4 5 6 7 8 9 ... * * 如果你曾经有过为什么在编程语言里索引是以0开始的疑问，就是因为内存工作方式的原因。 * 如果你想读取内存第一块，你需要从0读到1，第二块需要从1读到2。所以你取得的地址分别为0和1。 * * 你的计算机有比这多很多的内存，而且只是上面模式的延续。 * * 内存和狂野的西部有些相像，运行在你电脑上的每个程序都将数据保存在相同的*物理的*数据结构里。 * 如果不将它一层层的抽象，它将极其难用。 * * 但是这些抽象服务于两个额外的目的： * * - 将数据存在内存中，使得调用时更高效、更快速。 * - 将数据存在内存中，使得更易用。 */ /*** ===================================================================== ***\ ** - LIST ------------------------------------------------------------ ** * ========================================================================= * * * _______________________ * * ()=(_______________________)=() * * * * | | * * | ~ ~~~~~~~~~~~~~ | * * * * * | | * * * | ~ ~~~~~~~~~~~~~ | * * * | | * * | ~ ~~~~~~~~~~~~~ | * * * * | | * * * |_____________________| * * * * ()=(_______________________)=() * ** ** \*** ===================================================================== ***/ /** * 为了演示内存和数据结构之间的相互作用。我们首先准备实现一个LIST。 * * LIST表示一个有序序列，它的值允许重复。 */ class List { /** * 我们先用JavaScript的数组代表一块空内存，并且我们需要保存LIST的长度。 * * 提示，我们另外保存长度(length),是因为真正的"内存"并没有可读取的长度(length)的地方。 */ constructor() { this.memory = []; this.length = 0; } /** * 首先，我们需要从LIST中取得数据的方法。 * * 对于普通的LIST，你可以非常快的访问内存，因为你可以根据地址直接访问。 * * LIST的访问为常量复杂度 O(1) - "爽!!" */ get(address) { return this.memory[address]; } /** * 由于LIST有一个功能，你可以在开头，中间或者结尾插入东西。 * * 在我们的实现中，我们准备实现如下方法，使得可以在LIST的开头或结尾添加删除内容： * * - Push - 在结尾增加值 * - Pop - 删除结尾的值 * - Unshift - 在开头增加值 * - Shift - 删除开头的值 */ /* * 由push开始，我们需要在LIST的结尾增加一个值。 * * 其实很简单，就是在LIST的结尾后面增加一个值，因为我们保存了length，所以很好计算。 * 我们只需要增加一个值然后将长度加一。 * * 在LIST的结尾增加值为常数复杂度 O(1) - "爽!!" */ push(value) { this.memory[this.length] = value; this.length++; } /** * 接下来，我们需要在标的结尾"pop"一个值。 * * 与push相似，我们只需要删除LIST结尾地址的值。然后将长度减一。 * * 删除LIST结尾的值为常数复杂度 O(1) - "爽!!" */ pop() { // 如果没有值，则不操作。 if (this.length === 0) return; // Get the last value, stop storing it, and return it. var lastAddress = this.length - 1; var value = this.memory[lastAddress]; delete this.memory[lastAddress]; this.length--; // Also return the value so it can be used. return value; } /** * "push" 和 "pop" 均是对LIST的结尾操作，总的来说是非常简单的，因为它们都无需考虑LIST中剩下的 * 内容。 * * 让我们看看如果使用"unshift" 和 "shift"操作LIST的开头，会怎样？ */ /** * 想要在LIST的开头增加元素，我们需要将所有的值一个一个的向后移动，从而为新的值空出位置。 * * [a, b, c, d, e] * 0 1 2 3 4 * ⬊ ⬊ ⬊ ⬊ ⬊ * 1 2 3 4 5 * [x, a, b, c, d, e] * * 为了移动LIST中所有的元素，我们需要一个个迭代每个元素。 * * 因为我们要迭代LIST中的每一个元素： * * 在LIST头插入一个值为线性复杂度 O(N) - "还行." */ unshift(value) { // 保存我们要插到首位的元素 var previous = value; // 迭代每一个元素... for (var address = 0; address < this.length; address++) { // 将"当前"值替换为"上一个"值，并为下一次迭代保存当前值。 var current = this.memory[address]; this.memory[address] = previous; previous = current; } // 将最后的值，添加到LIST的新的最后位置。 this.memory[this.length] = previous; this.length++; } /** * 最后我们需要实现shift函数，向相反方向移动。 * * 我们将第一个值删除，然后LIST中的其他值移动到前一个位置。 * * [x, a, b, c, d, e] * 1 2 3 4 5 * ⬋ ⬋ ⬋ ⬋ ⬋ * 0 1 2 3 4 * [a, b, c, d, e] * * 删除LIST中的第一个元素为线性复杂度 O(N) - "还行." */ shift() { // 如果LIST为空，则什么也不做。 if (this.length === 0) return; var value = this.memory[0]; // 迭代每一个元素... for (var address = 0; address < this.length; address++) { // 使用LIST中的下一个元素替换当前元素 this.memory[address] = this.memory[address + 1]; } // 删除最后一个元素，因为它已经移动到了上一个地址 delete this.memory[this.length - 1]; this.length--; return value; } } /** * LIST的优势在于快速访问，和操作最后一个元素。然而正如我们看到的，它并不擅长处理非结尾位置的 * 元素，而且我们需要手动维护地址。 * * 所以，让我们来考一下不同的数据结构，以及它们如何处理添加，访问和无须地址删除值。 */ /*** ===================================================================== ***\ ** - HASH TABLES(哈希表) -------------------------------------------------- ** * ========================================================================= * * ((\ * * ( _ ,-_ \ \ * * ) / \/ \ \ \ \ * * ( /)| \/\ \ \| | .'---------------------'. * * `~()_______)___)\ \ \ \ \ | .' '. * * |)\ ) `' | | | .'-----------------------------'. * * / /, | '...............................' * * ejm | | / \ _____________________ / * * \ / | |_) (_| | * * \ / | | | | * * ) / | | | | * ** / / (___) (___) ** \*** ===================================================================== ***/ /** * 哈希表是一个无序的数据结构。它拥有"keys" 和 "values"，我们可以根据key计算 * 内存中的地址。 * * 基本思想是，我们操作的keys是可以"哈希化(hashable)"的 (我们很快会讲到)，并且可以非常高效地 * 在内存中新增，访问，删除。 * * var hashTable = new HashTable(); * * hashTable.set('myKey', 'myValue'); * hashTable.get('myKey'); // >> 'myValue' */ class HashTable { /** * 同样，我们使用JavaScript的普通数组来代表内存。 */ constructor() { this.memory = []; } /** * 为了将哈希表中的“键值对”保存到内存中，我们需要一个将key转变为地址的方法。 * 我们通过“散列(hashing)”操作完成。 * * 基本上，它需要传入一个key的参数，然后将key序列化为一个唯一的数。 * * hashKey("abc") => 96354 * hashKey("xyz") => 119193 * * 你必须注意，如果有一个很大的key，你要小心，以免它被匹配到一个并不存在的内存地址。 * * 所以哈希算法需要限制大小，这就意味着需要用有限的内存地址，对应无限的值。 * * 最终将会导致冲突，两个不同的key可能会映射到同一个内存地址。 * * 任何一个真正的哈希表在实现时都要处理这个问题。然而我们在这里打算忽略这个问题，假设不会 * 存在这种情况。 */ /** * 我们来建立"hashKey"函数 * * 不要纠结于理解这个函数的逻辑，你只要知道它接收一个string参数，并输出我们在其他函数中需要用到的 * （大多情况下）唯一的内存地址。 */ hashKey(key) { var hash = 0; for (var index = 0; index < key.length; index++) { // Oh look– magic. var code = key.charCodeAt(index); hash = ((hash << 5) - hash) + code | 0; } return hash; } /** * 下面，我们来定义可以根据key取值的“get”函数。 * * 哈希表取值为常数复杂度 O(1) - "爽!!" */ get(key) { // 我们首先将key转化为内存地址。 var address = this.hashKey(key); // 之后只要返回该地址得值。 return this.memory[address]; } /** * 我们在取值之前需要保存数据，所以我们需要定义可以插入值的“set”函数 * * 哈希表插入值为常数复杂度 O(1) - "爽!!" */ set(key, value) { // 同样我们需要先将key转化为内存地址。 var address = this.hashKey(key); // 之后只要改变该地址的值。 this.memory[address] = value; } /** * 最后我们只需要一个将元素从哈希表删除的方法。 * * 哈希表删除为常数复杂度 O(1) - "爽!!" */ remove(key) { // 同样我们需要先将key转化为内存地址。 var address = this.hashKey(key); // 之后，如果这个值存在则将其`delete`。 if (this.memory[address]) { delete this.memory[address]; } } } /** * ============================================================================ * ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-' * ============================================================================ */ /** * 从此往后，我们将不再与内存直接接触，因为剩下的数据结构开始基于其他数据结构而实现。 * * 这些数据结构致力于两件事情： * * - 根据使用方式组织数据。 * - 抽象掉实现详情。 * * 这些数据结构致力于建立一个结构用于各式各样的程序。它们增加了一些特定的语法，可以让你讨论更加 * 复杂的逻辑。它们都将具体的实现逻辑抽象，所以它们可以改变实现逻辑从而变得更快。 */ /*** ===================================================================== ***\ ** - STACKS(栈) ---------------------------------------------------------- ** * ========================================================================= * * _ . - - -- .. _ * * |||| .-' /```\ `'-_ /| * * |||| ( /`` \___/ ```\ ) | | * * \__/ |`"-//..__ __..\\-"`| | | * * || |`"||...__`````__...||"`| | | * * || |`"||...__`````__...||"`| \ | * * || _,.--|`"||...__`````__...||"`|--.,_ || * * || .'` |`"||...__`````__...||"`| `'. || * * || '. `/ |...__`````__...| \ .' || * * || `'-..__ `` ````` `` __..-'` || * * `""---,,,_______,,,---""` * ** ** \*** ===================================================================== ***/ /** * 栈与LIST有些像，因为它们都是有序的，但是栈限制你只能在结尾处“push”或“pop”值，正是我们 * 曾看到的直接映射内存时非常快的操作。 * * 然而，为了给栈增加功能，栈也可以使用其他数据结构实现。 * * 栈最常见的用途是，一个进程向栈中增加元素，另个进程删除最近添加的元素。 */ class Stack { /** * 我们又一次使用JavaScript数组，但是这一次它代表一个类似于我们之前实现的LIST而非内存。 */ constructor() { this.list = []; this.length = 0; } /** * 我们需要使用LIST的"push"和"pop"方法实现两个函数。 * 在功能方面是相同的。 */ /** * push将元素增加到栈顶 */ push(value) { this.length++; this.list.push(value); } /** * pop删除栈顶的元素 */ pop() { // 如果没有内容则什么也不做 if (this.length === 0) return; // 删除栈顶元素并将其返回 this.length--; return this.list.pop(); } /** * 我们还需要增加一个方法，可以取得栈顶的元素，但不删除它。 */ peek() { // 返回栈顶元素，但不删除。 return this.list[this.length - 1]; } } /*** ===================================================================== ***\ ** - QUEUES(队列) --------------------------------------------------------- ** * ========================================================================= * * /:""| ,@@@@@@. * * |: oo|_ ,@@@@@`oo * * C _) @@@@C _) * * ) / "@@@@ '= * * /`\\ ```)/ * * || | | /`\\ * * || | | || | \ * * ||_| | || | / * * \( ) | ||_| | * * |~~~`-`~~~| |))) | * * (_) | | (_) |~~~/ (_) * * | |`""....__ __....""`| |`""...._|| / __....""`| | * * | |`""....__`````__....""`| |`""....__`````__....""`| | * * | | | ||``` | | ||`|`` | | * * | | |_||__ | | ||_|__ | | * * ,| |, jgs (____)) ,| |, ((;:;:) ,| |, * ** `---` `---` `---` ** \*** ===================================================================== ***/ /** * 接下来，我们准备实现队列，它与栈类似，区别是它从队列头部删除元素而非头部。 * 删除最早的元素而非最新的元素。 * * 同样，因为有限的功能，队列同样有很多不同的实现方式。使用链表实现或许是一个好方法，之后 * 会为大家介绍。 */ class Queue { /** * 同样，队列使用JavaScript的数组代表LIST而非内存 */ constructor() { this.list = []; this.length = 0; } /** * 与栈相似，我们需要定义两个方法用来增加和删除队列中的元素。 * 首先是"enqueue"。 * * 它将向队列尾部增加元素 */ enqueue(value) { this.length++; this.list.push(value); } /** * 接下来是"dequeue"，这次我们从头部删除元素，而非从尾部。 */ dequeue() { // 如果没有内容则什么也不做 if (this.length === 0) return; // shift取出第一个元素并将其返回 this.length--; return this.list.shift(); } /** * 与栈相似，我们需要一个"peek"函数来取得下一个元素，但不删除它 */ peek() { return this.list[0]; } } /** * 需要强调的是，由于我们的队列是基于LIST实现的。所以也继承了"shift"的性能， * 线性复杂度 O(N) "还行." * * 之后会为大家介绍链表(linked list)，它可以让我们实现一个更快的队列。 */ /** * ============================================================================ * ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-' * ============================================================================ */ /** * 从此往后，我们将开始操作数据结构，一个数据结构的值引用另一个数据结构。 * * +- Data Structure ---------------------------------------+ * | +- Item A ---------------+ +- Item B ---------------+ | * | | Value: 1 | | Value: 2 | | * | | Reference to: (Item B) | | Reference to: (Item A) | | * | +------------------------+ +------------------------+ | * +--------------------------------------------------------+ * * 数据结构的值将会是属于它自己的更小的数据结构，其中包含了一些附加的信息，包括指向大数据结构中 * 其他元素的引用。 * * 你将很快明白我在说什么。 */ /*** ===================================================================== ***\ ** - GRAPHS(图) -------------------------------------------------------------- ** * ========================================================================= * * * * | RICK ASTLEY'S NEVER GONNA... * * | +-+ * * | +-+ |-| [^] - GIVE YOU UP * * | |^| |-| +-+ [-] - LET YOU DOWN * * | |^| |-| +-+ |*| [/] - RUN AROUND AND DESERT YOU * * | |^| |-| +-+ |\| |*| [\] - MAKE YOU CRY * * | |^| |-| |/| |\| +-+ |*| [.] - SAY GOODBYE * * | |^| |-| |/| |\| |.| |*| [*] - TELL A LIE AND HURT YOU * * | |^| |-| |/| |\| |.| |*| * * +-------------------------------- * ** ** \*** ===================================================================== ***/ /** * 与上面的字符图不同，图并不是某种类型的可视化图表。 * * 而是把它想象成这个样子： * * A –→ B ←–––– C → D ↔ E * ↑ ↕ ↙ ↑ ↘ * F –→ G → H ← I ––––→ J * ↓ ↘ ↑ * K L * * 我们有一堆用线彼此相连的“节点(node)” (A, B, C, D, ...)。 * * 这些节点看上去是这样的： * * Node { * value: ..., * lines: [(Node), (Node), ...] * } * * 整个图，看上去是这样的： * * Graph { * nodes: [ * Node {...}, * Node {...}, * ... * ] * } */ class Graph { /** * 我们准备将所有的节点放到JavaScript普通数组里。并非因为各个节点之间存在顺序，而是因为 * 我们需要一种保存所有引用的方式。 */ constructor() { this.nodes = []; } /** * 我们可以向创建的nodes里添加值，无需添加任何联系(lines)。 */ addNode(value) { this.nodes.push({ value: value, lines: [] }); } /** * 下面，我们需要在图里查找nodes。大多情况下为了让搜索更快，在图之上会创建另一个 * 数据结构。 * * 但是我们这里，只想简单的遍历所有的nodes，来查找我们需要的值。这是一个低效的选择， * 但在此还是够用的。 */ find(value) { return this.nodes.find(function(node) { return node.value === value; }); } /** * 下面我们可以在两个节点通过一条"线(line)"连接起来。 */ addLine(startValue, endValue) { // 找到各个值所对应的节点 var startNode = this.find(startValue); var endNode = this.find(endValue); // 节点不存在时抛出错误 if (!startNode || !endNode) { throw new Error('Both nodes need to exist'); } // 为startNode添加endNode的索引。 startNode.lines.push(endNode); } } /** * 最后你可以这样使用图： * * var graph = new Graph(); * graph.addNode(1); * graph.addNode(2); * graph.addLine(1, 2); * var two = graph.find(1).lines[0]; * * 这看起来或许费了很多功夫做了很少的事情，但是它其实是一个很强大的模式，尤其是在复杂 * 程序中查找想要的东西时。 * * 它们通过优化数据间的联系实现，而非操作数据本身。如果你知道图中有某个节点，那就很容易找到 * 图中与它有关系的所有元素了。 * * 太多东西都可以用这种方式抽象，好友圈，node_modules文件夹中的传递依赖，因特网本身也是 * 通过链接将网页连接到一起的图。 */ /*** ===================================================================== ***\ ** - LINKED LISTS(链表) --------------------------------------------------- ** * ========================================================================= * * _______________________ * * ()=(_______________________)=() ,-----------------,_ * * | | ," ", * * | ~ ~~~~~~~~~~~~~ | ,' ,---------------, `, * * | ,----------------------------, ,----------- * * | ~ ~~~~~~~~ | | | * * | `----------------------------' `----------- * * | ~ ~~~~~~~~~~~~~ | `, `----------------' ,' * * | | `, ,' * * |_____________________| `------------------' * * ()=(_______________________)=() * ** ** \*** ===================================================================== ***/ /** * 下面，将为大家介绍类-图结构怎样帮助优化数据列表的。 * * Linked lists(链表)是非常常见的数据结构，由于它向开头，中间及结尾插入元素都非常的高效， * 所以它常常被用与实现其他的数据结构。 * * 链表的基础理念和图非常像。一个节点指向另一个节点，它看上去大概是这样的： * * 1 -> 2 -> 3 -> 4 -> 5 * * 将其可视化为类JSON结构，看上去像这个样子： * * { * value: 1, * next: { * value: 2, * next: { * value: 3, * next: {...} * } * } * } */ class LinkedList { /** * 与图不同，整个链表只有一个节点作为链的开头。被称为链表的"head(头部)"。 * * 我们同样打算记录链表的长度。 */ constructor() { this.head = null; this.length = 0; } /** * 首先我们需要一个方法取得所给位置的值。 * * 这与常见的list不太一样，我们不能直接跳到对应的位置。而是需要在每个节点上移动。 */ get(position) { // 如果该位置比元素总数还大，则抛出错误 if (position >= this.length) { throw new Error('Position outside of list range'); } // 从头结点开始 var current = this.head; // 使用node.next通过每一个元素，直到到达给定的位置。 for (var index = 0; index < position; index++) { current = current.next; } // 返回我们找到的节点。 return current; } /** * 下面我们需要向特定的位置增加节点。 * * 我们准备建立一个通用的add方法，接收value和position参数。 */ add(value, position) { // 首先创建一个node承载value。 var node = { value: value, next: null }; // 将节点插入到头部是一个特殊情况。 // 我们将要插入节点的"next"参数指向当前的头部，再用其替代头部。 if (position === 0) { node.next = this.head; this.head = node; // 如果我们要在其他位置插入节点，我们需要将它与此位置当前的节点，和上一个节点连接到一起。 } else { // 首先找到当前位置的节点，与上一个节点。 var prev = this.get(position - 1); var current = prev.next; // 之后将要插入节点的"next"参数指向当前位置的节点，再将上一个节点的"next"参数改为 // 要插入的新节点。 node.next = current; prev.next = node; } // 最后增加length。 this.length++; } /** * 最后我们需要一个删除方法。我们只需找到相应的节点，然后将其从链中剔除。 */ remove(position) { // 如果要删除第一个节点的话，只需要将head指向第二个节点。 if (position === 0) { this.head = this.head.next; // 对于其他位置，我们需要找到它的上一个节点，然后将上一个节点 // 的"next"参数设为当前位置节点的下一个节点。 } else { var prev = this.get(position - 1); prev.next = prev.next.next; } // 然后减小length this.length--; } } /** * ============================================================================ * ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-' * ============================================================================ */ /** * 我们准备了解的剩下的两个数据结构都属于"tree(树)"家族。 * * 和现实中一样，有很多不同种类的树的数据结构。(译者：恕我无能) * * Binary Trees: * AA Tree, AVL Tree, Binary Search Tree, Binary Tree, Cartesian Tree, * left child/right sibling tree, order statistic tree, Pagoda, ... * * B Trees: * B Tree, B+ Tree, B* Tree, B Sharp Tree, Dancing Tree, 2-3 Tree, ... * * Heaps: * Heap, Binary Heap, Weak Heap, Binomial Heap, Fibonacci Heap, Leonardo * Heap, 2-3 Heap, Soft Heap, Pairing Heap, Leftist Heap, Treap, ... * * Trees: * Trie, Radix Tree, Suffix Tree, Suffix Array, FM-index, B-trie, ... * * Multi-way Trees: * Ternary Tree, K-ary tree, And-or tree, (a,b)-tree, Link/Cut Tree, ... * * Space Partitioning Trees: * Segment Tree, Interval Tree, Range Tree, Bin, Kd Tree, Quadtree, * Octree, Z-Order, UB-Tree, R-Tree, X-Tree, Metric Tree, Cover Tree, ... * * Application-Specific Trees: * Abstract Syntax Tree, Parse Tree, Decision Tree, Minimax Tree, ... * * 你肯定没想到，今天你会在这里学习树木学……而且那还不是所有的树。但是不要害怕，它们中的大多数 * 并不重要。它们只是很多计算机科学博士需要证明一些东西的时候用到的。 * * 树对于图还有链表在除了它是“单向的”方面，其他方面都很像。也就是说，它不会有引用循环。 * * 树: 非树: * * A A * ↙ ↘ ↗ ↘ * B C B ←–––– C * * 如果你在树的节点之间建立了循环的联系，那么它就不再是树了。 * * 树有很多用处，它可以用于优化搜索和排序。它可以让你更好的组织程序。它可以为你提供更易工作的 * 形式。 */ /*** ===================================================================== ***\ ** - TREES(树) ----------------------------------------------------------- ** * ========================================================================= * * ccee88oo \ | / * * C8O8O8Q8PoOb o8oo '-.;;;.-, ooooO8O8QOb o8bDbo * * dOB69QO8PdUOpugoO9bD -==;;;;;==-aadOB69QO8PdUOpugoO9bD * * CgggbU8OU qOp qOdoUOdcb .-';;;'-. CgggOU ddqOp qOdoUOdcb * * 6OuU /p u gcoUodpP / | \ jgs ooSec cdac pdadfoof * * \\\// /douUP ' \\\d\\\dp/pddoo * * \\\//// \\ \\//// * * |||/\ \\/// * * |||\/ |||| * * ||||| /||| * ** .............//||||\.......................//|||\\..................... ** \*** ===================================================================== ***/ /** * 我们从一个非常简单的树结构起步。它没有任何特殊的规则，看起来是这样的： * * Tree { * root: { * value: 1, * children: [{ * value: 2, * children: [...] * }, { * value: 3, * children: [...] * }] * } * } */ class Tree { /** * 树由一个parent开始，他被称为树的"root"。 */ constructor() { this.root = null; } /** * 我们需要一种方法来遍历整个数，对于每个node都会调用传入的callback函数。 */ traverse(callback) { // 我们定义一个walk函数，它可以递归地遍历树的每一个节点。 function walk(node) { // 首先为此节点调用callback callback(node); // 然后为他的子节点递归调用walk。 node.children.forEach(walk); } // Now kick the traversal process off. walk(this.root); } /** * 下面我们需要向树添加节点的方法 */ add(value, parentValue) { var newNode = { value: value, children: [] }; // 如果没有root，则将其设为root。 if (this.root === null) { this.root = newNode; return; } // 否则遍历整个树，查找匹配的节点，然后将新节点设为它的子节点。 this.traverse(function(node) { if (node.value === parentValue) { node.children.push(newNode); } }); } } /** * 这是一个最基础的树，它可能只有在你想代表的数据酷似树的时候才有用。 * * 但是，添加一些额外的规则，树可以为很多不同的需求服务。 */ /*** ===================================================================== ***\ ** - BINARY SEARCH TREES(二叉搜索树) --------------------------------------- ** * ========================================================================= * * 0 0 1 0 1 0 0 1 0 1 1 1 0 1 ,@@@@@@@@@@@@@@, 0 0 1 0 1 0 0 1 0 1 1 1 0 * * 0 1 0 1 0 1 0 1 1 0 1 1 0 @@` '@@ 0 1 0 1 0 1 1 0 1 0 1 0 * * 1 1 0 0 0 1 0 0 1 1 1 0 @@` 8O8PoOb o8o '@@ 0 0 1 0 0 1 0 0 1 1 1 * * 0 0 1 1 0 1 0 1 0 0 0 @@ dOB69QO8PdUgoO9bD @@ 1 0 1 1 0 1 0 1 0 0 * * ===================== @@ CgbU8OU qOp qOdOdcb @@ 0 1 1 0 1 0 1 0 1 0 * * @@ 6OU /p u gcoUpP @@ 1 0 1 1 0 1 0 0 1 1 * * ===================== @@ \\// /doP @@ 0 1 1 0 0 1 0 0 1 0 * * 1 1 0 0 1 1 0 1 1 0 0 @@ \\// @@ 1 0 1 0 0 1 1 0 1 1 * * 0 1 1 0 1 0 1 1 0 1 1 0 @@, ||| ,@@ 0 1 1 0 1 1 0 0 1 0 1 * * 1 0 1 0 1 1 0 0 1 0 0 1 0 @@, //|\ ,@@ 0 1 0 1 0 1 1 0 0 1 1 0 * ** 1 0 1 0 0 1 1 0 1 0 1 0 1 `@@@@@@@@@@@@@@' 0 1 1 1 0 0 1 0 1 0 1 1 ** \*** ===================================================================== ***/ /** * 二叉搜索树是树的一个非常普遍的方式，因为它可以高效的访问，搜索，插入以及删除值，同时 * 保持它们有序。 * * 假如有这么一串数字： * * 1 2 3 4 5 6 7 * * 让后将其转换为从中间开始的树。 * * 4 * / \ * 2 6 * / \ / \ * 1 3 5 7 * -^--^--^--^--^--^--^- * 1 2 3 4 5 6 7 * * 二叉树是这样工作的。每个节点有两个子节点： * * - 左节点: 比父节点的值小。 * - 右节点: 比父节点的值大。 * * > 提示: 树中的值必须唯一。 * * 这使得遍历查值使非常的有效率。比如我们想要找到树种的5： * * (4) <--- 5 > 4, 向右. * / \ * 2 (6) <--- 5 < 6, 向左. * / \ / \ * 1 3 (5) 7 <--- 找到 5! * * 需要强调的是，我们只需要3此判断就找到了5。如果我们将这个树扩充到1000个元素。 * 我们需要: * * 500 -> 250 -> 125 -> 62 -> 31 -> 15 -> 7 -> 3 -> 4 -> 5 * * 1000个元素仅需10次判断！ * * 另一个，二叉搜索树在删除或新增值时和链表很像，你只需更新它周围的元素就可以。 */ class BinarySearchTree { /** * 和之前的树一样，二叉搜索树也有"root". */ constructor() { this.root = null; } /** * 想要知道，某个值是否在树里，我们需要在树中搜索。 */ contains(value) { // 从root开始 var current = this.root; // 只要有下一个节点，我们就要继续搜索。 // 如果`left` 或 `right` 的值为 `null` 便结束搜索。 while (current) { // 如果比current.value大，则移向右节点 if (value > current.value) { current = current.right; // 如果比current.value小，则移向左节点 } else if (value < current.value) { current = current.left; // 否则肯定是相等，那么返回true } else { return true; } } // 如果没有匹配项，返回false return false; } /** * 像树种添加元素，同样需要向之前那样遍历树，向左或向右取决于此节点大于或小于我们准备 * 增加的值。 * * 不同的是，如果最终 `left` 或 `right` 是 `null` 时，我们将新的节点放在此位置。 */ add(value) { // 首先初始化节点。 var node = { value: value, left: null, right: null }; // 对于没有root的特殊情况，我们只需要将其设为root。 if (this.root === null) { this.root = node; return; } // 由root开始。 var current = this.root; // 持续循环，直到新节点添加完成，或发现该值已存在。 while (true) { // 如果比current.value大，则移向右节点 if (value > current.value) { // 如果 `right` 不存在，将其设为我们的节点并停止遍历。 if (!current.right) { current.right = node; break; } // 否则移向右节点 current = current.right; // 如果比current.value小，则移向左节点 } else if (value < current.value) { // 如果 `left` 不存在，将其设为我们的节点并停止遍历。 if (!current.left) { current.left = node; break; } // 否则移向左节点 current = current.left; // 如果要插入的值已存在则终止 } else { break; } } } } /*** ===================================================================== ***\ ** - YOU REACHED THE END! ------------------------------------------------ ** * ========================================================================= * * .''. * * .''. *''* :_\/_: . * * :_\/_: . .:.*_\/_* : /\ : .'.:.'. * * .''.: /\ : _\(/_ ':'* /\ * : '..'. -=:o:=- * * :_\/_:'.:::. /)\*''* .|.* '.\'/.'_\(/_'.':'.' * * : /\ : ::::: '*_\/_* | | -= o =- /)\ ' * * * '..' ':::' * /\ * |'| .'/.\'. '._____ * * * __*..* | | : |. |' .---"| * * _* .-' '-. | | .--'| || | _| | * * .-'| _.| | || '-__ | | | || | * * |' | |. | || | | | | || | * * _____________| '-' ' "" '-' '-.' '` |____________ * ** jgs~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ** \*** ===================================================================== ***/ /** * 可能内容有些多，但我希望它对你有帮助。如果你喜欢这些内容，欢迎star项目 * 或者粉我的twitter (@thejameskyle)? * * 你也可以看一下我的另一篇文章 "The Super Tiny Compiler" * here ------> https://github.com/thejameskyle/the-super-tiny-compiler */ // Just exporting everything for the tests... module.exports = { List: List, HashTable: HashTable, Stack: Stack, Queue: Queue, Graph: Graph, LinkedList: LinkedList, Tree: Tree, BinarySearchTree: BinarySearchTree }; ```