第 1 章 绪论

Introduction

教育与工作经历

2010-2014 中国科学技术大学 应用物理和计算机双学士
2014-2017 中国科学院大学 数字电路设计、编译工具链
2017-2021 加州大学圣克鲁兹分校 计算机工程博士（计算机网络）
2021.3 -2025.3 美国谷歌 高级软件工程师
谷歌内部全球骨干网络协议
机器学习模型优化、超高性能数据索引
2025.4- 至今 南京大学 软件学院 准聘副教授 国家级青年人才

研究方向

研究方向

课程组织

上课和课件

  • 我不要求来，但是我不会让你白来
  • 我新做了一套课件，这套课件还不成熟，只在课上播放
  • 课程网站上还是放原版课件
  • 不要找我要新版课件

分数构成

  • 上机作业：8 次，约 16 道题
  • 平时作业：来自旧版 PPT，拍照上传 Moodle
  • 期末考试
  • 平行班一切标准平行：题目一样、评分标准一样，最终分布的平均值保持一致

让我们开始

从会写程序开始

同学们已经学习过 C++、Java 等程序设计语言，熟悉了：

  • 数据类型
  • 表达式与控制流
  • 函数与类
  • 基本的程序组织方法

这些知识让我们能够写出程序。

但是，复杂软件还需要什么

  • 文件系统：目录之间的一对多层级关系怎样表示
  • 编译器：变量名怎样快速查找，表达式怎样表示成抽象语法树（Abstract Syntax Tree，AST）
  • 数据库：索引怎样组织，才能避免每次从头扫描
  • 大语言模型（Large Language Model，LLM）推理：词元序列、键值缓存（Key-Value Cache，KV Cache）、请求队列分别需要不同的数据组织方式

虽然这些系统的目标和功能完全不同，但是它们都在反复处理几个基本问题：顺序、层级、连接、查找、优先级以及计算成本。

数据结构与算法：组织数据，组织计算

数据结构（data structure）

组织数据，表达数据之间的关系

算法（algorithm）

组织计算过程，系统地解决问题

数据结构与算法二者相辅相成：数据组织形式和计算方法互相耦合

  • 数据怎样组织，会决定哪些操作容易、哪些操作昂贵
  • 算法需要执行什么操作，又会反过来决定数据应该怎样组织

本课程接下来要做的，就是把复杂系统里反复出现的问题抽象成少数可复用的结构与算法，并学会根据工作负载和约束进行选择。

本章路线图

绪论

真实场景
问题如何抽象 数据结构
D / R / Ops 抽象数据类型（Abstract Data Type，ADT）
接口与实现分离 算法的核心概念
定义、正确性（correctness）、复杂度 递归算法（recursive algorithm）
调用树（call tree）与调用栈（call stack） 工程基础
泛型（generics）· 异常（exception）· 输入/输出（input/output，I/O）

学习目标

完成本章后，应能回答：

  • 为什么数据结构不只是“存数据”
  • 如何从场景中识别线性表（linear list）、树（tree）、图（graph）、栈（stack）、队列（queue）等结构
  • 数据对象、关系、操作分别表示什么
  • 逻辑结构（logical structure）、物理结构（physical structure）和操作实现为什么要分开讨论
  • 抽象数据类型如何隔离使用者和实现者
  • 算法与程序有什么区别
  • 递归为什么必须有终止条件，并让问题规模持续缩小
  • 泛型、异常和输入/输出为什么是数据结构代码的工程基础

从真实场景到结构

数据结构通常不是凭空选择的，而是从问题中长出来的。

  • 游戏局面：一个状态可以走向多个后继状态
  • 图书目录：记录需要按顺序插入、删除、查找
  • 交通路口：道路之间存在能否同时通行的冲突关系

场景一：游戏中的一次选择

角色来到一个危险位置：

  • 前面有一个问号砖块
  • 地面上有一只乌龟
  • 右侧还有悬崖

现在可以做什么？

  • 顶问号砖块
  • 踩乌龟
  • 直接向前跳

同一个局面下，可能有不止一种合理选择。

从一次选择到决策树

把当前游戏局面看成一个状态。

每一种可选动作，都会产生一个新的局面。

而新的局面，又会继续产生新的选择。

于是，所有可能的未来会逐层展开。

这就是一棵决策树。

  • 单一决策主体 + 环境
  • 多方决策主体博弈
  • 智能体和动态环境多主体合作/交互

场景二：怎样管理这些书？

图书馆里有很多书。

如果我们只是想一本一本地浏览

如果读者给出一本书的 ISBN，希望马上找到它呢？

如果读者提出一个更复杂的问题：找 2020 年以后出版、数据库方向、当前可借阅的书，并按出版时间排序？

还是这些书，但需要支持的操作已经完全不同。

当“前后顺序”最重要

假设这些书已经排成一个确定的顺序。

最直接的处理方式，就是从第一本开始，一本一本向后访问。

这时真正重要的，不是书的 ISBN 或作者，而是：谁在谁前面，谁在谁后面。

把书的具体内容暂时拿掉，只保留元素之间的前后关系。

这种一前一后的逻辑关系，就是 线性表。

当“快速定位”最重要

现在读者给出一本书的 ISBN：978-7-111-68181-6，希望马上找到它。

顺序查找只能从第一本开始：先比较第 1 本，不匹配。

继续比较第 2 本，仍然不匹配。

再比较第 3 本，终于命中目标。

如果馆藏不是几本，而是 100 万本，这种逐本扫描就太慢了。

换一种思路：取 ISBN 末四位 1816，计算 H(1816)=1816 mod 7=3。

计算结果告诉我们直接检查 桶（bucket）3；这里保存的正是目标图书。

这种根据关键字（key）计算存储位置，再定位值（value）的结构，就是散列表（Hash Table）。

当查询本身变得复杂

现在读者提出：找 2020 年以后出版、数据库方向、当前可借阅的书，并按出版时间排序。

这时，一个 ISBN 已经不够了：每本书还要同时保存分类、年份、状态等多个属性。

查询也不再只是“找到一个关键字”，而是要做多条件过滤，再进行排序。

这已经不是一种单独的数据结构能够完整解决的问题。

我们需要更高层的软件系统：数据库管理系统（Database Management System，DBMS）。它内部仍会综合使用索引、B+ 树、散列表、排序等数据结构与算法。

场景三：一张城市道路网

城市里有 5 个地点 A–E，由 7 条道路连接起来。

如果每条道路都有通行能力，从 A 到 B，单位时间内最多能通过多少车流？

如果想把 A–E 五个地点都访问到，能不能做到不重复、不遗漏？

如果任务变成道路巡检，7 条路都必须走到，能不能做到每条道路恰好一次？

真实城市里道路上还有持续变化的车流。红绿灯怎样协同调度，才能让整个路网的总通行效率更高？

计算机系统里的数据结构

栈、队列、树和图会在系统软件和应用软件中反复出现。

Linux

栈、队列、树、调度

Redis

散列、跳表、压缩列表

PostgreSQL

B+ 树、排序、连接

Neo4j

图存储与路径查询

Kafka

队列、日志、分区

数据结构基本概念

数据是什么

数据是信息的载体，是能被计算机输入、识别、存储和处理的符号集合。

常见数据可以粗略分为：

  • 数值数据：int、float、复数、坐标、概率
  • 非数值数据：字符、字符串、图像、语音、图、文档

数据结构关注的不只是一个个数据项，还关注它们之间的关系和围绕这些关系设计的操作。

数据结构的三个层面

数据结构至少同时包含三件事：

  • 数据对象：有哪些元素
  • 关系：元素之间如何连接或排列
  • 操作：允许对这些元素做什么

只谈“存了哪些元素”是不够的。没有关系，就不知道如何遍历；没有操作，就不知道结构要支持什么成本。

线性结构与非线性结构

线性结构中，除首尾外，每个元素通常只有一个直接前驱和一个直接后继。

  • 线性表
  • 栈
  • 队列
  • 字符串

非线性结构中，一个元素可以连接多个元素。

  • 树
  • 堆
  • 图
  • 多路搜索树

结构分类：线性、树和图

三个视角必须分开

分析一个数据结构时，要区分三个问题：

  • 逻辑结构：从问题角度看，元素之间是什么关系
  • 物理结构：从机器角度看，元素如何存放
  • 操作实现：为了完成插入、删除、查找，需要执行哪些底层动作

同一个逻辑结构可以有多种物理实现。
同一个操作在不同实现上的代价可能完全不同。

逻辑结构、物理结构与操作

同一个线性表抽象数据类型，可以有不同物理实现。考虑一个具体任务：

  • 已有记录 S1, S2, S3, S4
  • 在逻辑位置 2 插入新记录 Sx
  • 比较数组实现和链式实现分别发生什么

关键问题是：逻辑上的一次 insert(2, Sx)，在不同物理结构中会变成哪些底层动作？

插入操作：逻辑与物理实现

数据类型

一个数据类型由两部分组成：\(\text{数据类型}=\text{值集合}+\text{操作集合}\)

例如 int：

  • 值集合：机器能表示的整数范围
  • 操作集合：+、-、*、/、%、比较等

程序语言会提供基础类型，也支持构造结构类型，例如数组、结构体、类和容器。

抽象数据类型：把使用和实现分开

抽象数据类型关注的是“能做什么”的接口，而不是“怎么做”的实现。

例如线性表抽象数据类型：

抽象数据类型示例：自然数

自然数的抽象数据类型可以只描述对象和操作，而不暴露机器内部如何表示整数。

ADT NaturalNumber
  objects: 0 到 MAXINT 的整数
  zero() -> NaturalNumber
  isZero(x) -> Boolean
  add(x, y) -> NaturalNumber
  equal(x, y) -> Boolean
  successor(x) -> NaturalNumber
  subtract(x, y) -> NaturalNumber
end

抽象数据类型是行为契约。

面向对象与抽象数据类型

面向对象把数据和操作组织进对象与类中。

  • 对象：属性值 + 操作
  • 类：具有相同属性和操作的对象模板
  • 封装：隐藏内部表示
  • 继承：复用和扩展已有抽象
  • 消息通信：对象之间通过方法调用协作

例如矩形对象可以包含左上角、右下角、边框颜色、填充颜色，并支持移动、缩放、改色等操作。

算法基本概念

算法的定义

一个算法应满足五个基本性质：

  • 输入：有零个或多个输入
  • 输出：至少产生一个结果
  • 确定性：每一步含义明确
  • 有限性：执行有限步后终止
  • 有效性：每一步都能机械地执行

程序是算法在某种语言和机器环境中的实现；算法是更抽象的计算过程。

算法和程序的区别

算法描述解决问题的步骤。程序把算法落实到具体语言、库、类型系统和运行环境中。

例如二分查找的算法思想是“每次比较中点并丢弃一半区间”。

实际程序还要处理：

  • 数组下标类型
  • 中点计算是否溢出
  • 没找到时返回什么
  • 元素类型如何比较
  • 输入是否已经有序

算法分析通常先讨论抽象过程，再检查程序实现是否忠实表达了这个过程。

选择排序：第一段算法过程

选择排序要解决的任务是：把数组从小到大排列。

它每一轮遵循同一个步骤：

  • 在未排序区间里扫描所有元素
  • 记录当前最小值的位置
  • 扫描结束后，把最小值换到未排序区间最左端
  • 已排序区间向右扩大一格

这个过程也解释了为什么选择排序需要大量比较；下一章会把比较次数精确数出来。

选择排序：扫描、记录与交换

为什么要分析算法

同一个排序问题，可以有不同算法。

如果逐个比较并选择最小值，比较次数大约为：


\[ (n-1)+(n-2)+\cdots+2+1=\frac{n(n-1)}{2} \]

这说明它的增长速度是 \(O(n^2)\)。更高效的比较排序可以达到 \(O(n\log n)\)。

算法分析至少关注：

  • 时间复杂度（time complexity）
  • 空间复杂度（space complexity）
  • 正确性
  • 边界条件

数学工具箱

算法分析会反复使用这些工具：

  • 指数和对数：描述规模增长和折半过程
  • 级数：分析多层循环和递归展开
  • 模运算：散列、循环队列、周期结构
  • 数学归纳法：证明递归和循环正确性
  • 反证法：证明不可能性或下界

本章不要求一次掌握所有细节，但要知道它们会服务于算法分析。

递归算法

递归的两条规则

递归函数必须同时满足：

  • 基本情形（base case）：存在能直接返回的终止条件
  • 规模推进（progress）：每次递归调用都更靠近终止条件

如果只有递归调用而没有终止条件，程序不会停。
如果有终止条件但调用没有靠近它，程序仍然可能不会停。

函数调用会发生什么

递归调用也是函数调用。一个没有递归的函数调用例子，可以展示栈帧（stack frame）如何保存执行现场。

关键事实：

  • 每次函数调用都会压入一个新的栈帧
  • 栈帧保存参数、局部变量、返回地址和返回值相关信息
  • 被调用函数返回时，自己的栈帧弹出
  • 调用者继续从返回地址之后执行

函数调用栈：代码与栈帧

final class CallStackDemo {
  static int g(int y) {
    int z = y + 1;
    return z * 2;
  }

  static int f(int x) {
    int total = 0;
    for (int i = 0; i < 2; i++) {
      total += g(x + i);
    }
    return total;
  }

  public static void main(String[] args) {
    int ans = f(3);
    System.out.println(ans);
  }
}
main 的栈帧保存本次调用自己的局部状态和返回位置；函数调用不会覆盖调用者，而是在栈顶增加新的执行上下文。
main 要得到 f(3) 才能完成对 ans 的赋值，因此调用者会暂停在这条语句，等被调函数返回后再从这里继续。
f 的方法头建立新的调用边界：参数 x=3 属于这一次调用，后面的局部状态都保存在同一个 f 栈帧中。
total 属于这一次 f 调用，并会跨越后面的两次 g 调用持续存在；嵌套调用结束后，f 仍要靠它保存累计结果。
i 和 total 都保存在 f 的栈帧里，所以即使中途进入 g，这一轮循环的状态也不会丢失。
f 需要 g(3) 的结果才能完成当前累加；新的 g 栈帧只负责这一子计算，f 保留原状态等待返回。
g 的方法头把实参 3 绑定为本次调用的参数 y；这个调用拥有独立栈帧，不会覆盖 f 的局部变量。
z 是 g 这次调用的局部状态，只服务于 g(3)；函数返回后它会随栈帧一起消失，真正传回调用者的是返回值。
g 已经把自己的局部计算压缩成返回值 8；这个值是调用者恢复当前表达式所需要的唯一结果。
返回值 8 交回 f 的调用点后，g 的栈帧已完成使命；控制权恢复到原来尚未完成的累加语句。
f 用返回值完成本轮累加，total=8 成为下一轮要继续维护的累计状态；这说明调用返回后，调用者会接着完成原表达式。
第一轮语句完成后才推进循环到 i=1。调用栈恢复的不只是函数名，而是调用者精确到循环位置和局部变量的完整上下文。
第二次调用 g 会创建新的栈帧；它与上一轮的 g(3) 已无共享局部状态，但仍把结果交回同一个 f 栈帧。
再次进入同一个 g 方法时，实参 4 绑定成新的 y；相同方法的两次调用因此可以拥有彼此独立的局部状态。
g(4) 有自己独立的 z=5。同一个函数被多次调用时，每次调用都拥有独立局部变量，这正是栈帧隔离状态的意义。
这一层再次把局部计算归约成一个返回值 10；调用者不需要保留 g 的局部细节，只需要它的结果。
结果 10 回到 f 后，第二个 g 栈帧也可以释放；f 恢复到第二轮尚未完成的累加。
total 从 8 更新为 18，把两次子调用的贡献合并进同一局部状态；这就是 f 最终要返回的累计结果。
当 i=2 时循环条件失败，说明所有子调用都已完成；此时 f 的局部状态已经足以产生函数结果。
f 把内部循环和两次 g 调用的细节封装成返回值 18，调用者只观察到这个函数结果。
18 交回 main 后，f 的栈帧可以释放；main 恢复到最初等待返回值的那条赋值语句。
返回值写入 ans 后，这次函数调用才真正完成了它在调用者表达式中的作用；结果从被调函数转化为调用者自己的局部状态。
赋值完成后程序继续顺序执行后续语句。函数调用栈负责保存和恢复上下文，使嵌套调用看起来仍像普通表达式的一部分。

阶乘代码

long factorial(int n) {
  if (n < 0) {
    throw new IllegalArgumentException("n must be non-negative");
  }
  if (n <= 1) {
    return 1L;
  }
  return n * factorial(n - 1);
}
factorial(n) 的契约是返回非负整数 n 的阶乘；递归体必须让参数持续减小并最终落到基例。
阶乘在这里定义在非负整数上。拒绝负数不只是输入检查：递归每次都把 n 减 1，只有从非负整数出发，这个“问题规模严格变小”的过程才保证最终到达基例，而不会无限向负数继续。
0!=1、1!=1 是递推关系的锚点，也是递归算法真正能够停下来的原因。到达这里后不再产生更小子问题，计算从“继续分解”切换到“逐层合并答案”。
n! = n × (n-1)! 把原问题变成一个规模更小、结构完全相同的子问题；当前这一层只需要记住自己的 n，等子问题返回后再完成乘法。因此共有 O(n) 层调用，时间和递归栈深度都随 n 线性增长。

阶乘递归：代码与栈帧

long factorial(int n) {
  if (n < 0) {
    throw new IllegalArgumentException("n must be non-negative");
  }
  if (n <= 1) {
    return 1L;
  }
  return n * factorial(n - 1);
}
factorial(4) 不能立刻完成 4×?：它先把 factorial(3) 作为更小的同类问题交给下一层，同时保留“回来以后还要乘 4”这件未完成的工作。递归栈保存的正是这些尚未完成的计算上下文。
factorial(3) 再把问题缩成 factorial(2)。此时外层的 4× 和这一层的 3× 都处于等待状态；栈深度因此对应“还有多少层子问题尚未返回”。
factorial(2) 继续缩到 factorial(1)。参数按 4→3→2→1 严格减小，这不仅描述执行过程，也给出了递归会终止的关键理由。
n=1 是递推链的锚点：这里已经知道答案，不再产生新的递归调用。计算从“向下分解问题”切换为“向上合并子问题结果”。
基例返回的 1 让 n=2 那层原本悬而未决的 2×factorial(1) 第一次可以完成。递归返回按后进先出的顺序展开，因此最后创建的子问题最先被解决并交回上一层。
n=2 只做本层负责的组合工作：把自己的因子 2 与子问题结果 1 相乘得到 2。每一层都不需要知道更深层怎样求解，只依赖它返回的结果。
结果 2 交回 n=3 后，n=2 这一层的任务已经完成。栈因此既记录调用历史，也保存“哪个更大的问题正在等待这个结果”。
n=3 用同一条递推规则完成 3×2=6。向上返回的过程正是在反向重建原问题：下降阶段负责缩小规模，回程阶段负责合并答案。
结果 6 再交给最外层的 n=4。返回值沿调用链反向传播，而每一层保存的局部 n 决定这一层应该怎样继续未完成的计算。
最外层终于得到子问题结果，于是完成 4×6=24。递归用相同的规则逐层缩小问题，再逐层把局部结果组合成原问题答案。
外层结果返回后，整条递推链才真正结束。对于 factorial(n)，最多同时保留约 n 个调用层，因此虽然每层只做常数次额外运算，递归仍需要 O(n) 的辅助栈空间。

Fibonacci：调用树与重复子问题

Fibonacci 代码

标准定义是：\(fib(0)=0,\quad fib(1)=1,\quad fib(n)=fib(n-1)+fib(n-2)\)

long fib(int n) {
  if (n < 0) {
    throw new IllegalArgumentException("n must be non-negative");
  }
  if (n <= 1) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}
fib(n) 按递推定义返回第 n 个 Fibonacci 数；方法体会把一个问题拆成两个更小但重叠的子问题。
负下标不在这里采用的 Fibonacci 定义域内；先拒绝它，还保证后续的 n-1、n-2 递归始终朝 0/1 靠近，而不是沿无效输入继续展开。
F(0)、F(1) 是递推关系的两个锚点。所有分支最终都必须落到这两个已知值，递归树才有可合并回原问题的叶子答案。
F(n)=F(n-1)+F(n-2) 产生两个重叠子问题；同一个 F(k) 会在不同分支被反复求解，这正是朴素递归出现指数级重复工作的根源。

Fibonacci 最佳计算方法？

前面的示例只是为了演示递归。

Fibonacci 真的该这么算吗？

  • 动态规划
  • 通项公式

汉诺塔（Tower of Hanoi）：递归分解

汉诺塔：更多盘

核心问题是：怎么通过递归把问题降维

Java语法回顾

语言复习：类、对象和访问控制

数据结构通常会被写成类或模板类。例如下面这个简单的对 int 的封装类，同时在 main 中展示如何构建和读写对象。

public class IntCell {
  private int value;

  public IntCell(int value) { this.value = value; }
  public int read() { return value; }
  public void write(int value) { this.value = value; }

  public static void main(String[] args) {
    IntCell cell = new IntCell(7);
    cell.write(11);
    System.out.println(cell.read());
  }
}
IntCell 把一个整数状态封装在对象内部，只允许通过公开操作读取或修改。
value 被封装成对象内部状态，构造器负责建立初始表示不变量。以后即使内部字段布局改变，只要对象仍能维持同一抽象语义，调用者就不需要跟着修改。
read/write 把“允许怎样观察和修改状态”固定成接口边界；验证、日志或其他约束都可以以后加入实现，而不必把这些细节泄漏给使用者。
main(…) 只负责串联示例输入与数据结构操作，不属于本页要分析的核心算法。
main 只依赖构造器和 read/write，而不直接碰字段。这正是抽象数据类型与封装的价值：客户端面向操作语义编程，实现细节可以独立演化。

泛型

数据结构通常不关心元素的具体类型，而关心元素支持哪些操作。

例如“找最大值”只需要元素能比较大小，也就是 T extends Comparable<? super T>。

static <T extends Comparable<? super T>> T findMax(List<T> values) {
  Iterator<T> iterator = values.iterator();
  if (!iterator.hasNext()) {
    throw new IllegalArgumentException("values must not be empty");
  }
  T best = iterator.next();
  while (iterator.hasNext()) {
    T candidate = iterator.next();
    if (candidate.compareTo(best) > 0) {
      best = candidate;
    }
  }
  return best;
}
findMax(…) 返回整个序列的最大元素；扫描过程中只需维护“已看前缀的最大值”这一不变量。
空列表没有“当前最大值”可初始化，所以先把这种无定义输入挡在扫描之外。
用首元素建立不变量：best 始终代表“已经看过的前缀”中的最大值。
每轮只引入一个新候选；过去被 best 压过的元素以后无需再比较。
只有更大的候选才替换 best，因此每轮结束后“前缀最大值”不变量继续成立。
循环结束时前缀就是整个列表，best 因而是全局最大值；每个元素只比较一次。

Java 泛型：从具体类型到类型参数

如果不用泛型，相似的函数往往会为不同类型重复写多份：

static int maxInt(int a, int b) {
  return a >= b ? a : b;
}

static double maxDouble(double a, double b) {
  return a >= b ? a : b;
}
maxInt(…) 返回两个候选中的较大者；算法只依赖一次比较而不改变输入。
整数版本已经包含完整算法：比较两个候选，只保留较大的那个。
maxDouble(…) 返回两个候选中的较大者；算法只依赖一次比较而不改变输入。
换成 double 后决策过程完全没变；复制实现只是在重复维护同一个算法。

泛型把“类型”也变成参数：

static <T extends Comparable<? super T>> T maxValue(T a, T b) {
  Objects.requireNonNull(a, "a");
  Objects.requireNonNull(b, "b");
  return a.compareTo(b) >= 0 ? a : b;
}
maxValue(…) 返回两个候选中的较大者；算法只依赖一次比较而不改变输入。
类型上界只要求“可比较”这一能力；非空检查则保证比较关系在运行时确实有定义。
核心仍只有一次比较与选择；泛型把这份算法从具体数值类型中抽离出来。

全课程代码会反复出现的 Java 语法

后面章节的代码会集中使用这些语言工具：

语法或库 典型写法 用途
泛型 class Stack<T>、T value 写可复用容器和算法
链接 Node<T> next 用对象引用表示链式结构和树结构连接
空引用 null 表示没有后继、孩子或根
容器类 ArrayList, LinkedList 保存顺序数据或辅助存储
类型推断 var it = ... 简化迭代器和复杂类型
比较器 Comparator<T> cmp 或 Lambda 表达式（lambda expression） 定制排序、堆和最优选择规则
可选返回 Optional<T> 表示查找可能失败
枚举 enum Tag 表达有限状态并避免名字污染

Java 引用语义（reference semantics）与对象生命周期

Java 容器以对象引用保存元素，例如 ArrayList 内部用连续数组存放元素。

ArrayList<Integer> values = new ArrayList<>();
values.add(10);
values.add(20);
values.add(1, 15);
values.remove(Integer.valueOf(10));
ArrayList 用连续槽位保存元素引用；末尾追加只扩展逻辑序列，不改变已有元素的身份。
在位置 1 插入会把后缀整体右移；顺序表的“中间插入”因此不是常数时间。
这里选择“按值删除”：先定位值 10，再收拢后缀；它与“删除下标 10”是不同的 List 操作语义。

异常处理

程序错误可以粗略分为：

  • 语法错误：编译阶段能发现
  • 运行时错误：执行时触发，例如越界、空指针、除零
  • 逻辑错误：程序能运行，但结果不符合需求

数据结构代码需要明确异常边界：

  • 空栈 pop
  • 空堆 deleteMin
  • 越界访问
  • 输入格式错误

Java 错误处理：异常与 Optional

数据结构的失败情况要明确表达。Java 中常见做法有两类：

  • 操作无法继续时抛出异常
  • 查找可能失败时返回 Optional<T>
static int pop(Deque<Integer> stack) {
  if (stack.isEmpty()) {
    throw new IllegalStateException("cannot pop from an empty stack");
  }
  return stack.pop();
}
pop(…) 必须返回并移除当前栈顶；空栈时没有合法结果，不能继续修改结构。
空栈没有“栈顶元素”，所以先把下溢变成明确异常；正常路径从此可以假设栈非空。
pop 把“取栈顶”和“删除栈顶”绑定为一次后进先出操作，返回的正是最近压入的元素。

输入输出与代码组织

课程代码应尽量把“算法核心”和“输入输出”分开。

  • 标准输入：适合在线评测和小规模测试
  • 文件输入：适合批量实验和复现实验结果
  • 标准错误：适合输出调试信息
  • 包（package）、导入和测试入口：适合组织容器类和测试代码

这样做可以让同一个数据结构脱离具体输入来源，在不同程序中复用。

顺序文件读取

顺序文件读取的模式是：打开、逐行读取、解析、处理、关闭。

static List<Integer> readIntegers(Path path) throws IOException {
  ArrayList<Integer> result = new ArrayList<>();
  try (BufferedReader reader = Files.newBufferedReader(path)) {
    String line;
    while ((line = reader.readLine()) != null) {
      String trimmed = line.trim();
      if (!trimmed.isEmpty()) {
        result.add(Integer.parseInt(trimmed));
      }
    }
  }
  return result;
}
readIntegers(…) 按文件顺序解析有效整数并返回列表；输入资源生命周期与结果列表分离。
结果容器与文件资源一起初始化；带资源的 try 语句（try-with-resources）把“读取结束就关闭”写成结构保证，不需要调用者记得清理。
逐行读取把工作集限制为“当前一行 + 已解析结果”，文件再大也不需要整份载入内存。
先规范化空白再判断空行，把格式噪声挡在整数解析之外，后续逻辑只处理有效记录。
每个有效整数立即按原顺序追加，因此输出列表保持文件中有效记录的顺序语义。
读到文件末尾（end of file，EOF）后资源自动关闭；返回的列表已与读取器生命周期解耦，可安全交给后续算法继续处理。

包、导入和异常类

大型课程代码需要稳定组织方式：

  • src/：数据结构源码目录
  • src/main/java：主程序和示例程序
  • src/test/java：测试入口
  • package ds：避免名字冲突
  • NoSuchElementException、IllegalStateException：表达容器下溢和上溢

这种组织方式把算法、输入输出和测试边界分开，使代码更容易编译、测试、复用和维护。

本章小结

  • 数据结构的核心是同时组织数据对象、关系和操作。
  • 数据对象说明“有哪些值”，关系说明“值之间怎样连接”，操作说明“允许怎样改变或查询”。
  • 面对实际场景时，先识别顺序、层级、网络、后进先出、先进先出等关系，再选择合适结构。
  • 逻辑结构、物理结构和操作实现必须分层讨论；同一种逻辑结构可以有多种存储方式。
  • 抽象数据类型用接口约束使用方式，让使用者依赖操作语义，而不是依赖内部表示。
  • 算法强调有限性、确定性、输入输出和有效步骤；程序只是算法在某种语言中的实现。
  • 递归必须同时满足基本情形与规模推进，并能用调用树和调用栈解释执行过程。
  • 泛型、异常和输入/输出边界把算法代码从具体类型、错误处理和外部数据源中解耦出来。

下载本章完整 Gradle 工程

本章习题

  • 习题 1：二进制中 1 的个数：题目：递归求非负整数二进制表示中 1 的个数。
  • 习题 2：递归求数组最大值和平均值：给定一个数组，分别用递归方法求数组最大值和平均值，并分析时间与递归栈空间复杂度。
  • 习题 3：链表长度与回文：给定单链表：用递归方法求链表长度，并说明如何判断链表保存的序列是否为回文。
  • 习题 4：组合、全排列和汉诺塔：分别说明组合选择、全排列和汉诺塔的递归分解方法；写出关键递推关系，并解释递归过程。

进入下一章

下一章会把“算法效率与资源代价”变成可计算的问题：

  • 如何从代码数出操作次数
  • 如何用大 \(O\) 记号描述增长速度
  • 如何分析循环、递归和分治
  • 如何比较不同数据结构实现的代价

从这里开始，程序不仅要能运行，还要能解释为什么正确、为什么高效。

致谢