10 Python数据结构[例子解释]
你是否想要将数据结构添加到你的编程工具箱中？今天就通过学习Python中的数据结构来迈出第一步。
当你学习一门新的编程语言时，理解基本数据类型和语言支持的内置数据结构是很重要的。在这个关于Python中数据结构的指南中，我们将涵盖以下内容：
- 数据结构的优势
- Python中的内置数据结构，如列表、元组、字典和集合
- 抽象数据类型（如栈和队列）的实现
让我们开始吧！
为什么数据结构有帮助？
在我们介绍各种数据结构之前，让我们看看使用数据结构的好处：
- 高效的数据处理：选择合适的数据结构有助于更有效地处理数据。例如，如果你需要存储同一数据类型的一组项目，并具有恒定的查找时间和紧密的耦合，你可以选择数组。
- 更好的内存管理：在大型项目中，对于存储相同数据的情况，一种数据结构可能比另一种更节省内存。例如，在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还有一个专用的数组数据结构，用于高效地存储相同数据类型的元素。我们将在本指南的后面学习它。
元组
在Python中，元组是另一个流行的内置数据结构。它们和Python列表类似，可以通过索引以恒定的时间访问和切片。但是它们是不可变的，所以你不能在原地修改它们。下面的代码片段通过一个示例nums元组解释了上述内容：
>>> nums = (5,4,3,2)
>>> nums[0]
5
>>> nums[0:2]
(5, 4)
>>> 5 in nums
True
>>> nums[0] = 7 # 不是有效的操作！
Traceback (most recent call last):
File "", line 1, in
TypeError: 'tuple' object does not support item assignment当您想创建一个不可变的集合并能够高效处理它时，应该考虑使用元组。如果您希望集合是可变的，最好使用列表。
📋 了解更多关于 similarities and differences between Python lists and tuples。
数组
数组是 Python 中较少知名的数据结构。它们与 Python 列表在支持的操作方面相似，例如常数时间的索引和线性时间的在特定索引处插入元素。
然而，列表和数组之间的关键区别在于数组存储一个单一数据类型的元素。因此，它们紧密耦合并且更节省内存。
要创建一个数组，可以使用内置的array模块中的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 "", line 1, in
TypeError: must be real number, not str字符串
在 Python 中，字符串是由 Unicode 字符组成的不可变集合。与 C 等编程语言不同，Python 没有专用的字符数据类型。因此，一个字符也是长度为一的字符串。
如前所述，字符串是不可变的：
>>> str_1 = 'python'
>>> str_1[0] = 'c'
Traceback (most recent call last):
File "", line 1, in
TypeError: 'str' object does not support item assignmentPython 字符串支持字符串切片和一组用于格式化字符串的方法。以下是一些示例：
>>> str_1[1:4]
'yth'
>>> str_1.title()
'Python'
>>> str_1.upper()
'PYTHON'
>>> str_1.swapcase()
'PYTHON'⚠ 请记住，所有上述操作都返回字符串的副本，不会修改原始字符串。如果您感兴趣，请查看关于 Python Programs on String Operations 的指南。
集合
在 Python 中，sets 是一组唯一且可散列的项。您可以执行常见的集合操作，例如并集、交集和差集：
>>> 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}冻结集合
如果您想要一个不可变的集合，可以使用冻结集合。您可以从现有集合或其他可迭代对象创建一个冻结集合。
>>> 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 "", line 1, in
AttributeError: 'frozenset' object has no attribute 'add'字典
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异常。
但是，使用defaultdict，您可以原生地处理此情况。当我们尝试访问一个不存在于字典中的键时，该键将被添加并用默认工厂指定的默认值初始化。
>>> from collections import defaultdict
>>> prices = defaultdict(int)
>>> prices['carrots']
0Stacks
堆栈是一种后进先出（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()
9Queues
队列是一种先进先出（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堆
在本节中，我们将讨论二叉堆。我们将重点讨论最小堆。
最小堆是一种完全二叉树。让我们解释一下完全二叉树的含义：
- 二叉树是一种树形数据结构，每个节点最多有两个子节点，且每个节点都小于其子节点。
- 完全表示树是完全填充的，除了最后一层可能除外。如果最后一层部分填充，则从左到右填充。
由于每个节点最多有两个子节点，并且满足它小于其子节点的属性，所以根节点是最小堆中的最小元素。
这是一个示例最小堆：
在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))
...# 输出
1
3
7
8
9
10
11
12Python中的最大堆
现在你已经了解了最小堆，你能猜出我们如何实现最大堆吗？
嗯，我们可以通过将每个数字乘以-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))
...# 输出
7
5
2优先队列
让我们通过学习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实现优先级队列
为了实现优先级队列，我们还可以使用PriorityQueue类从queue模块中使用。这也在内部使用堆。
下面是使用PriorityQueue实现的优先级队列的等效实现：
>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>> pq.put((2,'write'))
>>> pq.put((1,'read'))
>>> pq.put((3,'code'))
>>> pq
>>> while not pq.empty():
... print(pq.get())
...# Output
(1, 'read')
(2, 'write')
(3, 'code')总结
在本教程中，您了解了Python中各种内置数据结构。我们还介绍了这些数据结构支持的不同操作以及执行相同操作的内置方法。
然后，我们介绍了其他数据结构，如栈、队列和优先级队列，以及它们在Python中的实现，其中使用了collections模块提供的功能。
接下来，请查看beginner-friendly Python projects的列表。
