简易数据结构
简易数据结构
译自：https://github.com/thejameskyle/itsy-bitsy-data-structures
'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
};
1 回复
