第 10 章　数据结构入门

10.1从「一个变量」到「一群数据」

回顾第 4 章：一个变量就是「一块命名的内存」，存一个值。但现实中我们常常要处理一群数据。比如要存全班 50 个学生的成绩，用变量会怎么样？

score1 = 88
score2 = 76
score3 = 95
# …… 要写 50 行，写到手软

这不仅啰嗦，还带来一个致命问题：你没法用一个循环去遍历它们——因为 score1、score2 这些名字是散的，没有「顺序」，循环无从下手。

我们需要一种「把多个值装在一起、有顺序、能批量处理」的东西——这就是 数据结构（data structure）。

深挖一层：为什么「散的变量」注定无法批量处理

把这个痛点说透。score1、score2……score50 在 Python 眼里是50 个彼此独立的变量：每个名字各自绑定一块内存，名字与内存的对应是「点名式」的——想访问哪个，就必须在代码里把名字原样写出来。循环做不到这件事：循环需要「按位置批量访问」——给一个整数 i 就能拿到「第 i 个」，而这 50 个独立名字之间不存在任何可计算的对应关系，你无法从 score1 的位置算出 score2 在哪。

列表恰好补上了这块短板：50 个值装进连续格子之后，「第 i 个」变成了一个可计算的位置（10.4 节的「首地址 + 偏移」公式就是它的精确形式）。循环变量 i 从此有了意义——它就是偏移量，scores[i] 就是「跳到第 i 格取数」。所以数据结构的第一重意义，是把「名字寻址」升级为「位置寻址」，批量处理的大门由此打开。

再深一层：组织方式直接决定操作的成本。同一批数据，用列表装，随机访问快、中间插删慢；换成别的组织方式（见 10.4 节末尾的链表预告），插删快、随机访问慢。世界上没有「样样都快」的结构——选择数据结构，本质是看你最常做哪种操作，然后为高频操作挑一个便宜的结构。记住这条主线：这一章乃至将来任何数据结构课程，讲的其实都是「结构与成本的对应关系」。

temps = [12.5, 13.0, 11.8, 14.2, 15.0, 13.7, 12.9]

total = 0
highest = temps[0]          # 先拿第一个当基准
for t in temps:
    total = total + t         # 累加
    if t > highest:           # 遇到更大的就更新
        highest = t
average = total / len(temps)
print("平均：", average)       # 平均： 13.3
print("最高：", highest)       # 最高： 15.0

10.2列表 list：能装多个值的容器

Python 里最常用的数据结构是 列表（list），用方括号 [ ] 表示，里面用逗号隔开多个值：

scores = [88, 76, 95, 61]   # 一个列表，装 4 个成绩

要取列表里的某个值，用下标（index），写在方括号里：

scores[0]   # 第 1 个元素 → 88
scores[2]   # 第 3 个元素 → 95

列表的妙处在于：配合循环，你可以批量处理所有元素：

scores = [88, 76, 95, 61]
for s in scores:        # s 依次等于 88、76、95、61
    print(s)

下标：是「编号」，更是「偏移」

日常数数习惯从 1 开始——「第 1 个、第 2 个」，所以新手看到 scores[0] 总觉得别扭。这里先给一个过渡性的理解：把下标看成「从起点偏移的步数」。scores[0] 是「从起点偏移 0 步」，自然落在第一个元素上；scores[2] 是「偏移 2 步」，跳过前两个元素、落在第三个上。10.4 节会把这句话升级成精确的地址公式；现在先带着「下标即偏移」的直觉往下走。

Python 还提供了负下标：从末尾往前数，-1 是最后一个、-2 是倒数第二个。于是「取最后一个」不必写 scores[len(scores) - 1]，直接 scores[-1]。这个语法在「取最新记录」时特别顺手——日志列表里 logs[-1] 就是刚刚写入的最新一条。

scores = [88, 76, 95, 61]
print(scores[1])    # 76
print(scores[3])    # 61
print(scores[-1])   # 61（最后一个）
print(scores[-2])   # 95（倒数第二个）
print(scores[4])    # IndexError: list index out of range

另一个值得注意的 Python 特性：列表可以混装不同类型，[88, "缺考", 76.5, True] 完全合法，这与许多语言「数组只能装同一种类型」截然不同。原因藏在下一节：Python 列表的每个格子里放的不是值本身，而是一张张「写着地址的卡片」——地址的格式是统一的，至于地址那头是整数还是字符串，格子并不关心。

10.3内存布局：数组是连续的一排格子

现在追到底层。Python 的列表，底层其实是 数组（array）。数组在内存里有个关键性质：它的元素是「连续」存放的——一个紧挨一个，中间不留空隙。

想象内存是一长串编号的格子，数组就是其中连续的一段：

「连续」是数组最重要的性质，它带来一个巨大的好处，也带来一个限制：

深挖一层：格子里放的到底是什么？

「连续格子」的说法已经很形象，但真实情况还要再深一层：Python 列表的每个格子里放的并不是值本身，而是一张「地址卡片」（引用）。88、76 这些数字对象实际住在内存的其他角落，连续排成一排的，是它们对应的地址。取 scores[2] 时，计算机其实走了两步：第一步，按公式跳到第 2 格，读出卡片上的地址；第二步，再跳到该地址，把值取出来。

「两步跳」回答了 10.2 节留下的问题——为什么能混装类型：格子里只存地址，地址的格式统一，地址那头是整数、字符串还是布尔值都无所谓。作为对照，C 等语言的「传统数组」格子里直接放值本身，因此必须把元素类型和大小一次定死，换来的是少跳一步、更快更省。两种设计各有取舍，但「格子连续 → 下标可算出格子位置」这个随机访问的根基，两者完全一致——这正是本节标题强调「连续」的原因。

连续布局还有一个不显眼的代价：整块申请。1000 个元素的列表要一次申请 1000 格连续内存，而内存用久了会被各种数据切得七零八落（碎片化），一长段连续空位未必好找。Python 的对策是「预留余量」：列表通常多申请一些格子，append 先填空位，真满了才整体搬家到一块更大的连续内存。搬家要复制全部元素，看似昂贵，但分摊到每次 append 上成本很低（10.5 节细算这笔账）。

n = 1000
total_moves = 0
for i in range(n):
    total_moves = total_moves + (n - i)   # 在位置 i 插入要挪的元素数
print(total_moves / n)                     # 500.5

data = list(range(1000))                   # [0, 1, 2, …, 999]
data.insert(500, "新")
print(len(data))                           # 1001
print(data[500], data[501], data[1000])     # 新 500 999

账单之外：remove 与 del 这两个亲戚

除 pop 之外，删元素还有两个常用亲戚，成本结构各不相同：remove(值) 是「按内容删」——先从头扫描找到第一个等于该值的元素（平均翻一半，O(n)），找到后还要挪动补位（又是 O(n)）：一次 remove，两笔账单；del scores[i] 是「按下标删」，省去查找、只付挪动，和 pop(i) 一回事，区别只是 del 不返回被删的值、pop 会把值交给你。顺带一提 clear()——整表清空，与元素个数无关，O(1)。把它们与 pop 排在一起看：「按内容找」永远比「按位置取」贵一层，这个规律在字典、集合上同样成立，是贯穿数据结构的通则。

# 三种删除方式的账单对照（成本按 n=列表长度计）
scores = [88, 76, 95, 61, 70]
scores.remove(76)   # 按内容删：先扫到 76 在下标1，再把它后面的 95、61、70 各前移一格
del scores[0]      # 按下标删：不找，直接把 88 后面的所有元素前移一格
scores.pop()       # 删末尾：谁都不用挪（删掉的是 70）
print(scores)      # [95, 61]

10.4为什么能「随机访问」

「随机访问」（random access）意思是：不按顺序翻找，直接一步跳到任意下标取到值。比如 scores[2] 不管列表多长，都是「瞬间」取到。

这背后的原理，就是一道简单的地址换算公式。假设：

• 数组的首地址（第一个元素的位置）是 100；
• 每个元素占 1 格（大小固定）；
• 那么下标为 i 的元素，地址 = 首地址 + i。

把公式一般化：地址 = 首地址 + 下标 × 每格大小

图 10-2 里每格大小取的是 1；真实内存中一个元素往往占好几个字节，把公式一般化：元素地址 = 首地址 + 下标 × 每格字节数。一次乘法一次加法，与列表长度无关——这就是「O(1)」的准确含义：不管列表有 4 个还是 400 万个元素，定位任意一个都只花这套固定的小算术。与之相对，从头逐个翻找平均要翻一半、最坏翻到底，元素越多越慢，成本随规模 n 线性增长，记作 O(n)。大 O 记号（big-O）此刻只需记直觉：它描述成本随数据规模增长的趋势——O(1) 是「恒定、不涨」，O(n) 是「跟着 n 线性涨」。往后学到的每种数据结构、每种操作，都可以贴这样一张成本标签，选结构就是选标签。

顺手回答一个经典之问：「如果下标从 1 开始会怎样？」公式会变成「地址 = 首地址 + (下标 − 1) × 大小」，每次访问都多一次减法。今天看这一次减法微不足道，但在计算机资源寸土寸金的年代，省掉它是实打实的收益，于是「从 0 开始」成了主流传统并延续至今。更本质地说：下标天生就是偏移量，偏移的自然起点就是 0——「从 0 开始」不是怪癖，而是下标本义的直接体现。

预告：链表——把成本标签整个换掉

随机访问快是数组的招牌，插删要挪动是它的死穴。有没有组织方式恰好反过来——插删便宜、查找变贵？有，就是链表（linked list）。它不追求连续：每个元素独住一间「小屋」（节点），屋里除了值，还放着一张「下一跳地址」卡片指向下一个节点，整串数据靠卡片串起来。找元素必须从头节点出发一跳一跳数过去；但插删只需把附近一两个节点的卡片改个地址，其余节点纹丝不动。图 10-3 把两种布局画在一起对照。

把成本表翻译成「什么时候用谁」的口诀，这组对比才算真正落地。按下标频繁取数、总长相对稳定、要一口气遍历全部——用数组：地址公式一步直达，连续内存还附赠「缓存友好」的隐藏福利（硬件一次能搬一整块）；频繁在任意位置插删、总长涨落无常、内存碎片较多——用链表：定位之后改一两个指针完事，不必腾整段连续空间。放进场景里感受一下：查「第 37 号储位的灯亮不亮」，数组一步算出地址；维护一份「随时要在任意位置插入或撤销」的排班序列，链表改动局部到位。再送一条工程直觉：日常程序里数组/列表是默认选项，链表只在「插删压倒一切」的场景出场——因为链表的指针跳来跳去，对缓存反而不友好。选型从来不是背表格，而是问自己一句：我的程序里哪种操作最频繁？让最频繁的那个享受 O(1)。

10.5列表的常用操作

列表有一批常用操作，这里挑最实用的几个：

结合循环，列表能做很多事。比如求平均分：

scores = [88, 76, 95, 61]
total = 0
for s in scores:
    total = total + s       # 累加（第 8 章学的累加器）
average = total / len(scores)
print(average)              # 输出：80.0

给每个操作贴上「成本标签」

常用操作表之外，还藏着一张更重要的「成本表」，逐个分析：len(scores)——长度记在列表自己的「户口本」上，读一下就返回，O(1)；append——末尾追加谁也不挪，O(1)（偶尔碰上整体搬家，均摊下来仍是 O(1)，10.3 节的「预留余量」正是为此）；scores[i] 读或写——公式直达，O(1)；insert(i, x) 与 pop(i)——中间插删要挪后面所有元素，O(n)；95 in scores——无从计算、只能从头一个个比，O(n)。把这张账记在心里，写代码时自然就有了轻重。

从成本表能读出两条工程习惯：能 append 就不 insert——往末尾加是列表最便宜的动作，第 12 章项目里的成绩表就是纯 append 组织的；能按下标取就别用 in 找——in 是全表扫描，列表很长时反复 in 会明显拖慢。图 10-4 直观展示了 insert 的「挪人」过程。

scores = [88, 76, 95, 61]
scores.append(70)   # [88, 76, 95, 61, 70]
scores.pop(0)       # [76, 95, 61, 70]（删掉了 88）
scores[1] = 90      # [76, 90, 61, 70]

total = 0
for s in scores:
    total = total + s
print(len(scores))            # 4
print(total / len(scores))   # 74.25
print(95 in scores)          # False

10.6其他结构：元组与字典

列表之外，还有两个常用的数据结构，先混个脸熟：

元组 tuple：不能修改的列表

元组用圆括号，和列表几乎一样，但一旦创建就不能修改（不能增删改元素）。

point = (3, 5)     # 一个坐标点
point[0]           # 3
# point[0] = 9     # 报错！元组不可修改

字典 dict：按「名字」取值，而不是下标

列表靠「下标（0,1,2…）」找元素；字典靠「键（名字）」找元素，用花括号：

student = {"name": "小明", "age": 20, "score": 88}
student["name"]     # → "小明"，用键"name"取到值

为什么要有「不能改」的元组？

新手常有疑问：既然有了列表，为什么还发明一个「残废版列表」？因为不可修改不是缺陷，而是承诺。元组从创建到销毁内容永不改变，这带来两个实打实的好处：其一，它可以放心地当「钥匙」用——字典按键取值（下一小节），键必须是「不可变」的东西，列表随时可变、没资格当键，元组正合适；其二，多人协作时，「不该动的数据」放进元组等于上了锁，谁也别想悄悄改它。坐标 (x, y)、一组常量、函数的多个返回值，都适合用元组表达「生来如此、别动我」。

顺带揭一个伏笔：第 9 章讲过 return 把结果吐还给调用方；这里更进一步——return 后面可以一次列多个值，写 return average, highest, lowest, passed——Python 在背后打包的正是一个元组：四个值捆成一个不可变包裹交出去，调用方再拆包成四个变量。第 12 章项目里 compute_stats 返回四个统计值，用的就是这一手。

字典为什么「按名字」也能瞬间取到

按直觉，「按名字查」似乎得把整本字典翻一遍？恰恰不用。字典的底层叫哈希表（hash table）：对键做一次数学换算（哈希函数），直接算出这个键该住在哪个「桶」里。是不是很眼熟？列表是「下标 → 地址」一步算出，字典是「键 → 桶地址」一步算出——字典可以看作「下标从整数推广成任意键」的列表，「可计算的位置」被推广成了「可计算的键」。代价是键必须「可哈希」（本质上就是不可变），这正好呼应上一段：元组能当键、列表不能。至于哈希函数怎么设计、桶冲突怎么处理，属于后续课程；此刻记住「按键直达、平均 O(1)」即可。

readings = {"pump_a": 3.2, "pump_b": 4.8, "valve_c": 2.5}

print(readings["pump_b"])       # 4.8

total = 0
for v in readings.values():
    total = total + v
print(total / len(readings))    # 3.5

print("pump_a" in readings)     # True（查的是键）
print(readings["pump_x"])       # KeyError: 'pump_x'

元组的两个书写陷阱

元组书写上有个出了名的陷阱：单元素元组必须带逗号。("A",) 是元组，("A") 只是一对括号包着的字符串，Python 根本不会当元组看——括号在这里是「改变运算优先级」的数学括号，逗号才是元组的灵魂。同理 (5) 是整数 5，(5,) 才是「装着一个 5 的元组」。空元组没有元素、无逗号可带，写作 ()。另一条顺手记：已有列表可以一键转换成元组上锁——tuple(scores) 返回内容相同的元组；反过来 list(某元组) 解锁。真机上可以亲手验一遍：

t = ("A",)      # 元组：括号里一个元素 + 一个逗号
x = (5)        # 不是元组！这就是整数 5
print(type(t)) # <class 'tuple'>
print(type(x)) # <class 'int'>
print(len(t))  # 1
u = (88, 76)
print(u[0], u[1])   # 88 76 —— 元组同样用下标取值，只是不能赋值