单元 1.4.2 数据结构

结构

记录

一个无序的数据结构，其元素通过属性名称访问。这使得结构更易于使用，因为属性名称描述了存储的数据。

所有属性必须在记录可以使用之前定义。这使得结构的初始化更复杂。

person
first_name	last_name	email
John	Smith	[email protected]

person.first_name // John
person.email // [email protected]

列表

一个有序的数据结构，其元素通过索引访问。

employee_ids
0	1	2
0048_jsmith	0064_jbloggs	0073_jdoe

employee_ids[0] // 0048_jsmith
employee_ids[2] // 0073_jdoe

元组

一个不可变的列表（存储的数据不能修改）。

对于需要保持不变但可以通过索引访问的数据很有用。

链表

链表是存储数据的列表，其中包含指向列表中下一项的指针。列表中的最后一项的指针为 0 或 null，表示列表的结尾。

除了动态之外，链表的主要优势在于元素可以高效地插入到任何位置 - 只需更改几个指针即可。

以下是用表格表示的链表示例：名称指向字母表中下一个人的位置。

start = 3 //表示链表从 3 开始（因为 A 在字母表的开头）

nextFree = 4 //表示一个可用的空间，下一个要添加的项目将被添加在这里

索引	姓名	指针
0	Lain	2
1	JoJo	0
2	Miku	null
3	Ash	1
4		null

假设我们要将 Mikasa 插入链表

我们首先将 Mikasa 放入由 nextFree 指针给出的空间中。
接下来，我们会弄清楚我们想要将 Mikasa 放在列表中的哪个位置。因为我们决定链接到字母表中的下一个项目，所以 Mikasa 将出现在 Miku 之前，但出现在 Lain 之后。因此，Mikasa 需要成为列表中的第 4 项。例如，insert(3, "Mikasa") //3 指的是第 4 个位置，因为链表从 0 开始
Lains 指针被更改为指向 Mikasa（设置为 4）
Mikasa 的指针被设置为指向 Miku（设置为 2）
最后，nextFree 指针将被设置为 5（下一个空闲位置）

因此，更新后的链表将如下所示

start = 3 //表示链表从 3 开始（因为 A 在字母表的开头）

nextFree = 5 //表示一个可用的空间，下一个要添加的项目将被添加在这里

索引	姓名	指针
0	Lain	2 4
1	JoJo	0
2	Miku	null
3	Ash	1
4	Mikasa	~~null~~ 2
5		null

链表的可能用途

实现撤销功能
处理浏览器缓存
帮助操作系统作业队列

描述数组和链表之间的区别。[2]

答案

链表是一种动态数据结构 (1)，而数组是静态的 (1)。数组可以访问任何元素（即随机访问） (1)，而链表需要遍历到找到所需元素为止 (1)。数组的内容在内存中是连续存储的 (1)，而链表的内容可能不是 (1)。

数组

数组是一种有序的数据结构，通过索引访问。它包含一组通常为相同类型的元素。因此，它是一种复合类型，因为它用预先存在的数据类型形成数据结构。默认情况下，数组在定义时需要指定其大小，这是其中的元素数量。不能将元素添加到超出此大小的索引中。这在大多数编程语言中都是遵守的，但一些语言（特别是 Python 和 JavaScript 是例外，因为它们使用列表作为所有定义数组的底层数据结构）打破了规则。

一维数组

一维数组包含一组属性，每个属性都通过其索引访问。它们几乎与列表近似，只是它们的大小是固定的。

employee_ids
0	1	2
0048_jsmith	0064_jbloggs	0073_jdoe

employee_ids[0] // 0048_jsmith
employee_ids[2] // 0073_jdoe

多维数组

虽然数组可以定义为单个维度并保存一组值，如前所述，但它们也可以声明为多维数组。这意味着数组的每个索引都保存另一个数组，直到定义的维度数量。这意味着在二维数组（如下所示）中，数组将是一个数组的数组，这些数组都将包含值。它们可用于存储表格数据或应通过 x 和 y 坐标访问的数据，例如游戏中的像素或图块。

这些数组对于存储更复杂的数据非常有用，但也需要更复杂的编程来适应，因为您必须完全理解数组的结构才能访问正确的数据。

shopSales[]	0	1	2	3
0	128.90	135.52	145.31	156.65
1	50.11	30.34	40.32	45.43
2	67.54	142.81	76.51	130.72
3	156.14	135.41	91.25	109.49

在上面的示例中，shopSales 可以指连锁店赚取的利润，其中顶部索引是季度，左侧索引是商店编号。值得注意的是，在许多示例中，您需要先访问顶部索引，因为它将包含商店本身的数组。但是，这取决于您初始化和定义数组的方式，例如

let shopSales [4][4] = [
    [128.90, 50.11, 67.54, 156.13],
    [135.52, 30.34, 142.81, 135.41],
    [145.31, 40.32, 76.51, 91.25],
    [156.65, 45.43, 130.72, 109.49]
];
let cheltenham = 0;
let gloucester = 1;
let bristol = 2;
let london = 3;

shopSales[0][cheltenham]; //128.90 - The sales made in the Cheltenham store in the first quarter.
shopSales[3][london]; // 109.49 - The sales made in the London tore in the fourth quarter.
shopSales[2][1] // 40.32 - Gloucester store, second quarter

栈

栈是列表的修改实现。数据结构在实现时有一组规则需要遵循，但这种结构如何工作的确切实现将取决于它的编程方式。这是一个抽象数据类型的示例，因为我们不关心底层方法，只关心允许我们与之交互的抽象函数。

栈是LIFO或后进先出结构的示例。这意味着最后一个添加到栈的元素将是第一个被访问的元素。栈有一组函数，无论它在哪里都应该实现

函数	描述
`push(element)`	将元素推入堆栈顶端。
`pop()`	从堆栈顶端移除元素，然后返回它。
`empty()`	检查堆栈是否为空。
`full()`	检查堆栈是否已达到最大容量。

某些实现可能对这些函数使用略微不同的名称，例如isFull和isEmpty()。

一些堆栈是定义为固定大小的，但这取决于具体的实现。堆栈的顶部和底部的概念是比较随意的，你只需要确保记住，项目是添加到相同端，并从相同端移除。下面展示了堆栈使用的一个示例。

stack = new Stack(4); // Define a stack with a maximum capacity of 4 elements.
stack.empty(); // -> True

stack.push(10);
//Stack: [0] 10

stack.pop(); // -> 10
//Stack: empty

stack.push(23);
stack.push(53);
stack.push(12);
stack.push(1);
//Stack: [0] 1
//       [1] 12
//       [2] 53
//       [3] 23

stack.full() // -> True

stack.pop() // -> 1
//Stack: [0] 12
//       [1] 53
//       [2] 23

队列

队列类似于堆栈，它是一个抽象数据存储，遵循一组规则。它是一种FIFO结构或先进先出，这意味着第一个添加的数据将在查询时（队列在现实生活中是如何工作的，通常）成为第一个返回的数据。

它定义了自己的函数集。

函数	描述
`enqueue(element)`	将元素推入队列的顶端。
`dequeue()`	从队列底部移除元素，然后返回它。
`empty()`	检查队列是否为空。
`full()`	检查队列是否已达到最大容量。

下面展示了如何使用它的示例，但它在现实世界的编程中有很多非常有用和实际的应用。例如，如果需要执行一组任务，可以使用队列来确保它们按照添加的顺序执行。

queue = new Queue(4); // Define a queue with a maximum of 4 elements.
queue.empty(); // -> True

queue.enqueue(23)
queue.enqueue(53);
queue.enqueue(12);
queue.enqueue(1);
// Queue: [0] 23
//        [1] 53
//        [2] 12
//        [3] 1

queue.full(); // -> True

queue.dequeue(); // -> 23
queue.dequeue(); // -> 53
// Queue: [0] 12
//        [1] 1

可遍历结构

树

树是一种数据结构，由树干和树叶组成。树有很多不同的类型，但你只需要了解基础知识和二叉搜索树的特征。

树由一组节点组成，每个节点都包含一个值。它们然后连接到另一个节点，该节点可能会分支到另一个节点，依此类推，或者会结束该链。旁边显示了树的示例。

二叉搜索树

二叉搜索树是树的一种特定实现，遵循一组规则。这种树将有一个“比较函数”或类似名称的函数，它控制数据将在树中的哪个位置插入。这可能是像“a > b”这样的简单内容，其中 a 是要插入的数据，b 是当前节点。任何只有 2 个分支的树都被认为是二叉树。

插入

当插入数据时，它使用比较函数沿着树遍历一条路径。在旁边显示的图像中，如果我们要添加数据 9，它将进入根节点8。由于该值更大，因此它将进入右侧并进入10节点。由于该值更小，因此它将进入左侧。由于那里没有节点，因此它将在该位置添加节点。

如果左侧有节点，该过程将继续进行，直到到达没有子节点的位置，然后将在那里插入。重复项将在图中的哪个位置放置取决于比较函数的编写方式。

遍历

树可以以四种不同的方式遍历，这决定了如何遍历节点，因此控制了节点返回的顺序。

先序遍历

先序遍历的正式步骤如下：

如果节点不为空，则继续。
输出当前节点的数据。
转到左侧，并从头开始。
转到右侧，并从头开始。

最后两步是通过递归调用此函数来实现的。

手动执行时，你只需在节点左侧画一条线，并在节点周围画一条线，如图右侧所示。这种方法适用于每种遍历，只是取决于你在哪里画线。

中序遍历

中序遍历的正式步骤如下：

如果节点不为空，则继续。
转到左侧，并从头开始。
输出当前节点的数据。
转到右侧，并从头开始。

第 2 步和第 4 步是通过递归调用此函数来实现的。

手动执行时，你只需从每个节点向下画一条线，并在节点周围画一条线，如图右侧所示。这种方法适用于每种遍历，只是取决于你在哪里画线。

后序遍历

后序遍历的正式步骤如下：

如果节点不为空，则继续。
转到左侧，并从头开始。
转到右侧，并从头开始。
输出当前节点的数据。

第 2 步和第 3 步是通过递归调用此函数来实现的。

手动执行时，你只需在节点右侧画一条线，并在节点周围画一条线，如图右侧所示。这种方法适用于每种遍历，只是取决于你在哪里画线。

广度优先遍历

广度优先遍历没有关于如何访问节点的特定步骤，但很容易猜到。它按顺序访问树的每一层，并从左到右输出节点的内容。

你不需要知道如何实现它，但了解它的工作原理是有意义的。

图

图类似于树，但复杂得多。它由节点和连接组成，就像树一样，但每个节点不只连接到下方，任何节点都可以连接到另一个节点。每个连接要么与方向相关联（例如 a 连接到 b），在这种情况下，图被称为有向图，要么没有方向（例如a和b有连接），在这种情况下，它被称为无向图。

图非常适合对大量复杂数据进行建模，因为它允许更自然地连接数据。有些图将在连接旁边显示数字，这些数字被称为权重，并影响使用 Dijkstra 等算法进行遍历时的工作方式。

您必须了解如何遍历图数据结构，这可以通过两种算法来实现。以下内容摘自 OCR 计算机书籍。

深度优先遍历

PUSH the first node onto the stack
Mark as visited
Repeat
    Visit the next unvisited node to the one on the top of the stack
    Mark as visited
    PUSH this node onto the stack
    If no node to visit POP node off the stack
Until the stack is empty

广度优先遍历

PUSH the first node into the queue
Mark as visited
Repeat
    Visit the unvisited nodes connected to the first node
    PUSH nodes onto queue
Until all nodes visited
Repeat
    POP next node from queue
    Repeat
        Visit unvisited nodes connected to current node
        PUSH nodes into queue
    Until all nodes visited
Until queue empty

哈希表

数据存储在通过将数据的标识符传递给哈希函数生成的内存位置中。哈希函数生成一个内存地址来存储项目的 data，它总是对特定输入标识符返回相同的答案。

一些简单的哈希函数会为不同的数据项提供相同的内存地址。在这种情况下，将说明重新计算重复地址的方法。这可能会转到下一个可用的内存地址，或者检查之后每第三个内存地址，直到找到一个可用的地址。