10 Python 数据结构 [Explained With Examples]

作者
Tweet
Share
Share
Pin
0 Shares

您是否希望增强您的编程技能，掌握更多数据组织方法？ 今天就让我们一起深入学习Python中的数据结构吧！

在您学习任何新的编程语言时，理解该语言支持的基础数据类型和内置数据结构至关重要。在这份Python数据结构指南中，我们将探讨以下几个方面：

  • 数据结构带来的优势
  • Python中常用的内置数据结构，例如列表（list）、元组（tuple）、字典（dictionary）和集合（set）
  • 如何实现诸如堆栈（stack）和队列（queue）这样的抽象数据类型

让我们开始这段探索之旅吧！

为何数据结构如此重要？

在我们深入研究各种数据结构之前，先来看看使用它们能带来哪些好处：

  • 高效的数据操作：选择合适的数据结构能够显著提升数据处理的效率。例如，当需要存储相同类型的数据集合（查找时间固定且元素紧密相连）时，数组会是不错的选择。
  • 更佳的内存管理：在大型项目中，不同的数据结构在存储相同的数据时，内存效率可能大相径庭。例如，在Python中，列表和元组都可以存储各种类型的数据集合。然而，如果您确定集合不需要被修改，那么使用元组会比列表更节省内存。
  • 代码的组织性：为特定的功能选择合适的数据结构，可以使您的代码结构更清晰。其他阅读您代码的开发者会期望您按照功能需求使用特定的数据结构。例如，如果需要实现一个能够快速查找和插入的键值映射，字典就是理想之选。

列表 (List)

在Python中创建动态数组时，列表是首选的数据结构，无论是面对编码面试还是日常应用场景。

Python列表是一种可变且动态的容器类型，允许您在列表中添加或删除元素，而无需创建新的副本。

使用Python列表时，请注意：

  • 对列表进行索引和访问特定位置的元素，这是一个时间复杂度为常数的操作。
  • 在列表末尾添加元素，也是一个时间复杂度为常数的操作。
  • 在特定位置插入元素，这是一个时间复杂度为线性的操作。

Python提供了一系列列表方法，可以帮助我们高效地执行常见操作。以下代码片段展示了如何在示例列表中进行这些操作：

>>> nums = [5,4,3,2]

>>> nums.append(7)
>>> nums
[5, 4, 3, 2, 7]

>>> nums.pop()
7
>>> nums
[5, 4, 3, 2]

>>> nums.insert(0,9)
>>> nums
[9, 5, 4, 3, 2]

Python列表还支持使用in运算符进行切片操作和成员关系测试：

>>> nums[1:4]
[5, 4, 3]

>>> 3 in nums
True

列表数据结构不仅灵活且易于使用，还允许我们存储不同类型的数据元素。Python也提供了专门的数组数据结构，用于高效存储相同类型的数据元素，我们将在本指南的后续部分介绍。

元组 (Tuple)

在Python中，元组是另一种常用的内置数据结构。它们与列表类似，可以快速地通过索引访问元素或进行切片操作。但元组是不可变的，一旦创建，就不能修改。以下代码片段通过示例元组nums展示了这一点：

>>> nums = (5,4,3,2)

>>> nums[0]
5

>>> nums[0:2]
(5, 4)

>>> 5 in nums
True

>>> nums[0] = 7 # not a valid operation!
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

因此，当您需要创建不可修改的集合并高效地处理它们时，元组是理想的选择。如果集合需要被修改，列表会是更好的选择。

📋 进一步了解Python列表和元组之间的异同。

数组 (Array)

数组是在Python中相对较少被提及的数据结构。在支持的操作上，它们与列表类似，例如通过索引进行常数时间的元素访问，以及在指定位置插入元素的时间复杂度为线性时间。

然而，列表和数组之间的主要区别在于，数组只能存储单一数据类型的元素。这使得数组在内存使用上更紧凑、效率更高。

要创建数组，我们可以使用内置的array模块中的array()构造函数。这个构造函数接收一个字符串，用于指定元素的数据类型，以及元素本身。这里我们创建了一个存储浮点数的数组nums_f：

>>> from array import array
>>> nums_f = array('f',[1.5,4.5,7.5,2.5])
>>> nums_f
array('f', [1.5, 4.5, 7.5, 2.5])

您可以像操作Python列表一样对数组进行索引：

>>> nums_f[0]
1.5

数组是可变的，可以进行修改：

>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])

但是，您不能将元素修改为不同的数据类型：

>>> nums_f[0]='zero'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: must be real number, not str

字符串 (String)

在Python中，字符串是Unicode字符的不可变序列。与C等编程语言不同，Python没有单独的字符数据类型。所以，一个字符实际上就是一个长度为1的字符串。

如前所述，字符串是不可变的：

>>> str_1 = 'python'
>>> str_1[0] = 'c'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

Python字符串支持切片操作和一系列字符串格式化方法。以下是一些示例：

>>> str_1[1:4]
'yth'
>>> str_1.title()
'Python'
>>> str_1.upper()
'PYTHON'
>>> str_1.swapcase()
'PYTHON'

⚠ 请注意，以上所有操作都会返回字符串的副本，而不会修改原始字符串。如果您对此感兴趣，可以查看有关字符串操作的Python程序指南。

集合 (Set)

在Python中，集合是唯一且可哈希项的无序集合。您可以执行常见的集合运算，例如并集、交集和差集：

>>> set_1 = {3,4,5,7}
>>> set_2 = {4,6,7}

>>> set_1.union(set_2)
{3, 4, 5, 6, 7}

>>> set_1.intersection(set_2)
{4, 7}

>>> set_1.difference(set_2)
{3, 5}

默认情况下，集合是可变的，因此您可以添加新元素并修改它们：

>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}

📚 阅读Python中的集合：包含代码示例的完整指南。

冻结集合 (Frozenset)

如果您需要一个不可变的集合，可以使用冻结集合。您可以通过现有的集合或其他可迭代对象创建冻结集合。

>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})

由于frozenset_1是一个冻结集合，如果我们尝试添加元素（或以其他方式修改它），将会出现错误：

>>> frozenset_1.add(15)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

字典 (Dictionary)

Python字典在功能上类似于哈希映射。字典用于存储键值对，其中键必须是可哈希的，意味着对象的哈希值在生命周期内不会改变。

您可以使用键快速访问值、插入新项目并在常数时间内删除现有项目。字典提供了一系列方法来执行这些操作。

>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}

>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}

>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}

有序字典 (OrderedDict)

虽然Python字典本身提供键值映射，但它本质上是一种无序的数据结构。从Python 3.7开始，元素的插入顺序被保留。您可以使用collections模块中的OrderedDict来明确这一点。

如图所示，OrderedDict保留了键的插入顺序：

>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='two'
>>> od['third']='three'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])

默认字典 (Defaultdict)

在使用Python字典时，键错误是很常见的。每当您尝试访问字典中不存在的键时，都会遇到KeyError异常。

但是，使用collections模块中的defaultdict，您可以优雅地处理这种情况。当您尝试访问字典中不存在的键时，这个键会被自动添加，并使用默认工厂指定的默认值进行初始化。

>>> from collections import defaultdict
>>> prices = defaultdict(int)
>>> prices['carrots']
0

堆栈 (Stack)

堆栈是一种后进先出（LIFO）的数据结构。我们可以在堆栈上执行以下操作：

  • 压入（push）：向栈顶添加元素。
  • 弹出（pop）：移除栈顶元素。

下图说明了堆栈的压入和弹出操作：

如何使用列表实现堆栈？

在Python中，我们可以使用Python列表来实现堆栈数据结构。

对栈的操作等价于列表操作：

  • 压入：使用append()方法将元素追加到列表末尾。
  • 弹出：使用pop()方法从列表末尾删除并返回最后一个元素。

以下代码片段演示了如何使用Python列表模拟堆栈的行为：

>>> l_stk = []
>>> l_stk.append(4)
>>> l_stk.append(3)
>>> l_stk.append(7)
>>> l_stk.append(2)
>>> l_stk.append(9)
>>> l_stk
[4, 3, 7, 2, 9]
>>> l_stk.pop()
9

如何使用双端队列实现堆栈？

另一种实现堆栈的方法是使用collections模块中的双端队列（deque）。双端队列支持从两端添加和删除元素。

为了模拟堆栈，我们可以：

  • 使用append()将元素添加到双端队列的末尾；
  • 使用pop()弹出最后添加的元素。
>>> from collections import deque
>>> stk = deque()
>>> stk.append(4)
>>> stk.append(3)
>>> stk.append(7)
>>> stk.append(2)
>>> stk.append(9)
>>> stk
deque([4, 3, 7, 2,9])
>>> stk.pop()
9

队列 (Queue)

队列是一种先进先出（FIFO）的数据结构。元素被添加到队列的末尾，并从队列的开头（队头）删除，如下所示：

我们可以使用双端队列来实现队列数据结构：

  • 使用append()将元素添加到队列末尾。
  • 使用popleft()方法从队列开头删除元素。
>>> from collections import deque
>>> q = deque()
>>> q.append(4)
>>> q.append(3)
>>> q.append(7)
>>> q.append(2)
>>> q.append(9)
>>> q.popleft()
4

堆 (Heap)

在本节中，我们将讨论二叉堆，重点关注最小堆。

最小堆是一棵完全二叉树。 让我们详细解释一下完全二叉树的含义：

  • 二叉树是一种树形数据结构，其中每个节点最多有两个子节点，并且每个节点都小于其子节点。
  • 术语“完全”意味着树已完全填满，除了最后一层。如果最后一层已部分填充，则从左到右填充。

因为每个节点最多有两个子节点，并且还满足小于其子元素的性质，所以根节点是最小堆中最小的元素。

这是一个最小堆的例子：

在Python中，heapq模块帮助我们构建堆并在堆上执行操作。让我们从heapq导入所需的函数：

>>> from heapq import heapify, heappush, heappop

如果您有一个列表或其他可迭代对象，您可以通过调用heapify()从中构造一个堆：

>>> nums = [11,8,12,3,7,9,10]
>>> heapify(nums)

您可以索引第一个元素以检查它是否是最小元素：

>>> nums[0]
3

现在，如果您向堆中插入一个元素，节点将被重新排列，以满足最小堆属性。

>>> heappush(nums,1)

当我们插入 1 (1 < 3) 时，我们看到 nums[0] 返回 1，它现在是最小元素（和根节点）。

>>> nums[0]
1

您可以通过调用heappop()函数从最小堆中删除元素，如下所示：

>>> while nums:
...     print(heappop(nums))
...
# Output
1
3
7
8
9
10
11
12

Python 中的最大堆

现在您已经了解了最小堆，您能猜出我们如何实现最大堆吗？

我们可以通过将每个数字乘以-1，将最小堆的实现转换为最大堆。 最小堆中排列的负数与最大堆中排列的原始数字等效。

在Python实现中，当使用heappush()向堆添加元素时，我们可以将元素乘以-1：

>>> maxHeap = []
>>> heappush(maxHeap,-2)
>>> heappush(maxHeap,-5)
>>> heappush(maxHeap,-7)

根节点乘以-1将成为最大的元素。

>>> -1*maxHeap[0]
7

当从堆中删除元素时，使用heappop()并乘以-1以返回原始值：

>>> while maxHeap:
...     print(-1*heappop(maxHeap))
...
# Output
7
5
2

优先级队列 (Priority Queue)

让我们通过了解Python中的优先级队列数据结构来结束讨论。

我们知道：在队列中，元素按照进入队列的顺序被删除。但优先级队列会按照元素的优先级提供元素——对于调度等应用程序非常有用。因此，在任何时间点，都会返回具有最高优先级的元素。

我们可以使用键来定义优先级。在这里，我们将为键使用数字权重。

如何使用 Heapq 实现优先级队列

下面是使用heapq和Python列表的优先级队列实现：

>>> from heapq import heappush,heappop
>>> pq = []
>>> heappush(pq,(2,'write'))
>>> heappush(pq,(1,'read'))
>>> heappush(pq,(3,'code'))
>>> while pq:
...     print(heappop(pq))
...

当删除元素时，队列会首先服务于最高优先级的元素（1，’read’），然后是（2，’write’），最后是（3，’code’）。

# Output
(1, 'read')
(2, 'write')
(3, 'code')

如何使用 PriorityQueue 实现优先级队列

要实现优先级队列，我们还可以使用queue模块中的PriorityQueue类。它也在内部使用堆。

这是使用PriorityQueue的优先级队列的等效实现：

>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>> pq.put((2,'write'))
>>> pq.put((1,'read'))
>>> pq.put((3,'code'))
>>> pq
<queue.PriorityQueue object at 0x00BDE730>
>>> while not pq.empty():
...     print(pq.get())
...
# Output
(1, 'read')
(2, 'write')
(3, 'code')

总结

在本教程中，您了解了Python中各种内置的数据结构。我们还回顾了这些数据结构支持的不同操作，以及执行相同操作的内置方法。

之后，我们讨论了其他数据结构，例如堆栈、队列和优先级队列，以及它们使用collections模块功能的Python实现。

接下来，您可以查看一份适合初学者的Python项目列表。