第 5 章 数据结构（内置容器）

5.1 列表 list

列表是 Python 中最常用的数据结构——有序、可变、允许重复元素。

5.1.1 创建、索引与切片

# 创建
fruits = ["apple", "banana", "cherry"]
numbers = [1, 2, 3, 4, 5]
mixed = [1, "hello", True, 3.14, None]   # 可以混合类型
empty = []
from_range = list(range(5))               # [0, 1, 2, 3, 4]

# 索引
fruits[0]     # "apple"
fruits[-1]    # "cherry"

# 切片（返回新列表）
numbers[1:4]   # [2, 3, 4]
numbers[::2]   # [1, 3, 5]
numbers[::-1]  # [5, 4, 3, 2, 1]

# 切片赋值 — 可以替换、插入、删除
lst = [1, 2, 3, 4, 5]
lst[1:3] = [20, 30]    # [1, 20, 30, 4, 5] — 替换
lst[1:1] = [10, 15]    # [1, 10, 15, 20, 30, 4, 5] — 插入
lst[1:3] = []           # [1, 20, 30, 4, 5] — 删除

5.1.2 增删改查常用方法

lst = [1, 2, 3]

# 添加
lst.append(4)          # [1, 2, 3, 4] — 尾部添加单个元素
lst.extend([5, 6])     # [1, 2, 3, 4, 5, 6] — 尾部添加多个
lst.insert(0, 0)       # [0, 1, 2, 3, 4, 5, 6] — 指定位置插入

# + 和 * 运算符
[1, 2] + [3, 4]    # [1, 2, 3, 4] — 创建新列表
[0] * 5             # [0, 0, 0, 0, 0]

# 删除
lst.pop()              # 6 — 弹出并返回末尾元素
lst.pop(0)             # 0 — 弹出并返回指定位置元素
lst.remove(3)          # 删除第一个值为 3 的元素
del lst[0]             # 删除指定位置
lst.clear()            # 清空列表

# 查找
fruits = ["apple", "banana", "cherry", "banana"]
fruits.index("banana")        # 1 — 返回第一个匹配的索引
fruits.count("banana")        # 2 — 计数
"apple" in fruits             # True — 成员检测
"grape" not in fruits         # True

# 其他
lst = [3, 1, 4, 1, 5, 9]
len(lst)          # 6
min(lst)          # 1
max(lst)          # 9
sum(lst)          # 23
lst.reverse()     # 原地反转
lst.copy()        # 浅拷贝，等价于 lst[:]

5.1.3 列表排序与 key 函数

# sort() — 原地排序，返回 None
numbers = [3, 1, 4, 1, 5, 9, 2, 6]
numbers.sort()                   # [1, 1, 2, 3, 4, 5, 6, 9]
numbers.sort(reverse=True)       # [9, 6, 5, 4, 3, 2, 1, 1]

# sorted() — 返回新列表，原列表不变
original = [3, 1, 4, 1, 5]
new_list = sorted(original)      # original 不变

# key 参数 — 自定义排序规则
words = ["banana", "pie", "Washington", "a"]
words.sort(key=len)              # ['a', 'pie', 'banana', 'Washington']
words.sort(key=str.lower)        # 不区分大小写排序

# 复杂排序
students = [
    ("Alice", 90),
    ("Bob", 75),
    ("Charlie", 90),
    ("David", 85),
]

# 按成绩降序，成绩相同按姓名升序
students.sort(key=lambda s: (-s[1], s[0]))
# [('Alice', 90), ('Charlie', 90), ('David', 85), ('Bob', 75)]

# 使用 operator.itemgetter（比 lambda 更快）
from operator import itemgetter
students.sort(key=itemgetter(1), reverse=True)

5.1.4 列表的浅拷贝与深拷贝

# 赋值 — 不是拷贝，是引用
a = [1, [2, 3], 4]
b = a          # b 和 a 指向同一对象
b[0] = 99
print(a)       # [99, [2, 3], 4] — a 也变了

# 浅拷贝 — 只拷贝一层
a = [1, [2, 3], 4]
b = a.copy()        # 等价于 a[:] 或 list(a)
b[0] = 99
print(a)            # [1, [2, 3], 4] — 第一层不受影响
b[1][0] = 99
print(a)            # [1, [99, 3], 4] — 内层对象仍然共享！

# 深拷贝 — 递归拷贝所有层级
import copy
a = [1, [2, 3], 4]
b = copy.deepcopy(a)
b[1][0] = 99
print(a)            # [1, [2, 3], 4] — 完全独立

* 重复创建列表的陷阱：

# 创建二维列表的错误方式
matrix = [[0] * 3] * 3
matrix[0][0] = 1
print(matrix)
# [[1, 0, 0], [1, 0, 0], [1, 0, 0]]  — 三行是同一个列表！

# 正确方式
matrix = [[0] * 3 for _ in range(3)]
matrix[0][0] = 1
print(matrix)
# [[1, 0, 0], [0, 0, 0], [0, 0, 0]]  — 各自独立

5.2 元组 tuple

元组是不可变的有序序列。

5.2.1 不可变性与用途

# 创建
t = (1, 2, 3)
single = (42,)      # 注意逗号！(42) 只是数字 42 加括号
empty = ()
from_list = tuple([1, 2, 3])

# 解包
x, y, z = (1, 2, 3)
first, *rest = (1, 2, 3, 4, 5)  # first=1, rest=[2,3,4,5]
first, *middle, last = (1, 2, 3, 4, 5)  # first=1, middle=[2,3,4], last=5

# 不可变
t = (1, 2, 3)
# t[0] = 99  # TypeError!

# 但如果元组包含可变对象...
t = (1, [2, 3], 4)
t[1].append(99)     # 合法！修改的是列表，不是元组
print(t)            # (1, [2, 3, 99], 4)

元组的用途：

# 1. 函数多值返回
def get_min_max(data):
    return min(data), max(data)

lo, hi = get_min_max([3, 1, 4, 1, 5])

# 2. 字典的键（列表不行，因为列表不可哈希）
locations = {
    (35.68, 139.69): "Tokyo",
    (39.90, 116.40): "Beijing",
}

# 3. 表示固定结构的数据
point = (3, 4)
rgb = (255, 128, 0)

# 4. 函数参数打包和解包
def add(a, b):
    return a + b
args = (3, 4)
add(*args)  # 7

5.2.2 命名元组 namedtuple

给元组的每个位置取名字，兼具元组的不可变性和类的可读性：

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
p = Point(3, 4)
print(p.x, p.y)       # 3 4
print(p[0], p[1])     # 3 4 — 仍然支持索引
print(p)               # Point(x=3, y=4)

# 带默认值
Point3D = namedtuple("Point3D", ["x", "y", "z"], defaults=[0])
p = Point3D(1, 2)     # Point3D(x=1, y=2, z=0)

# 转换
p._asdict()            # {'x': 3, 'y': 4}
p._replace(x=10)       # Point(x=10, y=4) — 返回新对象

# 实际应用
Color = namedtuple("Color", "red green blue")
white = Color(255, 255, 255)
print(f"R={white.red}, G={white.green}, B={white.blue}")

现代替代：typing.NamedTuple

from typing import NamedTuple

class Point(NamedTuple):
    x: float
    y: float
    z: float = 0.0

p = Point(1.0, 2.0)
print(p)  # Point(x=1.0, y=2.0, z=0.0)

5.3 字典 dict

字典是键值对的无序（Python 3.7+ 保持插入顺序）集合。

5.3.1 字典创建与基本操作

# 创建
d1 = {"name": "Alice", "age": 30}
d2 = dict(name="Alice", age=30)
d3 = dict([("name", "Alice"), ("age", 30)])
d4 = {x: x**2 for x in range(5)}  # {0:0, 1:1, 2:4, 3:9, 4:16}

# 访问
d1["name"]             # "Alice"
# d1["email"]          # KeyError!
d1.get("email")        # None — 安全访问
d1.get("email", "N/A") # "N/A" — 提供默认值

# 添加 / 修改
d1["email"] = "alice@example.com"
d1["age"] = 31

# 删除
del d1["email"]
age = d1.pop("age")           # 30，删除并返回值
d1.pop("missing", None)       # None，键不存在时不报错
item = d1.popitem()            # 弹出最后一个键值对

# 遍历
person = {"name": "Alice", "age": 30, "city": "Beijing"}

for key in person:                    # 遍历键
    print(key)
for value in person.values():         # 遍历值
    print(value)
for key, value in person.items():     # 遍历键值对
    print(f"{key}: {value}")

# 成员检测（检测的是键）
"name" in person       # True
"Alice" in person      # False — 不检测值

# 其他方法
person.keys()          # dict_keys(['name', 'age', 'city'])
person.values()        # dict_values(['Alice', 30, 'Beijing'])
person.items()         # dict_items([('name', 'Alice'), ...])
len(person)            # 3

setdefault 和 update：

# setdefault — 键不存在时设置默认值并返回
d = {}
d.setdefault("fruits", []).append("apple")
d.setdefault("fruits", []).append("banana")
print(d)  # {'fruits': ['apple', 'banana']}

# update — 批量更新
d1 = {"a": 1, "b": 2}
d1.update({"b": 20, "c": 30})
print(d1)  # {'a': 1, 'b': 20, 'c': 30}

# 用关键字参数
d1.update(d=40, e=50)

5.3.2 字典推导式

# 基本字典推导
squares = {x: x**2 for x in range(6)}
# {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

# 带条件
even_squares = {x: x**2 for x in range(10) if x % 2 == 0}
# {0: 0, 2: 4, 4: 16, 6: 36, 8: 64}

# 键值互换
original = {"a": 1, "b": 2, "c": 3}
inverted = {v: k for k, v in original.items()}
# {1: 'a', 2: 'b', 3: 'c'}

# 过滤字典
scores = {"Alice": 90, "Bob": 55, "Charlie": 78, "David": 45}
passed = {name: score for name, score in scores.items() if score >= 60}
# {'Alice': 90, 'Charlie': 78}

5.3.3 defaultdict、OrderedDict、Counter

from collections import defaultdict, OrderedDict, Counter

# defaultdict — 访问不存在的键时自动创建默认值
word_count = defaultdict(int)
for word in "hello world hello python hello".split():
    word_count[word] += 1
print(dict(word_count))  # {'hello': 3, 'world': 1, 'python': 1}

# 分组
groups = defaultdict(list)
students = [("Alice", "A"), ("Bob", "B"), ("Charlie", "A"), ("David", "B")]
for name, grade in students:
    groups[grade].append(name)
print(dict(groups))  # {'A': ['Alice', 'Charlie'], 'B': ['Bob', 'David']}

# Counter — 计数器
c = Counter("abracadabra")
print(c)                   # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
print(c.most_common(2))    # [('a', 5), ('b', 2)]

# Counter 的运算
c1 = Counter(a=3, b=1)
c2 = Counter(a=1, b=2)
print(c1 + c2)   # Counter({'a': 4, 'b': 3})
print(c1 - c2)   # Counter({'a': 2})

# OrderedDict — Python 3.7+ 普通 dict 已保持顺序，但 OrderedDict 仍有用处
# 1. == 比较时关心顺序
from collections import OrderedDict
d1 = OrderedDict(a=1, b=2)
d2 = OrderedDict(b=2, a=1)
print(d1 == d2)  # False — 顺序不同

d3 = {"a": 1, "b": 2}
d4 = {"b": 2, "a": 1}
print(d3 == d4)  # True — 普通 dict 不关心顺序

# 2. move_to_end 方法
d1.move_to_end("a")    # 移到末尾
d1.move_to_end("b", last=False)  # 移到开头

5.3.4 字典合并运算符（Python 3.9+）

defaults = {"color": "red", "size": 10, "visible": True}
overrides = {"color": "blue", "size": 20}

# | 合并（创建新字典）
merged = defaults | overrides
# {'color': 'blue', 'size': 20, 'visible': True}

# |= 就地合并
defaults |= overrides

# 旧方法（3.9 之前）
merged = {**defaults, **overrides}

5.4 集合 set 与 frozenset

集合是无序、不重复的元素集合。

5.4.1 集合运算

# 创建
s1 = {1, 2, 3, 4, 5}
s2 = {4, 5, 6, 7, 8}
empty = set()          # 注意：{} 创建的是空字典！

# 从列表去重
numbers = [1, 2, 2, 3, 3, 3, 4]
unique = list(set(numbers))  # [1, 2, 3, 4]（顺序可能变）

# 保留顺序的去重
unique_ordered = list(dict.fromkeys(numbers))  # [1, 2, 3, 4]

# 基本操作
s = {1, 2, 3}
s.add(4)           # {1, 2, 3, 4}
s.remove(2)        # {1, 3, 4} — 不存在会 KeyError
s.discard(99)      # {1, 3, 4} — 不存在也不报错
s.pop()            # 弹出任意一个元素
len(s)
3 in s

# 集合运算
s1 = {1, 2, 3, 4, 5}
s2 = {4, 5, 6, 7, 8}

s1 | s2     # {1, 2, 3, 4, 5, 6, 7, 8}  并集
s1 & s2     # {4, 5}                      交集
s1 - s2     # {1, 2, 3}                   差集
s2 - s1     # {6, 7, 8}
s1 ^ s2     # {1, 2, 3, 6, 7, 8}          对称差集

# 等价方法
s1.union(s2)
s1.intersection(s2)
s1.difference(s2)
s1.symmetric_difference(s2)

# 子集和超集
{1, 2} <= {1, 2, 3}     # True — 子集
{1, 2, 3} >= {1, 2}     # True — 超集
{1, 2} < {1, 2, 3}      # True — 真子集
{1, 2, 3}.isdisjoint({4, 5})  # True — 无交集

5.4.2 集合推导式

# 基本集合推导
squares = {x**2 for x in range(-5, 6)}
# {0, 1, 4, 9, 16, 25}

# 字符串中的唯一字符
text = "hello world"
unique_chars = {c for c in text if c != " "}
# {'d', 'e', 'h', 'l', 'o', 'r', 'w'}

frozenset — 不可变集合

fs = frozenset([1, 2, 3])
# fs.add(4)  # AttributeError — 不可变

# 可以作为字典的键或集合的元素
d = {frozenset({1, 2}): "pair"}
nested = {frozenset({1, 2}), frozenset({3, 4})}

5.5 推导式总结

推导式是 Python 最 Pythonic 的特性之一：

# 列表推导式
squares = [x**2 for x in range(10)]

# 带条件的列表推导
evens = [x for x in range(20) if x % 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]
# 等价于:
# for row in matrix:
#     for x in row:
#         flat.append(x)

# 字典推导式
word_lengths = {word: len(word) for word in ["hello", "world", "python"]}

# 集合推导式
unique_lengths = {len(word) for word in ["hello", "world", "python"]}

# 生成器表达式（不创建列表，惰性求值，省内存）
total = sum(x**2 for x in range(1000000))
# 不用 sum([x**2 for x in range(1000000)])，那会先创建一个百万元素的列表

推导式 vs 循环

# 推导式更简洁、通常更快
# 但如果逻辑太复杂，用循环更好

# 好的推导式 — 简洁明了
result = [x.strip().lower() for x in lines if x.strip()]

# 坏的推导式 — 过于复杂，不如用循环
result = [
    transform(x)
    for group in data
    for x in group.items
    if x.is_valid()
    if not x.is_deleted()
]

# 等价的循环 — 在这种情况下更清晰
result = []
for group in data:
    for x in group.items:
        if x.is_valid() and not x.is_deleted():
            result.append(transform(x))

容器选择指南

本章小结：Python 提供了丰富的内置数据结构。列表和字典是最常用的，理解它们的时间复杂度、可变性和拷贝行为至关重要。推导式是 Python 的标志性语法，能让代码更简洁；但过度嵌套时应退回使用循环。