03_列表与字典：C数组与结构体的平替

列表与字典：C 数组与结构体的平替 (Lists & Dicts)

---

章节概述

本章介绍 Python 中最重要的两种复合数据结构——列表（list）和字典（dict），并与 C 程序员熟悉的数组和结构体做对比。你将看到 Python 的列表如何替代 C 的动态数组（自动扩容、异构、越界保护），字典如何让哈希表的复杂操作变得一行搞定。我们还会介绍切片（slicing）和推导式（comprehension），这两者是 Python 数据处理的核心武器。

核心理念：C 程序员花 80% 的代码管理内存和边界，Python 程序员用列表和字典把注意力放回数据本身。列表不是 malloc(sizeof(int) * N)，字典不是手写哈希表——它们是 Python 的超级积木。

---

第一节：list —— 可增长的动态数组

---

1.1 list vs C 数组的本质区别

// C 语言：固定大小数组
int arr[5] = {1, 2, 3, 4, 5};
arr[0] = 99; // 合法
// arr[5] = 100; // 越界！不确定行为
 
// C 语言：动态数组（需要手工管理）
int *arr = malloc(5 * sizeof(int));
// 扩容时需要 realloc + memcpy

python -c "
# Python 列表：自动扩容、异构建、越界保护
arr = [1, 2, 3, 4, 5]
arr[0] = 99
# arr[100] = 42 # IndexError: list index out of range
arr.append(6) # 自动增长
arr.extend([7, 8, 9]) # 批量追加
print(arr)
"

1.2 列表基本操作

python -c "
arr = [10, 20, 30, 40, 50]
 
# 索引和长度
print('arr[0]:', arr[0])
print('arr[-1]:', arr[-1]) # 最后一个元素（C 没有负索引）
print('len:', len(arr))
 
# 插入
arr.insert(2, 25) # 在索引 2 处插入
print('after insert:', arr)
 
# 删除
del arr[1] # 按索引删除
print('after del:', arr)
 
# 弹出
popped = arr.pop() # 弹出最后一个
print('popped:', popped, 'arr:', arr)
 
# 查找
idx = arr.index(30) # 返回首次出现的索引
print('index of 30:', idx)
 
# 计数
count = arr.count(30) # 统计出现次数
print('count of 30:', count)
 
# 排序
arr.sort() # 原地排序
print('sorted:', arr)
"

Python 列表的 sort() 使用 Timsort（一种稳定的混合排序算法），时间复杂度 O(n log n)。[i] 索引操作是 O(1)，但在列表头部插入是 O(n)（需要移动元素）。

1.3 列表是异构建的

python -c "
# Python 列表可以存放不同类型
mixed = [1, 'hello', 3.14, [1, 2], {'key': 'value'}]
for item in mixed:
 print(type(item).__name__, ':', item)
"

对比 C 语言实现异构数组的繁琐：

// C: 异构数组需要用 union + enum tag
typedef enum { INT, STR, FLOAT } Tag;
typedef struct {
 Tag tag;
 union { int i; char *s; double f; } value;
} Variant;
 
Variant arr[5];
arr[0].tag = INT; arr[0].value.i = 42;
arr[1].tag = STR; arr[1].value.s = "hello";
arr[2].tag = FLOAT; arr[2].value.f = 3.14;
// 每次访问都要检查 tag——繁琐且易出错

---

第二节：切片 (Slicing) —— Python 的超级武器

---

2.1 切片基本语法 [start:stop:step]

python -c "
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 
print('arr[2:7]: ', arr[2:7]) # 索引 2 到 6
print('arr[:5]: ', arr[:5]) # 开头到索引 4
print('arr[5:]: ', arr[5:]) # 索引 5 到末尾
print('arr[::2]: ', arr[::2]) # 每隔一个取一个
print('arr[1::2]: ', arr[1::2]) # 从 1 开始步长 2
print('arr[::-1]: ', arr[::-1]) # 反转整个列表！
print('arr[-3:]: ', arr[-3:]) # 最后三个
"

在 C 语言中复制子数组需要：

// C: 手动循环复制子数组
#include <string.h>
int arr[] = {0,1,2,3,4,5,6,7,8,9};
int sub[5];
memcpy(sub, arr + 2, 5 * sizeof(int)); // 相当于 arr[2:7]

Python 一行：sub = arr[2:7]。

2.2 切片修改

python -c "
arr = [0, 1, 2, 3, 4, 5]
arr[1:3] = [10, 20] # 替换索引 1-2
print('replace:', arr)
 
arr[2:2] = [100, 200] # 在索引 2 处插入（不替换任何元素）
print('insert:', arr)
 
arr[1:4] = [] # 删除索引 1-3
print('delete:', arr)
 
# 步长不为 1 的切片赋值要求左右长度一致
arr[::2] = ['a', 'b', 'c']
print('step assign:', arr)
"

2.3 字符串切片同理

python -c "
s = 'Hello, World!'
print('s[::-1]: ', s[::-1]) # 反转字符串
print('s[7:]: ', s[7:])
print('s.split(\",\"):', s.split(',')) # 按分隔符切割
"

---

第三节：tuple —— 不可变列表

---

3.1 tuple 的定义和特性

python -c "
# 元组是不可变的序列
t = (1, 2, 3, 'hello')
print('type:', type(t))
print('t[0]:', t[0])
print('t[1:3]:', t[1:3])
# t[0] = 99 # TypeError: 'tuple' object does not support item assignment
 
# 单元素元组需要逗号
single = (42,) # 这是元组
not_tuple = (42) # 这是整数！括号只是优先级运算符
print(type(single), type(not_tuple))
 
# 打包和解包
a, b, c, d = t # 元组解包
print('a=', a, 'b=', b, 'c=', c, 'd=', d)
"

C 语言的对应概念：

// C 没有元组类型，用 const 数组模拟不可变性
const int t[] = {1, 2, 3};
// t[0] = 99; // 编译错误（只读）
// 没有解包语法——需要逐条赋值

Python 元组相当于 编译时固定大小、运行时不可修改的 list。它很小但很强大：常被用作函数多返回值、字典键、集合元素。

3.2 多返回值本质是元组

python -c "
def divide(a, b):
 quotient = a // b
 remainder = a % b
 return quotient, remainder # 返回的是元组！
 
q, r = divide(10, 3)
print('q =', q, 'r =', r)
 
result = divide(20, 7)
print('result tuple:', result) # (2, 6)
print('type:', type(result))
"

对比 C 使用输出参数：

// C: 通过指针参数返回多个值
void divide(int a, int b, int *quotient, int *remainder) {
 *quotient = a / b;
 *remainder = a % b;
}
 
int q, r;
divide(10, 3, &q, &r);
// Python 写法: q, r = divide(10, 3) —— 简洁六个数量级

---

第四节：dict —— 秒杀手写哈希表

---

4.1 字典基本操作

python -c "
# 字典：键值对的集合
d = {'name': 'Alice', 'age': 30, 'scores': [90, 85, 92]}
 
print('d[\"name\"]:', d['name'])
print('d.get(\"age\"):', d.get('age'))
print('d.get(\"email\", \"N/A\"):', d.get('email', 'N/A'))
 
# 添加/修改
d['email'] = 'alice@example.com'
 
# 遍历
for key, value in d.items():
 print(f'{key}: {value}')
 
# 删除
removed = d.pop('age')
print('removed:', removed, 'd:', d)
 
# 检查键是否存在
print('\"name\" in d:', 'name' in d)
print('\"salary\" in d:', 'salary' in d)
"

C 语言中手写哈希表需要 hcreate() / hsearch()（POSIX）或自行实现：

#include <search.h> // POSIX 哈希表 API
#include <string.h>
 
// 创建哈希表
hcreate(100);
 
// 插入（需要手动管理键值的内存）
ENTRY e, *ep;
e.key = "name";
e.data = "Alice";
hsearch(e, ENTER);
 
// 查找
e.key = "name";
ep = hsearch(e, FIND);
// 注意：POSIX 的 hsearch 是全局单例，不支持多表并存

4.2 字典推导式

python -c "
# 从一个列表创建字典
keys = ['a', 'b', 'c']
values = [1, 2, 3]
d = {k: v for k, v in zip(keys, values)}
print(d)
 
# 从现有数据转换
squares = {x: x**2 for x in range(6)}
print(squares)
 
# 过滤
filtered = {k: v for k, v in squares.items() if v > 10}
print(filtered)
"

4.3 嵌套字典和 JSON

python -c "
import json
 
# Python 字典几乎就是 JSON 的镜像
config = {
 'server': {
 'host': '0.0.0.0',
 'port': 8080,
 'debug': False
 },
 'database': {
 'type': 'postgresql',
 'pool_size': 10,
 'retries': [1, 3, 5]
 }
}
 
# 字典 ↔ JSON 字符串
json_str = json.dumps(config, indent=2)
print('JSON:')
print(json_str)
 
# JSON ↔ 字典
parsed = json.loads(json_str)
print('\\nParsed type:', type(parsed))
"

C 程序员处理 JSON 需要引入 cJSON 或 jannson 等第三方库，并手动管理解析后的内存。Python 的 json 模块是标准库的一部分，json.loads() 返回原生 dict/list，无需操心 free。

---

第五节：set 与推导式 (Comprehension)

---

5.1 set —— 去重与集合运算

python -c "
# 集合：无序、不重复的元素集合
s1 = {1, 2, 3, 4, 5}
s2 = {4, 5, 6, 7, 8}
 
print('并集:', s1 | s2) # {1,2,3,4,5,6,7,8}
print('交集:', s1 & s2) # {4,5}
print('差集:', s1 - s2) # {1,2,3}
print('对称差:', s1 ^ s2) # {1,2,3,6,7,8}
 
# 去重
items = [1, 2, 2, 3, 3, 3, 4]
unique = list(set(items))
print('去重:', unique)
 
# 成员检查 O(1)
print('3 in s1:', 3 in s1) # True
"

对比 C 语言：

// C: 集合运算需要手工实现
// 交集：
for (int i = 0; i < n1; i++)
 for (int j = 0; j < n2; j++)
 if (a[i] == b[j]) { ... }
// O(n²) 时间复杂度，Python 的 set 操作是 O(n)

5.2 列表推导式 (List Comprehensions)

python -c "
# 【核心语法】列表推导式
# [表达式 for 变量 in 可迭代对象 if 条件]
 
# 基本形式
squares = [x**2 for x in range(10)]
print('squares:', squares)
 
# 带条件过滤
evens = [x for x in range(20) if x % 2 == 0]
print('evens:', evens)
 
# 嵌套循环
pairs = [(a, b) for a in 'AB' for b in '12']
print('pairs:', pairs)
 
# 嵌套推导式（矩阵转置）
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transposed = [[row[i] for row in matrix] for i in range(3)]
print('transposed:', transposed)
"

对比 C 语言实现同样功能：

// C: 生成 0-9 的平方列表
int squares[10];
for (int i = 0; i < 10; i++)
 squares[i] = i * i;
 
// Python: [x**2 for x in range(10)]
// 少写 3 行，而且它直接生成 list 对象，不需要预先知道大小

5.3 字典推导式与集合推导式

python -c "
# 字典推导式
word = 'hello'
freq = {ch: word.count(ch) for ch in set(word)}
print('freq:', freq)
 
# 集合推导式
squares_set = {x**2 for x in range(-5, 6)}
print('squares_set:', squares_set)
 
# 对比：等价的 for 循环写法
result = []
for x in range(-5, 6):
 result.append(x**2)
print('loop version:', result)
# 推导式版本: [x**2 for x in range(-5, 6)]
"

5.4 生成器表达式 —— 延迟求值

python -c "
# 列表推导式：立即求值，占用内存
big_list = [x**2 for x in range(10**6)]
import sys
print('list size:', sys.getsizeof(big_list), 'bytes')
 
# 生成器表达式：延迟求值
big_gen = (x**2 for x in range(10**6))
print('generator size:', sys.getsizeof(big_gen), 'bytes')
print('first 5:', [next(big_gen) for _ in range(5)])
"

生成器表达式使用小括号 (...) 而非中括号 [...]。它类似于 C 中的”惰性迭代器”——只有在请求时才计算下一个值，适合处理无法一次性放入内存的超大数据集。

---

练习

以下题目用于验证本章所学内容：

题号	题目	链接	涉及知识点
P1004	方格取数	https://www.luogu.com.cn/problem/P1004	二维数组、循环
P1008	全排列	https://www.luogu.com.cn/problem/P1008	递归、排列
P1001	A+B Problem	https://www.luogu.com.cn/problem/P1001	输入输出、变量