算法中使用的数据结构解释*

算法中使用的数据结构解释

在算法的执行过程中，需要有能够容纳临时数据的内存数据结构。数据结构的有效实施需要选择适当的数据结构。迭代或递归算法需要专门为其逻辑设计的数据结构。

也有人表述为容器，存放数据的容器。

在递归算法的情况下，嵌套的数据结构可以促进其实现并提高其性能。本文将结合数据结构来讨论算法。本文的重点是Python数据结构，因为我们将在整个文章中使用Python。然而，本文介绍的概念也可以应用于其他语言，如Java和C++。

在这篇文章中，你应该了解Python如何处理复杂的数据结构，以及哪一种结构应该用于特定类型的数据。

在这篇文章中，将讨论以下几点。

• 使用Python来探索数据结构

• 对抽象数据类型的探索

• 队列和堆栈

• 树

Python数据结构的探索

在任何编程语言中，数据结构都是用来存储和处理复杂数据的。Python中的数据结构是用于有效管理、组织和搜索数据的容器。它们被用来存储和处理被称为集合的数据元素组。以下五个数据结构可以用来在 Python 中存储集合。

一个可以变异的有序元素序列

以不可变的方式排序的元素序列

集合的元素是无序的

字典将键值对定义为无序的包

数据框是一个用于存储二维数据的二维结构

在下面的小节中，我们将更详细地探讨它们。

列表

列表是 Python 的主要数据结构，用于存储可变元素。一个列表不一定要包含相同类型的数据元素。

有必要用 [ ] 包围列表中的元素，并用逗号将它们分开。例如，这段代码一起创建了四个不同类型的数据元素。

[图片上传失败...(image-e3bc07-1667467474169)]

在 Python 中，列表对于创建一维的可写数据结构是很有用的，在算法开发的不同阶段都需要。

列表

列表可以使用数据结构中的实用函数进行管理，这使得它们非常有用。****为了利用它们，让我们考虑以下情况。

有可能通过使用列表的索引来获得某个特定位置的元素，因为列表中元素的位置是确定的。这个概念的演示可以在下面的代码中找到。

这段代码生成了一个四元素的列表，如下面的屏幕截图所示。

[图片上传失败...(image-fe3f43-1667467474169)]

因为索引从0开始，所以用索引1检索绿色，即bin_color[1]。

一个列表可以通过指定一个索引范围来切分，以便检索其元素的一个子集。你可以用下面的代码创建一个列表的片断。

Python 的 list 数据结构是****最流行的单维数据结构之一****。

在对列表进行切片的过程中，范围表示如下：

[图片上传失败...(image-d3f4af-1667467474175)]

第一个数字（包括）和第二个数字（排除）

类似地bin_colors[0:2] 包含 bin_color[0] 和 bin_color[1]，但不包含 bin_color[2]

由于一些 Python 用户抱怨列表不直观，在使用它们时应该记住这一点。****这里有一段代码，你可能会觉得很有用。

如果没有指定起始或结束索引，列表将从头开始，如果都没有指定索引，列表将在结束时结束。从前面的代码可以看出，这个概念实际上已经被证明了。

[图片上传失败...(image-be5c99-1667467474175)]

在 Python 中也可以有负的索引，从列表的末端开始计算。下面是一个说明这一点的代码例子。

当我们想引用最后一个元素而不是第一个元素时，负指数特别有用。

[图片上传失败...(image-efa171-1667467474174)]

列表中有两种类型的嵌套：简单和复杂。列表的嵌套是通过这个功能实现的。在迭代和递归算法的情况下，这提供了重要的能力。

考虑下面的代码例子，它显示了一个列表中的一个列表 (嵌套)。

[图片上传失败...(image-ec1e53-1667467474169)]

在 Python 中，一个 for 循环可以用来遍历一个列表的每个元素。下面可以看到一个例子。****通过迭代前面的代码，列表中的每个元素都被打印出来。

[图片上传失败...(image-d8efad-1667467474174)]

Lambda中的函数

Lambda函数可以以多种方式应用于列表。在算法的背景下，它们特别重要，因为它们提供了快速创建函数的能力。它们有时在文献中被称为匿名函数。下面的例子展示了如何使用它们。

过滤数据的第一步是定义一个谓词，这是一个接受单个参数并返回一个布尔值的函数。在下面的代码中可以找到它的使用示范。

[图片上传失败...(image-b448b9-1667467474174)]

使用lambda函数来过滤一个列表，我们在这段代码中指定过滤标准。基于定义的标准，过滤函数从一个序列中过滤元素。在 Python 中，它通常与 lambda 结合使用过滤函数。此外，图元和集合也可以用它来过滤。x > 100是前面代码中定义的标准。****列表中的所有元素将被遍历，任何未能通过这个过滤器的元素将被删除。

Lambda函数可用于使用map()函数来转换数据，一个例子。

[图片上传失败...(image-ea0dfd-1667467474174)]

用lambda函数来使用map函数是相当强大的****。****当与map函数一起使用时，可以使用lambda函数为序列的每个元素指定一个变换器。前面的代码使用乘以2作为转化器。列表中的每个元素都用map函数乘以2。

Reduce()可以用来在一个列表的每个元素上递归运行一个函数，以便汇总数据。

[图片上传失败...(image-f1a8e4-1667467474174)]

需要注意的是，reduce函数需要一个数据聚合函数。这段代码包括一个名为functools的数据聚合函数。它指定了一个列表中的项目将如何被聚合。作为聚合的结果，前两个元素将被替换成结果。直到我们到达终点，我们重复减少的过程，直到达到一个聚合的数字。doSum函数表示每次迭代中x1和x2的聚合标准。

270 是前面代码块的结果。

使用range() 范围函数

使用range函数，可以很容易地生成大的数字列表。列表中的数字序列可以用这个函数自动填充。

使用range函数很容易。要使用它，我们只需指定我们想要在列表中加入多少个元素。它从零开始，默认情况下增加一个。

[图片上传失败...(image-856984-1667467474174)]

此外，我们还可以指定步长和结束数。

[图片上传失败...(image-2d7958-1667467474174)]

从3到29开始的奇数将由前面的范围函数返回。

列表很耗时

使用大O符号，一个列表的时间复杂度可以总结为以下几点。

[图片上传失败...(image-46ed34-1667467474174)]

请注意，无论列表的大小，添加一个元素所需的时间都是一样的。列表的大小会影响表中的其他操作。性能影响随着列表的增长而增加。

Tuple 元组

集合也可以用元组来存储，图元是一种数据结构。元组数据结构与列表不同，它是不可变的（只读）。元组的元素用（）包围。

一个元组可以包含不同类型的元素，就像一个列表一样。它们的元素也支持复杂的数据类型。因此，通过使用元组中的元组，可以创建嵌套的数据结构。迭代和递归算法大大得益于创建嵌套数据结构的能力。

你可以使用下面的代码来创建元组。

[图片上传失败...(image-ba830f-1667467474174)]

由于它们的性能优势，只要有可能，就应该首选不可变的数据结构（比如图元）。不可变数据结构的性能明显快于可变数据结构，特别是在处理大数据时。例如，我们必须为改变列表中的数据元素的能力付出代价，所以我们应该仔细考虑是否真的有必要，以便将代码实现为只读元组。

这段代码将图元（100,200,300）称为第三个元素，a[2]。这个元组的第二个元素是200，被称为a[2][1]。

元组的时间复杂性

(使用Big O符号) 下面是一些元组函数的时间复杂性的例子。

[图片上传失败...(image-cf2902-1667467474174)]

值得注意的是，Append在已经存在的元组中增加了额外的元素。O(1)是其复杂性。

词典

特别是在分布式算法中，键值对是很重要的。Python 中的 dictionary 包含这些键值对的集合。在创建 dictionary 时，选择最适合在整个数据处理过程中识别数据的键是很重要的。任何类型的元素都可以作为值，例如数字或字符串。在 Python 中，一个 list 总是被用作值，其他复杂的数据类型也是如此。作为一种值类型，字典可以用来创建嵌套字典。

为变量分配颜色的一个简单方法是将键值对用{ }括起来。作为说明，这里有一段代码，用三个键值对创建一个简单的字典。

如下面的截图所示，前面的代码创建了三个键值对。

[图片上传失败...(image-e1ee06-1667467474174)]

下面的代码检索和更新与一个键相关的值。

[图片上传失败...(image-f99ed4-1667467474169)]

一个键可以被用作索引，也可以用get函数来检索与之相关的一个值。

[图片上传失败...(image-6e2229-1667467474174)]

使用下面的代码，你可以更新与一个键相关的值。

[图片上传失败...(image-b6b17d-1667467474174)]

我们可以通过在前面的代码中更新字典中的键来更新一个值。

dictionary 的时间复杂性****的估计

一个用大O符号表示的字典有如下的时间复杂性。

[图片上传失败...(image-3c529c-1667467474174)]

根据字典的复杂性分析，必须注意到键值的检索或设置与字典的大小无关。换句话说，将一个键值对添加到三个维度的字典中与将一个键值对添加到一百万维度的字典中所花费的时间是一样的。

集合 set()

集合是具有不同类型的元素的集合。在 [] 内的是元素。请看下面的代码块作为一个例子。

[图片上传失败...(image-fad2a-1667467474174)]

集合的特点是只为每个元素存储不同的值。下面的图示说明了如果你试图添加另一个多余的元素会发生什么。

[图片上传失败...(image-dac2b7-1667467474169)]

让我们定义两个集合来说明可以对它们进行哪些操作。

黄色的东西属于一个叫做黄色的集合

[图片上传失败...(image-3e3ccd-1667467474174)]

**还有一个名为红色的集合，它包含红色的东西****这两个集合有一些共同的东西。下面的维恩图说明了这两个集合之间的关系。******[图片上传失败...(image-b73e45-1667467474168)]**** 这两个集合可以用Python实现，如下所示。[图片上传失败...(image-4f2178-1667467474174)]

这里有一个演示集合操作的Python代码。****在Python中，集合可以被连接和相交，如前面的代码片断所示。正如我们所知，联合将两个集合的所有元素结合在一起，而相交则产生两个集合共有的一个元素。应该注意以下几点。****要得到前面定义的两个集合的并集，请使用****黄色|红色****。****为了找到黄色和红色之间的重叠部分，我们使用****yellow&red****集合时间复杂度分析****下面是对集合的时间复杂性的分析。[图片上传失败...(image-d7c146-1667467474174)]

当对集合进行复杂度分析时，很明显，无论集合的大小，向其添加元素所花费的时间是不一样的。****DataFrame****Python的pandas包提供了用于存储表格数据的DataFrames。传统的结构化数据是使用这种数据结构处理的，它是算法最重要的数据结构之一。下面是一个需要考虑的表格。****现在可以用一个DataFrame来表示。****[图片上传失败...(image-138e23-1667467474169)] 通过使用下面的代码，我们可以创建一个简单的DataFrame。[图片上传失败...(image-bb7dab-1667467474174)]

**在前面的代码中的df.column中指定了一个列名列表。****在其他语言和框架中也可以使用DataFrame来实现表格数据结构。Apache Spark框架和R是两个例子。****数据框架术****语****在这篇文章中，我们将研究在DataFrame背景下使用的一些术语。****DataFrame的列或行在pandas文档中被称为轴。****作为一个组，多个轴被称为轴。****数据框架允许将标签应用到列和行上。****创建DataFrame子集****可以通过两种不同的方式来创建DataFrame的子集（假设子集的名称为myDF）。*****选择列******行的选择*****让我们仔细看一下它们各自的情况。****列的选择：******[图片上传失败...(image-fae2e6-1667467474168)]**** 选择适当的特征集是机器学习算法中最重要的任务之一。根据算法的不同，在某一阶段可能不需要所有的特征。下一节解释了如何通过列选择来选择Python特征。****可以通过列的名称来检索，如下面的例子。[图片上传失败...(image-53bbc-1667467474174)]

DataFrames 确定性地定位列。为了通过它的位置检索一个列，请遵循以下步骤。****需要注意的是，我们在这段代码中只检索了DataFrame的前三行。****选择行[图片上传失败...(image-a5be1-1667467474174)]

DataFrame的行代表我们问题空间中的数据点。创建一个问题空间的子集需要选择行。有两种方法来创建这个子集。

1. 通过指定它们的位置来定位
2. 通过指定一个来进行过滤
3. 通过确定行的位置，可以检索出一个行的子集。

所有的列和前两行将由前面的代码返回。****[图片上传失败...(image-37fd9a-1667467474169)] 创建子集的选择标准可以通过向过滤器添加列来定义。使用这种方法，你可以选择一个数据元素的子集，如下所示。[图片上传失败...(image-3e0c4c-1667467474173)]

在这段代码中，只有那些满足过滤器条件的行被创建。矩阵矩阵中有列和行，它是一个二维数据结构。在一个矩阵中，每个元素都由它的列和行来标识。****Numpy数组可以用来在Python中创建矩阵值，如下所示。[图片上传失败...(image-b06d11-1667467474173)]

前面的代码将创建三行和三列。矩阵操作在矩阵数据操作中，有许多操作可供选择。让我们试试对上面的矩阵进行转置。使用transpose()函数，列将被转换成行，行将被转换成列。

[图片上传失败...(image-c9f086-1667467474173)]

多媒体数据处理在很大程度上依赖于矩阵操作。****在学习了数据结构之后，我们的下一节将讨论Python中的抽象数据类型。抽象数据类型：一个探索****人们普遍认为，抽象是一个概念，它确定了复杂系统的共同核心功能。抽象数据类型（ADTs）是通过将这一概念应用于通用数据结构而创建的。****使用ADT的结果是更简单、更干净的算法，因为它们隐藏了实现层面的细节，并提供了一个与实现无关的数据结构。各种编程语言都可以用来实现ADTs，包括C++、Java和Scala。在本节中，我们将使用Python实现ADTs。我们将从向量开始。矢量矢量是一种以单维存储数据的结构。Python 最流行的数据结构是列表。Python 提供了两种创建向量的方法。[图片上传失败...(image-a5cb36-1667467474173)]

通过使用一个 Python 列表，你可以用以下方式创建一个向量。****在这个由这段代码创建的列表中会有四个元素。****也可以使用 NumPy 数组来创建向量，如下所示。[图片上传失败...(image-336550-1667467474173)]

在这段代码中，myVector是用np.array创建的。****在 Python 中，为了分隔整数的各个部分，使用了下划线。通过这样做，它们变得更易读，更不容易出错。在处理这个问题时，大数字特别有用。相应地，a=1可以用来表示10亿堆栈一维列表可以存储在堆栈中，它是一种线性数据结构。可以使用后进先出或FILO系统来存储项目。堆栈是由添加和删除元素的过程来定义的。在一端只有一个添加，在另一端只有一个删除。****堆栈可以按以下方式进行操作。

[图片上传失败...(image-ef117c-1667467474173)]

*如果 isEmpty 返回 true，那么栈就是空的。******一个元素的添加是通过推送******填充最近添加的元素并将其删除******从堆栈中推送和弹出数据可以用下面的图来说明。*****在上图的顶部部分，推操作被用来向堆栈添加项目。在步骤1.1、1.2和1.3中，推操作被使用了三次，向堆栈中添加了三个元素。在上图的底部，从堆栈中检索存储的值。在步骤2.2和2.3中使用pop操作从堆栈中取出两个后进先出格式的元素。****堆栈类将在Python中由一个叫做Stack的类来定义。这个类的代码将看起来像这样。[图片上传失败...(image-9d62af-1667467474173)]

使用下面的代码，四个元素可以被推到栈上。

[图片上传失败...(image-4075ed-1667467474173)]

使用前面的代码，四个数据元素被创建在一个堆栈中。****堆栈有很高的时间复杂性****为了理解堆栈的时间复杂度（使用大O符号），我们来看看。

[图片上传失败...(image-6fc4d0-1667467474173)]

堆栈的大小对上面列出的四种操作的性能没有任何影响。****一个实践中的例子****堆栈在许多应用中被用作数据结构。在网络浏览器中，可以使用后进先出的数据访问模式来访问历史记录，而历史记录可以存储在堆栈中。在使用文字处理程序时，用户可能想执行撤销操作。****队列****队列是存储n个元素的单维结构。一个FIFO格式用于添加和删除元素。队列的后端和前端分别被称为后端和前端。去排队是将元素从前端移除的过程。排队是在末端添加元素的过程。****一个排队操作显示在图的上部。结果队列显示在1.4中，是步骤1.1、1.2和1.3的结果。红色在后面，黄色在前面。****下图的底部显示了一个去排队操作。从队列的前面，步骤2.2、2.3和2.4逐一移除元素。

[图片上传失败...(image-bb146f-1667467474173)]

下面的代码可以用来实现上图中的队列。[图片上传失败...(image-a13030-1667467474173)]

下面是一张截图，显示了前述图中的元素是如何排队和脱队的。

[图片上传失败...(image-c547c4-1667467474173)]

在前面的代码中，首先将四个项目排入队列。队列和堆栈是基于相同的基本思想的用一个类比来分析堆栈和队列将有助于我们理解它们背后的基本思想。让我们想象一下，我们有一张桌子，里面放着我们的邮件，比如说，来自加拿大邮政的邮件。把邮件堆放好后，我们逐一打开，看一看。可以使用以下两种方法。****字母被堆叠起来，每个新的字母都被放在堆叠的顶部。字母是从上到下读的。这里可以找到一个堆叠的例子。最近到达的信件将被首先处理。在列表顶部拿起一个字母的过程被称为弹出操作。每当一个字母到达时，将其推到顶部，这被称为推操作。如果我们得到一个相当大的堆栈，并且许多字母连续到达，如果我们最终得到一个大的堆栈，我们可能永远不会到达堆栈底部的重要字母。****当我们查看一个或多个字母时，我们会注意先处理最老的那个：每次我们想检查一个或多个字母时，我们都会先处理最老的那个。队列就是我们所说的。将一个字母添加到堆中的过程被称为enqueueing。当一个字母从堆中被移除时，它被称为去排队操作。Tree 树由于其分层的数据存储能力，树是算法中最有用的数据结构之一。每当我们需要表示算法中数据元素之间的层次关系时，我们就会使用树。****这种数据结构相当有趣，也相当重要，所以让我们深入了解一下。****每棵树的顶端都有一个根，还有一组由分支连接的节点，因此每棵树的节点数量是有限的。****术语****为了理解树形数据结构，我们来研究一些术语。[图片上传失败...(image-724ea2-1667467474173)]

根节点****根节点没有父母。下图的根节点是A，算法通常在其树结构中把最高值放在根节点上。****节点的级别****一个节点和它的根节点之间的距离决定了它的级别。例如，在下图中，节点D、E、F的级别是2。****同级节点****在树的同一层次的节点被称为兄弟姐妹。我们可以看到下图中的节点B和C是兄弟姐妹。****子节点和父节点****节点C的级别必须低于节点F的级别，这样节点F才是节点C的孩子；反之，节点C是节点F的父。****节点的程度****节点按其拥有的子女数量进行排序。下图中显示了一个双度节点的例子。[图片上传失败...(image-8fa1e9-1667467474173)]

一棵树的度数****如果树中的节点被相应程度的节点所连接，那么这些节点可以有一个最大的程度。下面是一个度数为2的树的例子。****子树****树的子树由根节点和每个子节点组成，而根节点是由选定的节点形成的。如下图所示，节点E的子树由节点E作为根，节点G和H作为子节点组成。****叶子节点****在一棵树上，一个叶子节点没有子女。在下图中，D、G、H和F是叶子节点。****内部节点****如果它既不是根节点也不是叶节点，就没有内部节点这一说。为了有一个子节点，必须至少有一个父节点。****有不同类型的树****根据树的特性，可以将其分为不同的类型。****程度为2的树被称为二叉树。例如，一棵二叉树的度数为2，如下图所示。****在上图中，你可以看到一棵树在四个层次上有八个节点。****每当所有节点的度数相同时，这棵树就是满的。树的度数将与节点的数量相同。如下图所示，有几种类型的树。****如左图所示，二叉树不是一棵完整的树，因为节点C的度数是1，而所有其他节点的度数是2。左边的树和中间的树都是全树。****一棵理想的树是一棵全树，它的叶子节点都在同一级别。如上图所示，右边的二叉树是一棵完美的全树，因为所有的叶子结点都在同一级别，即第2级。****有序树是一棵树，它的子节点按照特定的标准排列。例如，在从左到右遍历一棵树的过程中，同一级别的节点将随着它们的上升而增加价值。