抽象数据结构
5.1.1 识别需要使用递归思维的情况。
递归思维是将一个复杂问题分解成更小、更简单的子问题，然后使用与原始问题相同的方法来解决子问题。以下是一些通常需要使用递归思维的情况：
- 具有递归结构的问题：具有自然递归结构的问题，例如树遍历，非常适合递归思维。这些问题可以很容易地分解成更小的子问题，这些子问题可以递归地解决。
- 可以简化为自身更小版本的问题：如果一个问题可以简化为自身更小版本，那么它就可以递归地解决。例如，一个涉及计算第 n 个斐波那契数的问题可以通过递归地计算第 (n-1) 个和第 (n-2) 个斐波那契数来解决。
- 分治问题：分治问题可以通过递归解决。例如，在数组中找到最大元素的问题可以通过将数组分成两半，然后递归地找到每半的最大元素来解决。
- 回溯问题：回溯问题，例如旅行商问题，可以通过递归地探索所有可能的解决方案并回溯来解决，当发现解决方案不正确时。
- 在这些情况下，递归算法很有用，因为它们允许将问题分解成更小的子问题，从而更容易理解和解决。递归解决方案可以以紧凑而优雅的方式实现，从而更容易理解和维护。
5.1.2 在特定问题中识别递归思维。
递归思维涉及将一个问题分解成更小的子问题，这些子问题可以使用与原始问题相同的方法来解决。以下是一个示例，帮助您了解如何在问题中识别递归思维。
示例：求一个数的阶乘的问题。
一个数的阶乘定义为小于或等于该数的所有正整数的乘积。例如，5 的阶乘是 5 * 4 * 3 * 2 * 1 = 120。
要递归地解决这个问题，我们可以使用以下步骤：
- 确定基本情况：基本情况是当数字为 1 时，阶乘为 1。
- 将问题分解成更小的子问题：要找到数字 n 的阶乘，我们可以找到 n-1 的阶乘，然后乘以 n。这将问题分解成可以递归解决的更小子问题。
- 进行递归调用：调用函数以找到 n-1 的阶乘，并将结果存储在一个变量中。
- 组合解决方案：将递归调用的结果乘以 n 以获得 n 的阶乘。
- 返回解决方案：将计算结果返回给函数的调用者。
这个问题可以通过将问题分解成更小的子问题并使用相同的方法来解决每个子问题来递归地解决。这是递归思维的本质。
子程序是执行特定任务的自包含代码单元。它们也被称为函数、过程或子例程。子程序可以从程序的其他部分调用，从而允许模块化和可重用代码。以下是一些子程序中常用的语句：
- 函数声明：函数声明指定函数的名称、它接受的参数以及它返回的值的类型。例如，在像 Python 这样的编程语言中，函数声明可能看起来像这样：def factorial(n)
- 参数传递：参数是传递给函数的值。它们由函数用来执行其计算。参数传递主要有两种方法：按值传递和按引用传递。
- 返回语句：return 语句用于从函数返回一个值给调用代码。return 语句也可以用来在满足某个条件时提前退出函数。例如，在 Python 中：return result
- 局部变量：局部变量是在函数内声明和使用的变量。它们只能在函数作用域内访问，并且对程序的其他部分不可见。
- 递归：子程序可以调用自身，这种技术称为递归。这允许将问题分解成更小的子问题并使用相同的方法来解决。
- 函数调用：函数调用是一个语句，它调用一个函数，传递任何必要的参数，并允许函数执行其代码。例如，在 Python 中：factorial(5)
- 作用域：变量的作用域是程序中可以访问它的区域。在函数内声明的变量具有局部作用域，而在函数外部声明的变量具有全局作用域。
这些是一些子程序中常用的语句，但确切的语法可能会因使用的编程语言而异。
递归二分查找是一种搜索算法，它使用分治法在一个排序数组中查找目标值。该算法的基本思想是不断将数组分成两半，并将中间元素与目标值进行比较。以下是对递归二分查找步骤的概述：
- 检查基本情况：如果数组的长度为 0，则目标值不存在于数组中，搜索应返回
False。 - 确定中间元素：将数组的长度除以 2 以找到中间元素的索引。
- 将中间元素与目标值进行比较：如果中间元素等于目标值，则搜索成功，函数应返回
True。 - 递归地搜索数组的左半部分或右半部分：如果目标值小于中间元素，则搜索数组的左半部分。如果目标值大于中间元素，则搜索数组的右半部分。
- 重复这些步骤，直到找到目标值或数组为空：继续将数组分成两半，并将中间元素与目标值进行比较，直到找到目标值或数组为空。
使用递归二分查找的优点是它是一种简单而有效的算法，可用于搜索大型数组。但是，它需要一个排序数组，并且由于递归调用，会使用大量的内存。
快速排序是一种排序算法，它使用分治法对元素数组进行排序。由于其平均时间复杂度为 O(n log n)，因此它是最常用的排序算法之一。
以下是对快速排序算法步骤的概述：
- 选择一个枢轴元素：枢轴元素用于将数组划分为两个较小的子数组。一种常见的方法是选择数组的第一个、最后一个或中间元素作为枢轴。
- 对数组进行分区：重新排列数组中的元素，以便所有小于枢轴的元素都在它左侧，所有大于枢轴的元素都在它右侧。
- 递归地排序子数组：对步骤 2 中创建的子数组重复分区步骤，直到子数组的长度为 0 或 1。
- 组合子数组：子数组组合成一个排序数组。
快速排序的最佳时间复杂度为 O(n log n)，平均时间复杂度为 O(n log n)，使其成为对大型数组进行排序的有效算法。但是，可以通过使用随机枢轴或选择中位数元素作为枢轴来避免其最坏情况时间复杂度为 O(n^2)。
5.1.3 跟踪递归算法以表达问题的解决方案。
跟踪递归算法涉及遵循算法的步骤，以查看它是如何解决问题的。步骤如下：
- 确定基本情况：跟踪递归算法的第一步是确定基本情况，即停止递归的条件。基本情况应该简单易解，并提供问题的非递归解决方案。
- 将问题分解为更小的子问题：下一步是将问题分解为可以递归解决的更小的子问题。这是通过对函数进行递归调用，并使用较小的输入来完成的。
- 跟踪递归调用：对于每个递归调用，跟踪函数的步骤，以查看它如何解决子问题。重复此步骤，直到达到基本情况。
- 组合解决方案：一旦达到基本情况，就可以组合更小子问题的解决方案，以形成原始问题的解决方案。
- 返回解决方案：最后，将解决方案返回给函数的调用者。
为了正确跟踪算法，了解递归算法的结构以及更小子问题与原始问题之间的关系非常重要。跟踪应该提供算法如何解决问题的逐步描述，并帮助您理解算法的行为。
5.1.4 描述二维数组的特征。
二维数组是数组的数组，其中每个元素都是一个数组。它是一组排列成行和列的元素，可以用来表示数据表。二维数组的主要特征如下
- 大小：二维数组的大小由其行数和列数决定。它是一种固定大小的数据结构。
- 索引：二维数组中的元素使用两个索引访问，一个用于行，一个用于列。索引从 0 开始。
- 表示：二维数组可以表示为一个带行列的表，其中每个元素由一个单元格表示。
- 多维：二维数组是一种多维数组，这意味着它可以用来在多个维度上存储数据。
- 存储：二维数组中的元素存储在内存的连续块中，这使得访问元素的速度比访问一维数组中的元素更快。
这些是二维数组的一些主要特征。二维数组被广泛用于计算机编程，以表格形式表示和操作数据。
5.1.5 使用二维数组构造算法。
二维数组（也称为矩阵）在各种算法中很有用，可以用来表示表格、图形和图像。一些使用二维数组的常见算法是
- 矩阵乘法：一个算法来乘以两个矩阵。结果存储在第三个矩阵中。
- 在二维数组中搜索：一个算法在二维数组中搜索特定值。
- 图像处理：一个算法对图像执行操作，例如调整大小、过滤和边缘检测。
- 图形表示：一个算法使用二维数组来表示图形，其中每个单元格表示一个节点及其边。
为了实现这些算法，您可以使用以下技术与二维数组一起使用
- 遍历行和列：为了访问二维数组中的所有元素，您可以使用嵌套循环来遍历每一行和每一列。
- 访问元素：您可以使用行和列索引访问二维数组中的元素，例如
array[row][column]。 - 修改元素：您可以通过分配一个新值来修改二维数组中元素的值，例如
array[row][column] = newValue。
通过使用这些技术，您可以构建执行矩阵操作、在二维数组中搜索值以及处理图像和图形的算法。
5.1.6 描述堆栈的特征和应用。
堆栈是一种线性数据结构，遵循后进先出 (LIFO) 原则，其中添加到堆栈中的最后一个元素是第一个被移除的元素。堆栈的主要特征和应用如下
特征
- LIFO：添加到堆栈中的最后一个元素是第一个被移除的元素。
- 动态大小：堆栈的大小可以在运行时更改。
- 两个主要操作：在堆栈上执行的两个主要操作是 push（将元素添加到堆栈的顶部）和 pop（从堆栈的顶部移除元素）。
- 访问受限：堆栈中唯一可以访问的元素是顶部的元素。
应用
- 撤消/重做操作：堆栈可以用来在文本编辑器和图像编辑器中实现撤消/重做操作。
- 递归：堆栈用于在递归期间跟踪函数调用。
- 符号平衡：堆栈可以用来检查符号是否平衡，例如在包含括号、方括号和花括号的表达式中。
- 回溯：堆栈可以用来实现回溯算法，例如解决迷宫或在图形中查找路径。
- 网页浏览历史：堆栈可以用来实现网页浏览历史，其中访问的每个网页都添加到堆栈的顶部，后退按钮会移除顶部的元素。
这些是堆栈的一些主要特征和应用。通过使用 LIFO 原则以及 push 和 pop 操作，堆栈可以用来实现各种需要按特定顺序跟踪元素的算法和应用。
5.1.7 使用堆栈的访问方法构造算法。
以下是可以使用堆栈的访问方法构造的一些常见算法
- 深度优先搜索 (DFS)：一种图形遍历算法，它以深度优先顺序访问图形中的所有顶点，从给定的源顶点开始。该算法使用堆栈来跟踪下一个要访问的顶点。
- 中缀表达式转换为后缀表达式：一个算法将中缀表达式转换为后缀表达式。该算法使用堆栈来跟踪运算符和操作数。
- 计算后缀表达式：一个算法来计算后缀表达式。该算法使用堆栈来跟踪操作数并执行算术运算。
- 回溯：一种算法，它尝试不同的解决方案，并在解决方案不起作用时返回到之前的状态。该算法使用堆栈来跟踪要重新访问的状态。
为了实现这些算法，您可以使用以下堆栈访问方法
- push：将元素添加到堆栈的顶部。
- pop：从堆栈的顶部移除元素。
- peek：获取顶部元素而不移除它。
- isEmpty：检查堆栈是否为空。
通过使用这些访问方法，您可以构建执行操作的算法，例如以深度优先顺序访问顶点、将中缀表达式转换为后缀表达式、计算后缀表达式以及回溯。
5.1.8 描述队列的特征和应用。
队列是一种线性数据结构，遵循先进先出 (FIFO) 原则，其中添加到队列中的第一个元素是第一个被移除的元素。队列的主要特征和应用如下
特征
- FIFO：添加到队列中的第一个元素是第一个被移除的元素。
- 动态大小：队列的大小可以在运行时更改。
- 两个主要操作：在队列上执行的两个主要操作是入队（将元素添加到队列的末尾）和出队（从队列的开头移除元素）。
- 访问受限：队列中唯一可以访问的元素是头部的元素和尾部的元素。
应用
- BFS（广度优先搜索）：一种图形遍历算法，它以广度优先顺序访问图形中的所有顶点，从给定的源顶点开始。该算法使用队列来跟踪下一个要访问的顶点。
- CPU 调度：队列用于跟踪等待由 CPU 执行的任务。CPU 根据任务添加到队列的顺序来调度任务。
- 事件处理：队列用于跟踪在操作系统或计算机程序中发生的事件。事件按添加到队列的顺序处理。
- 打印机队列：队列用于跟踪等待由打印机执行的打印作业。打印作业按添加到队列的顺序执行。
这些是队列的一些主要特征和应用。通过使用 FIFO 原则以及入队和出队操作，队列可以用来实现各种需要按特定顺序跟踪元素的算法和应用。
5.1.9 使用队列的访问方法构造算法。
以下是可以使用队列的访问方法构造的一些常见算法
- 广度优先搜索 (BFS)：一种图形遍历算法，它以广度优先顺序访问图形中的所有顶点，从给定的源顶点开始。该算法使用队列来跟踪下一个要访问的顶点。
- 树的层序遍历：一种树遍历算法，它以层序访问树中的所有节点，从根节点开始。该算法使用队列来跟踪每层要访问的节点。
- 图中的最短路径：一种在图中找到两个顶点之间最短路径的算法。该算法使用队列来跟踪接下来要访问的顶点。
为了实现这些算法，您可以使用以下队列访问方法
- 入队：将元素添加到队列的末尾。
- 出队：从队列中删除第一个元素。
- 窥视：获取第一个元素，但不删除它。
- 为空：检查队列是否为空。
通过使用这些访问方法，您可以构建执行以下操作的算法，例如：以广度优先的顺序访问顶点、跟踪要访问的节点以及在图中找到最短路径。
5.1.10 解释数组作为静态栈和队列的使用。
数组可用于实现静态栈和队列。
栈是一种后进先出 (LIFO) 数据结构，其中元素从栈顶添加和删除。数组可用于通过使用数组的末端来表示栈顶来实现静态栈。要将元素压入栈，我们递增末端索引并将元素存储在该位置。要弹出元素，我们检索末端索引处的元素并递减末端索引。
队列是一种先进先出 (FIFO) 数据结构，其中元素从末尾添加并从开头删除。数组可用于通过使用两个索引来实现静态队列，一个索引表示队列的开头，另一个索引表示队列的末尾。要将元素入队，我们递增末端索引并将元素存储在该位置。要将元素出队，我们检索开头索引处的元素并递增开头索引。
需要注意的是，静态数组的大小是固定的，这意味着一旦它已满，就不能再向其中添加任何元素。当使用数组作为静态栈或队列时，这可能是一个限制。使用链表实现的栈和队列的动态版本可以通过根据需要分配新内存来克服此限制。
链表
[edit | edit source]5.1.11 描述动态数据结构的特征和特性。
动态数据结构是一种可以在运行时改变其大小的数据结构。动态数据结构的一些特征和特性包括
- 调整大小：动态数据结构的大小可以根据需要进行更改，使其比大小固定的静态数据结构更灵活。
- 动态内存分配：动态数据结构动态地分配内存，这意味着内存是在需要时分配的，而不是在程序开始时一次性分配所有内存。
- 高效的插入和删除：动态数据结构通常允许高效地插入和删除元素，使其在元素数量可能频繁变化的应用程序中非常有用。
- 复杂度：与静态数据结构相比，动态数据结构通常在搜索和访问等操作方面具有更高的时间复杂度。
- 示例：动态数据结构的一些示例包括链表、栈、队列和树。
5.1.12 描述链表在逻辑上的运行方式。
链表是一种动态数据结构，它由一系列节点组成，每个节点包含一个数据元素和指向列表中下一个节点的引用（或“链接”）。
在逻辑上，链表的运行方式如下
- 链表中的第一个节点被称为头节点。它包含列表的第一个元素和指向下一个节点的引用。
- 下一个节点包含它自己的数据元素和指向列表中下一个节点的引用。这对于列表中的每个节点都继续下去，直到最后一个节点，该节点没有指向另一个节点的引用（它的“下一个”链接为空）。
- 要访问列表中的特定节点，必须从头节点开始，然后遵循从一个节点到下一个节点的链接，直到到达所需节点。
- 要将新节点插入列表，将创建一个新节点，并将它的“下一个”链接设置为引用它应该在列表中跟随的节点。然后更新在新节点之前的节点的“下一个”链接，以引用新节点。
- 要从列表中删除节点，将更新在它之前的节点的“下一个”链接以引用它之后的节点，从而有效地将节点从列表中删除。
通过以这种方式将节点链接在一起，链表允许高效地插入和删除元素，以及快速遍历列表中的元素。
5.1.13 勾勒出链表（单向、双向和循环）。
单链表：单链表由一系列节点组成，每个节点包含一个数据元素和指向列表中下一个节点的引用。它可以被可视化为一系列节点，其中每个节点通过指向下一个节点的单箭头连接到下一个节点。
双向链表：双向链表类似于单链表，但除了指向下一个节点的引用外，每个节点还包含指向前一个节点的引用。它可以被可视化为一系列节点，其中每个节点通过指向下一个节点的箭头连接到下一个节点，并且还通过指向前一个节点的箭头连接到前一个节点。
循环链表：循环链表是一种链表，其中列表中的最后一个节点指向第一个节点，形成一个节点的循环链。它可以被可视化为一系列节点，其中最后一个节点通过箭头连接到第一个节点，形成一个节点的循环链。
树
[edit | edit source]5.1.14 描述树在逻辑上的运行方式（包括二叉树和非二叉树）。
树是用于组织和存储数据的层次数据结构。树有两种类型：二叉树和非二叉树。
二叉树：二叉树是一种树形数据结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。
在逻辑上，二叉树的运行方式如下
- 树中顶部的节点称为根节点。
- 树中的每个节点都有一个值，父节点的值用于确定子节点的位置。如果节点的值小于父节点的值，则将其放置在左侧作为左子节点。如果节点的值大于父节点的值，则将其放置在右侧作为右子节点。
- 此过程将继续进行树中的每个节点，每个节点的左子节点和右子节点将成为其各自子树的父节点。
- 要搜索树中的特定值，从根节点开始，并将节点的值与目标值进行比较。如果节点的值小于目标值，则搜索将继续在右子树中进行。如果节点的值大于目标值，则搜索将继续在左子树中进行。此过程将继续进行，直到找到目标值或确定目标值不存在于树中。
非二叉树：非二叉树是树，其中节点可以有多于两个子节点。非二叉树的逻辑操作类似于二叉树，只是每个节点可以有多于两个子节点，并且节点拥有的子节点数量决定了如何执行特定值的搜索。确定节点在树中的位置的过程也不同，因为它可能涉及额外的比较和条件。
在逻辑上，非二叉树的运行方式如下
- 树中顶部的节点称为根节点。
- 树中的每个节点都有一个值，父节点的值用于确定子节点的位置。确定节点位置的过程可能涉及多个比较和条件，具体取决于树的具体实现。
- 每个节点的子节点形成子树，确定节点位置的过程将继续进行树中的每个节点。
- 要搜索树中的特定值，从根节点开始，并评估子节点的值。根据树的实现，搜索可能涉及多个比较和条件来确定要遍历哪个子节点。
- 此过程将继续进行，直到找到目标值或确定目标值不存在于树中。
在非二叉树中，节点拥有的子节点数量可能会影响搜索特定值的时间复杂度，因为它可能需要遍历更多分支。但是，非二叉树在某些二叉树可能不足以处理的应用程序中更灵活，更有用。
5.1.15 定义以下术语：父节点、左子节点、右子节点、子树、根节点和叶节点。
- 父节点：父节点是树形数据结构中有一个或多个子节点的节点。
- 左子节点：左子节点是树形数据结构中位于父节点左侧的子节点。
- 右子节点：右子节点是树形数据结构中位于父节点右侧的子节点。
- 子树：子树是树形数据结构的一部分，它包含一个节点及其所有后代。
- 根节点：根节点是树形数据结构中顶部的节点。它是树中所有操作和遍历的起点。
- 叶节点：叶节点是树形数据结构中没有子节点的节点。它是树中分支的末端，没有进一步的后代。
5.1.16 说明中序遍历、后序遍历和前序遍历树的遍历结果。
在树形数据结构中，树遍历的结果是指访问节点的顺序。有三种常见的树遍历方法：中序遍历、后序遍历和前序遍历。
- 中序遍历：在中序遍历中，节点按以下顺序访问：左子树、根节点和右子树。如果树是二叉搜索树，则中序遍历的结果是一个已排序的节点列表。
- 后序遍历：在后序遍历中，节点按以下顺序访问：左子树、右子树和根节点。后序遍历的结果是一个节点列表，表示它们在逆波兰表达式求值中处理的顺序。
- 前序遍历：在前序遍历中，节点按以下顺序访问：根节点、左子树和右子树。前序遍历的结果是一个节点列表，表示树的结构。
这些遍历方法在各种操作中很有用，例如搜索、打印和修改树形数据结构。
5.1.17 勾勒出二叉树。
二叉树可以被直观地表示为一系列连接的节点，其中每个节点最多有两个子节点。
要勾勒出二叉树，请执行以下步骤
- 为根节点绘制一个框，并用其值标记它。
- 从根节点绘制一条线到其左子节点的框，并用其值标记它。
- 从根节点绘制一条线到其右子节点的框，并用其值标记它。
- 对每个子节点重复此过程，绘制连接到其子节点的框的线，并用它们的值标记它们。
- 继续此过程，直到所有节点都被表示和标记。
以下是一个简单的二叉树草图示例。
5
/ \
3 8
/ \
2 4
请注意，在二叉树中，每个节点最多可以有两个子节点。如果一个节点没有子节点，则称为叶节点。二叉树的高度定义为从根节点到叶节点的最长路径上的边数。此示例中二叉树的高度为 2。
5.1.18 定义动态数据结构的术语。
动态数据结构是一种数据结构，其大小可以在程序执行期间发生变化。与静态数据结构不同，动态数据结构的大小可以根据需要增加或减少。这是通过在运行时动态分配内存来实现的，而不是预先分配内存。
动态数据结构在许多应用程序中使用，因为它们可以适应不断变化的要求并处理不可预测的数据量。动态数据结构的一些常见示例包括链表、堆栈和队列，以及更复杂的数据结构，如树和图。
动态数据结构通常使用指针和动态内存分配来实现，这允许高效灵活地操作数据。但是，这也需要仔细管理内存，因为动态分配的内存必须在不再需要时明确释放。
5.1.19 比较静态数据结构和动态数据结构的使用。
静态数据结构和动态数据结构是两种类型的数据结构，它们具有不同的特征和用例。
静态数据结构是在程序编译时确定大小并且在运行时无法更改的固定大小的数据结构。静态数据结构的示例包括数组、固定大小的堆栈和队列以及矩阵。静态数据结构的优点是它们的大小在运行时不会改变，因此每个元素的内存分配是可预测且简单的。这使得它们在需要固定数据量的任务（例如数学运算）中非常有效。
另一方面，动态数据结构是可以改变大小的数据结构。动态数据结构的示例包括链表、使用动态数组实现的堆栈和队列以及树。动态数据结构的优点是它们能够适应不断变化的要求，因此可以处理不可预测的数据量。这使得它们非常适合需要能够根据需要扩展或缩小的数据结构的任务，例如数据存储和检索。
总之，选择静态数据结构还是动态数据结构取决于手头任务的要求。对于需要固定数据量的任务，静态数据结构更有效，而对于需要动态数据结构的任务，动态数据结构是更好的选择。
5.1.20 为给定情况建议合适的结构。
要为给定情况建议合适的数据结构，请考虑以下因素
- 数据的规模和性质：是少量数据还是大量数据？是数字、类别还是两者兼而有之？
- 访问模式：您需要多频繁地访问数据？您需要搜索特定元素、对数据进行排序还是经常插入/删除元素？
- 时间和空间复杂度：对数据操作所需的理想时间和空间复杂度是多少？
根据上述因素，您可以从以下常用的数据结构中选择
- 数组：当您需要存储少量项目并通过索引随机访问它们时。
- 链表：当您需要存储大量项目并按顺序访问它们时。
- 堆栈：当您需要先访问最后一个元素，并且只需要访问最后一个元素时，就像“撤销”功能一样。
- 队列：当您需要按照先进先出顺序访问元素时，就像排队一样。
- 哈希表：当您需要根据键快速访问元素，并且不需要保留元素的顺序时。
- 树：当您需要经常有效地搜索、插入和删除元素，并维护元素之间的顺序时。
- 图：当您需要表示元素之间的关系或查找两个节点之间的最短路径时。
注意：数据结构的选择将取决于问题的具体要求以及时间和空间复杂度之间的权衡。