简易数据结构

今天我们将要了解并学习数据结构。

"OOooooOOOooh *soo* exciting" right?

没错，它不是最有内容的话题，但它很重要。并非为了向计算机输入奇怪的101，而是让自己成为一名
更好的程序员。

理解数据结构可以让你：

  • 管理复杂的系统，并使你的代码更易维护。
  • 构建高性能，高效率的应用。

我认为前者更重要一些。使用正确的数据结构可以大幅简化本来很复杂的逻辑。

当然后者同样重要。如果关心性能和内存，应用正确的数据机构比通常的解决方案更重要。

为了了解数据结构，我们准备尝试一起实现它们中的一部分。别怕，我们将保持代码的简洁。
实际上，注释要比代码多。

1
2
3
4
5
/**
 * ============================================================================
 * ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
 * ============================================================================
 */

什么是数据结构？

实际上，他们是一些不同的存储和组织数据的方法，供若干不同的需求使用。

数据总可以以很多不同的方式表现。然而，基于数据的具体内容与它的用途，总有一种表现方式更优一些。

想要理解为什么，让我们先简单聊一聊算法。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** ===================================================================== ***\
 ** - 算法 ---------------------------------------------------------------- **
 * ========================================================================= *
 *                                                                           *
 *                        ,--,--.    ,--,--.                                 *
 *   ,----------.        |   |   |  |   |   |            _____               *
 *  |`----------'|       |   |   |  |   |   |           |     |    ,------.  *
 *  |            |       |   |   |  |   |   |      ,--. | 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 符号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*** ===================================================================== ***\
 ** - 大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
数组 爽!! 还行! 还行! 还行!
链表 还行! 还行! 爽!! 爽!!
二叉搜索树 不错哦! 不错哦! 不错哦! 不错哦!

设置，一些操作可能会有不同的”平均”性能和”最差”性能。

没有最完美的数据结构，你选择某个数据结构应基于你正在做的东西，和你将要做的事情。
这也是为什么了解一系列不同的常见数据结构很重要。你可以从中选择你需要的。

内存

1
2
3
4
5
6
7
8
9
10
11
12
/*** ===================================================================== ***\
 ** - 内存 -------------------------------------------------------------- **
 * ========================================================================= *
 *                             _.-..                                         *
 *                           ,'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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** ===================================================================== ***\
 ** - LIST ------------------------------------------------------------ **
 * ========================================================================= *
 *                  *     _______________________                            *
 *                    ()=(_______________________)=()           *            *
 *       *                |                     |                            *
 *                        |   ~ ~~~~~~~~~~~~~   |       *               *    *
 *             *          |                     |                            *
 *   *                    |   ~ ~~~~~~~~~~~~~   |         *                  *
 *                        |                     |                            *
 *                        |   ~ ~~~~~~~~~~~~~   |                 *          *
 *        *               |                     |                            *
 *                   *    |_____________________|         *        *         *
 *                    ()=(_______________________)=()                        *
 **                                                                         **
\*** ===================================================================== ***/

为了演示内存和数据结构之间的相互作用。我们首先准备实现一个LIST。

LIST表示一个有序序列，它的值允许重复。

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
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(哈希表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** ===================================================================== ***\
 ** - HASH TABLES(哈希表) -------------------------------------------------- **
 * ========================================================================= *
 *                           ((\                                             *
 *     (              _  ,-_  \ \                                            *
 *     )             / \/  \ \ \ \                                           *
 *     (            /)| \/\ \ \| |          .'---------------------'.        *
 *     `~()_______)___)\ \ \ \ \ |        .'                         '.      *
 *                 |)\ )  `' | | |      .'-----------------------------'.    *
 *                /  /,          |      '...............................'    *
 *        ejm     |  |          /         \   _____________________   /      *
 *                \            /           | |_)                 (_| |       *
 *                 \          /            | |                     | |       *
 *                  )        /             | |                     | |       *
 **                /       /              (___)                   (___)     **
\*** ===================================================================== ***/

哈希表是一个无序的数据结构。它拥有”keys” 和 “values”，我们可以根据key计算
内存中的地址。

基本思想是，我们操作的keys是可以”哈希化(hashable)”的 (我们很快会讲到)，并且可以非常高效地
在内存中新增，访问，删除。

var hashTable = new HashTable();

hashTable.set('myKey', 'myValue');
hashTable.get('myKey'); // >> 'myValue'

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
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];
    }
  }
}
1
2
3
4
5
/**
 * ============================================================================
 * ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
 * ============================================================================
 */

从此往后，我们将不再与内存直接接触，因为剩下的数据结构开始基于其他数据结构而实现。

这些数据结构致力于两件事情：

  • 根据使用方式组织数据。

  • 抽象掉实现详情。

    这些数据结构致力于建立一个结构用于各式各样的程序。它们增加了一些特定的语法，可以让你讨论更加
    复杂的逻辑。它们都将具体的实现逻辑抽象，所以它们可以改变实现逻辑从而变得更快。

STACKS(栈)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** ===================================================================== ***\
 ** - STACKS(栈) ---------------------------------------------------------- **
 * ========================================================================= *
 *                             _ . - - -- .. _                               *
 *         ||||            .-'      /```\     `'-_             /|            *
 *         ||||           (     /`` \___/ ```\    )           | |            *
 *         \__/           |`"-//..__     __..\\-"`|           | |            *
 *          ||            |`"||...__`````__...||"`|           | |            *
 *          ||            |`"||...__`````__...||"`|           \ |            *
 *          ||       _,.--|`"||...__`````__...||"`|--.,_       ||            *
 *          ||    .'`     |`"||...__`````__...||"`|     `'.    ||            *
 *          ||   '.        `/ |...__`````__...| \         .'   ||            *
 *          ||     `'-..__  ``      `````      ``  __..-'`     ||            *
 *                        `""---,,,_______,,,---""`                          *
 **                                                                         **
\*** ===================================================================== ***/

栈与LIST有些像，因为它们都是有序的，但是栈限制你只能在结尾处“push”或“pop”值，正是我们
曾看到的直接映射内存时非常快的操作。

然而，为了给栈增加功能，栈也可以使用其他数据结构实现。

栈最常见的用途是，一个进程向栈中增加元素，另个进程删除最近添加的元素。

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
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(队列)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*** ===================================================================== ***\
 ** - QUEUES(队列) --------------------------------------------------------- **
 * ========================================================================= *
 *                   /:""|                     ,@@@@@@.                      *
 *                  |: oo|_                   ,@@@@@`oo                      *
 *                  C     _)                  @@@@C   _)                     *
 *                    ) /                     "@@@@ '=                       *
 *                   /`\\                      ```)/                         *
 *                  || | |                       /`\\                        *
 *                  || | |                      || | \                       *
 *                  ||_| |                      || | /                       *
 *                  \( ) |                      ||_| |                       *
 *               |~~~`-`~~~|                    |))) |                       *
 *         (_)   |         |         (_)        |~~~/          (_)           *
 *         | |`""....__     __....""`| |`""...._|| /  __....""`| |           *
 *         | |`""....__`````__....""`| |`""....__`````__....""`| |           *
 *         | |       | ||```         | |        ||`|``         | |           *
 *         | |       |_||__          | |        ||_|__         | |           *
 *        ,| |, jgs  (____))        ,| |,       ((;:;:)       ,| |,          *
 **       `---`                     `---`                     `---`         **
\*** ===================================================================== ***/

接下来，我们准备实现队列，它与栈类似，区别是它从队列头部删除元素而非头部。
删除最早的元素而非最新的元素。

同样，因为有限的功能，队列同样有很多不同的实现方式。使用链表实现或许是一个好方法，之后
会为大家介绍。

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 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)，它可以让我们实现一个更快的队列。

1
2
3
4
5
/**
 * ============================================================================
 * ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
 * ============================================================================
 */

从此往后，我们将开始操作数据结构，一个数据结构的值引用另一个数据结构。

+- Data Structure ---------------------------------------+
|  +- Item A ---------------+ +- Item B ---------------+ |
|  | Value: 1               | | Value: 2               | |
|  | Reference to: (Item B) | | Reference to: (Item A) | |
|  +------------------------+ +------------------------+ |
+--------------------------------------------------------+

数据结构的值将会是属于它自己的更小的数据结构，其中包含了一些附加的信息，包括指向大数据结构中
其他元素的引用。

你将很快明白我在说什么。

GRAPHS(图)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** ===================================================================== ***\
 ** - 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, …)。

这些节点看上去是这样的：

1
2
3
4
Node {
  value: ...,
  lines: [(Node), (Node), ...]
}

整个图，看上去是这样的：

1
2
3
4
5
6
7
Graph {
  nodes: [
    Node {...},
    Node {...},
    ...
  ]
}
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
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);
  }
}

最后你可以这样使用图：

1
2
3
4
5
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(链表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** ===================================================================== ***\
 ** - LINKED LISTS(链表) --------------------------------------------------- **
 * ========================================================================= *
 *      _______________________                                              *
 *  ()=(_______________________)=()              ,-----------------,_        *
 *      |                     |               ,"                      ",     *
 *      |   ~ ~~~~~~~~~~~~~   |             ,'    ,---------------,     `,   *
 *      |               ,----------------------------,          ,----------- *
 *      |   ~ ~~~~~~~~ |                              |        |             *
 *      |               `----------------------------'          `----------- *
 *      |   ~ ~~~~~~~~~~~~~   |            `,    `----------------'     ,'   *
 *      |                     |              `,                      ,'      *
 *      |_____________________|                 `------------------'         *
 *  ()=(_______________________)=()                                          *
 **                                                                         **
\*** ===================================================================== ***/

下面，将为大家介绍类-图结构怎样帮助优化数据列表的。

Linked lists(链表)是非常常见的数据结构，由于它向开头，中间及结尾插入元素都非常的高效，
所以它常常被用与实现其他的数据结构。

链表的基础理念和图非常像。一个节点指向另一个节点，它看上去大概是这样的：

1 -> 2 -> 3 -> 4 -> 5

将其可视化为类JSON结构，看上去像这个样子：

1
2
3
4
5
6
7
8
9
10
{
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {...}
    }
  }
}

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
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--;
  }
}
1
2
3
4
5
/**
 * ============================================================================
 * ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
 * ============================================================================
 */

我们准备了解的剩下的两个数据结构都属于”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, ...

你肯定没想到，今天你会在这里学习树木学……而且那还不是所有的树。但是不要害怕，它们中的大多数
并不重要。它们只是很多计算机科学博士需要证明一些东西的时候用到的。

树对于图还有链表在除了它是“单向的”方面，其他方面都很像。也就是说，它不会有引用循环。

1
2
3
4
5
    树:                     非树:

    A                        A
  ↙   ↘                    ↗   ↘
B       C                B ←–––– C

如果你在树的节点之间建立了循环的联系，那么它就不再是树了。

树有很多用处，它可以用于优化搜索和排序。它可以让你更好的组织程序。它可以为你提供更易工作的
形式。

TREES(树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*** ===================================================================== ***\
 ** - 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               *
 *               \\\////                         \\ \\////                   *
 *                |||/\                           \\///                      *
 *                |||\/                           ||||                       *
 *                |||||                          /|||                        *
 ** .............//||||\.......................//|||\\..................... **
\*** ===================================================================== ***/

我们从一个非常简单的树结构起步。它没有任何特殊的规则，看起来是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
Tree {
  root: {
    value: 1,
    children: [{
      value: 2,
      children: [...]
    }, {
      value: 3,
      children: [...]
    }]
  }
}

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
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(二叉搜索树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*** ===================================================================== ***\
 ** - 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

让后将其转换为从中间开始的树。

1
2
3
4
5
6
7
          4
       /     \
    2           6
  /   \       /   \
 1     3     5     7
-^--^--^--^--^--^--^-
 1  2  3  4  5  6  7

二叉树是这样工作的。每个节点有两个子节点：

  • 左节点: 比父节点的值小。

  • 右节点: 比父节点的值大。

    提示: 树中的值必须唯一。

    这使得遍历查值使非常的有效率。比如我们想要找到树种的5：

1
2
3
4
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次判断！

另一个，二叉搜索树在删除或新增值时和链表很像，你只需更新它周围的元素就可以。

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
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!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*** ===================================================================== ***\
 ** - YOU REACHED THE END! ------------------------------------------------ **
 * ========================================================================= *
 *                                           .''.                            *
 *                 .''.             *''*    :_\/_:     .                     *
 *                :_\/_:   .    .:.*_\/_*   : /\ :  .'.:.'.                  *
 *            .''.: /\ : _\(/_  ':'* /\ *  : '..'.  -=:o:=-                  *
 *           :_\/_:'.:::. /)\*''*  .|.* '.\'/.'_\(/_'.':'.'                  *
 *           : /\ : :::::  '*_\/_* | |  -= o =- /)\    '  *                  *
 *            '..'  ':::'   * /\ * |'|  .'/.\'.  '._____                     *
 *                *        __*..* |  |     :      |.   |' .---"|             *
 *                 _*   .-'   '-. |  |     .--'|  ||   | _|    |             *
 *              .-'|  _.|  |    ||   '-__  |   |  |    ||      |             *
 *              |' | |.    |    ||       | |   |  |    ||      |             *
 * _____________|  '-'     '    ""       '-'   '-.'    '`      |____________ *
 ** jgs~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ **
\*** ===================================================================== ***/

可能内容有些多，但我希望它对你有帮助。如果你喜欢这些内容，欢迎star项目
或者粉我的twitter (@thejameskyle)?

你也可以看一下我的另一篇文章 “The Super Tiny Compiler”
here ——> https://github.com/thejameskyle/the-super-tiny-compiler