第2章:数据结构
一、导读
1.1 本章学习目标
第2章深入讲解 Python 的内置数据结构:列表、元组、字典、集合、双端队列。重点在于理解它们的内部实现和使用技巧。
本章核心学习目标:
- 掌握列表和元组的区别:可变 vs 不可变
- 理解字典的内部实现:哈希表的优化
- 掌握集合的数学运算:并集、交集、差集
- 了解 collections 模块:deque、Counter、defaultdict
1.2 为什么本章如此重要
数据结构是编程的基础。Python 的内置数据结构经过高度优化,理解它们的特性有助于写出高效代码。
1.3 核心问题引导
列表的 append 为什么是 O(1) 均摊?
字典在 Python 3.7+ 为什么保持插入顺序?
元组比列表快的原因是什么?
二、核心概念详解
2.1 列表推导与生成器表达式
python
# 列表推导: 简洁高效
symbols = [chr(i) for i in range(32, 127) if i % 2 == 0]
# 嵌套推导
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flat = [x for row in matrix for x in row] # [1,2,3,4,5,6,7,8,9]
# 生成器表达式: 惰性求值,节省内存
total = sum(x * x for x in range(1_000_000)) # 不创建列表
# 笛卡尔积
colors = ['red', 'blue']
sizes = ['S', 'M', 'L']
shirts = [(c, s) for c in colors for s in sizes]2.2 元组的不可变性
python
# 元组不可变,但包含的可变对象可以修改
t = (1, [2, 3], 4)
# t[0] = 10 # TypeError
t[1].append(5) # OK: 修改的是列表,不是元组
print(t) # (1, [2, 3, 5], 4)
# 元组作为字典键
locations = {}
locations[(35.68, 139.69)] = 'Tokyo'
locations[(51.51, -0.13)] = 'London'
# 命名元组
from collections import namedtuple
City = namedtuple('City', 'name country population coordinates')
tokyo = City('Tokyo', 'JP', 36.933, (35.689722, 139.691667))
print(tokyo.name) # Tokyo
print(tokyo._fields) # ('name', 'country', 'population', 'coordinates')2.3 字典的优化
python
# Python 3.7+: 字典保持插入顺序
d = {'one': 1, 'two': 2, 'three': 3}
print(list(d.keys())) # ['one', 'two', 'three']
# 字典推导
d = {chr(i): i for i in range(65, 70)}
# {'A': 65, 'B': 66, 'C': 67, 'D': 68, 'E': 69}
# 常用字典方法
d = {'a': 1, 'b': 2}
d.setdefault('c', 3) # 如果键不存在,设置默认值
d.update({'d': 4, 'e': 5})
print(d.get('f', 0)) # 0 (不存在时返回默认值)
# defaultdict
from collections import defaultdict
index = defaultdict(list)
for word in ['apple', 'banana', 'avocado', 'blueberry']:
index[word[0]].append(word)
# {'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry']}2.4 集合
python
# 集合运算
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
print(a | b) # 并集: {1, 2, 3, 4, 5, 6}
print(a & b) # 交集: {3, 4}
print(a - b) # 差集: {1, 2}
print(a ^ b) # 对称差集: {1, 2, 5, 6}
# 子集/超集
print({1, 2} <= a) # True (子集)
print(a >= {1, 2}) # True (超集)
# frozenset: 不可变集合,可用作字典键
fs = frozenset([1, 2, 3])
d = {fs: 'value'}三、实战案例
3.1 案例一:高效的去重和排序
python
# 去重保持顺序
def unique_preserve_order(seq):
seen = set()
result = []
for item in seq:
if item not in seen:
seen.add(item)
result.append(item)
return result
items = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
print(unique_preserve_order(items)) # [3, 1, 4, 5, 9, 2, 6]
# 按多个键排序
students = [
('Alice', 'A', 85),
('Bob', 'B', 90),
('Charlie', 'A', 92),
('David', 'B', 78),
]
# 先按班级,再按分数降序
students.sort(key=lambda s: (s[1], -s[2]))四、本章小结
列表推导简洁高效,生成器表达式节省内存
元组不可变,适合用作字典键和集合元素
字典在 Python 3.7+ 保持插入顺序
集合支持数学运算,适合去重和关系计算
五、思考与练习
为什么列表的 insert(0, x) 是 O(n)?
如何实现一个有序字典(在 Python 3.7 之前)?