第 1 章绪论

Introduction

为什么学习数据结构

现代软件很少只是“把数据放进去”。真正困难的是：

数据之间有什么关系
需要支持哪些操作
操作要在多大的数据规模上运行
代码如何保持正确、可维护、可复用

数据结构与算法回答的是同一个核心问题：怎样组织数据，才能让计算过程清晰而高效。

本章路线图

绪论
建立全课程语言

真实场景
问题如何抽象数据结构
D / R / Ops ADT
接口与实现分离算法
定义、正确性、复杂度递归
调用树与调用栈工程基础
泛型、异常、I/O

学习目标

完成本章后，应能回答：

为什么数据结构不只是“存数据”
如何从场景中识别线性表、树、图、栈、队列等结构
数据对象、关系、操作分别表示什么
逻辑结构、物理结构和操作实现为什么要分开讨论
ADT 如何隔离使用者和实现者
算法与程序有什么区别
递归为什么必须有 base case 和 progress
泛型、异常和 I/O 为什么是数据结构代码的工程基础

场景一：游戏搜索

一个游戏局面通常不是只对应一个下一步。

如果当前局面有 5 种合法走法，每一种走法又继续产生新的局面，那么所有可能的未来会展开成一棵树。

树结构适合回答：

从当前局面往下能走到哪些状态
哪条路径更可能获胜
搜索深度增加时，状态数量如何增长

场景二：图书目录

图书目录中的每条记录可以包含：

书名
作者
登录号
分类
出版年月

如果主要操作是按顺序浏览、插入、删除和查找，目录首先可以抽象成线性表。

线性表的核心不是“长得像表格”，而是元素之间有清晰的前后顺序。

场景三：交通路口

交通路口的难点不是单条道路，而是多条通行方向之间是否冲突。

如果两个方向不能同时放行，就可以在它们之间连一条冲突边。

这样得到的结构是图：

顶点表示通行方向
边表示冲突关系
图染色可以用来安排不同信号灯相位

这些知识会在哪里用到

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

Linux

栈、队列、树、调度

Redis

散列、跳表、压缩列表

PostgreSQL

B+ tree、排序、连接

Neo4j

图存储与路径查询

Kafka

队列、日志、分区

数据是什么

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

常见数据可以粗略分为：

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

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

数据结构的三个层面

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

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

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

线性结构与非线性结构

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

线性表
栈
队列
字符串

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

树
堆
图
多路搜索树

结构分类：线性、树和图

三个视角必须分开

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

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

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

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

同一个线性表 ADT，可以有不同物理实现。考虑一个具体任务：

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

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

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

数据类型

一个数据类型由两部分组成：\(\text{Data Type} = \text{Value Set} + \text{Operation Set}\)

例如 int：

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

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

ADT：把使用和实现分开

ADT 关注的是“能做什么”，而不是“一定怎么做”。

例如线性表 ADT 可以提供：

insert(pos, value)
remove(pos)
find(value)
size()

调用者只依赖这些操作的行为契约。内部用数组还是链表，是实现者的选择。

ADT 示例：自然数

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

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

ADT 的重点不是语法，而是行为契约。

面向对象与 ADT

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

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

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

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

数据结构通常会被写成类或模板类。

class IntCell {
public:
  explicit IntCell(int value = 0) : value_(value) {}
  int read() const { return value_; }
  void write(int value) { value_ = value; }

private:
  int value_;
};

这里 private 隐藏内部表示，public 暴露稳定接口。
这正是 ADT 思想在代码中的落点。

语言复习：对象创建与方法调用

对象把状态和操作绑定在一起。

int main() {
  IntCell cell{7};
  cell.write(42);
  std::cout << cell.read() << "\n";
}

可维护的类实现通常遵循同一风格：

构造函数建立合法初始状态
成员函数维护类不变量
测试代码放在 main 或单元测试中

算法的定义

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

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

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

算法性质：含义与反例

算法和程序的区别

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

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

实际程序还要处理：

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

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

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

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

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

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

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

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

为什么要分析算法

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

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

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

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

算法分析至少关注：

时间复杂度
空间复杂度
正确性
边界条件

数学工具箱

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

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

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

递归的两条规则

递归函数必须同时满足：

Base case：存在能直接返回的终止条件
Progress：每次递归调用都更靠近终止条件

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

函数调用会发生什么

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

关键事实：

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

函数调用栈：代码与栈帧

int g(int y) {
  int z = y + 1;
  return z * 2;
}

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

int main() {
  int ans = f(3);
}

阶乘代码

long long factorial(int n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

这里：

n <= 1 是 base case
factorial(n - 1) 是 progress
返回值沿调用栈逐层合成

阶乘递归：代码与栈帧

long long factorial(int n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

Fibonacci：调用树与重复子问题

Fibonacci 代码

标准定义是：

\[ fib(0)=0,\quad fib(1)=1,\quad fib(n)=fib(n-1)+fib(n-2) \]

long long fib(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n - 1) + fib(n - 2);
}

朴素递归直观，但会重复计算大量相同子问题。动态规划会通过保存子问题结果消除这种重复。

Hanoi 塔：递归分解

泛型为什么重要

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

例如“找最大值”只需要元素能比较大小：

template <class T>
T findMax(const std::vector<T>& a) {
  T best = a.at(0);
  for (const auto& x : a) {
    if (best < x) {
      best = x;
    }
  }
  return best;
}

这使同一份容器代码可以用于整数、字符串和自定义对象。

泛型与比较接口

泛型代码需要明确“类型必须支持什么能力”。

在 C++ 中，可以通过模板和比较器表达：

template <class T, class Compare>
T findBest(const std::vector<T>& a, Compare cmp) {
  T best = a.at(0);
  for (const auto& x : a) {
    if (cmp(best, x)) {
      best = x;
    }
  }
  return best;
}

比较器会在排序、堆、搜索树和图算法中反复出现。读泛型算法时，先找清楚元素类型和比较规则。

C++ 模板：从具体类型到类型参数

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

int maxInt(int a, int b) {
  return a < b ? b : a;
}

double maxDouble(double a, double b) {
  return a < b ? b : a;
}

这里真正变化的是类型，算法步骤并没有变化。

模板把“类型”也变成参数：

template <class T>
T maxValue(const T& a, const T& b) {
  return a < b ? b : a;
}

后面写线性表、栈、队列、堆和搜索树时，模板让同一个数据结构可以保存不同元素类型。

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

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

语法或库	典型写法	用途
模板	`template <class T>`	写可复用容器和算法
引用	`const T& value`	避免复制，并表达只读参数
指针	`Node<T>* next`	表示链式结构和树结构连接
空指针	`nullptr`	表示没有后继、孩子或根
STL 容器	`std::vector`, `std::list`	保存顺序数据或辅助存储

读代码时先判断：这个名字表示“值”、 “引用”，还是“结构之间的连接”。

C++ 语法：STL 与工程表达

这些工具让代码更接近算法意图：

语法或库	典型写法	用途
STL 适配器	`std::stack`, `std::queue`, `std::priority_queue`	表达栈、队列和优先队列
自动类型	`auto it = ...`	简化迭代器和复杂类型
比较器	`Compare cmp` 或 lambda	定制排序、堆和最优选择规则
可选返回	`std::optional<T>`	表示查找可能失败
枚举类	`enum class Tag`	表达有限状态并避免名字污染

1. 先看容器

数据放在数组、链表、栈、队列、堆，还是集合中。

2. 再看连接

指针、下标和引用说明元素之间如何到达。

3. 找比较规则

排序、堆和搜索树都依赖比较器或顺序关系。

4. 看失败路径

optional、异常和状态值说明操作何时不能完成。

C++ 值语义与对象生命周期

C++ 容器通常直接保存对象值，例如 std::vector<int> 保存的是一段连续的 int。

std::vector<int> a;
a.push_back(3);
int x = a.at(0);

std::vector<std::string> words;
words.emplace_back("tree");

读 C++ 数据结构代码时，要特别注意对象何时被创建、复制、移动和销毁：

push_back(x)：把已有对象放入容器，可能复制或移动
emplace_back(args...)：在容器内部直接构造对象
const T&：只读引用，通常用于避免不必要复制
T&&：右值引用，常用于移动资源

异常处理

程序错误可以粗略分为：

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

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

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

C++ 错误处理：异常与 optional

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

操作无法继续时抛出异常
查找可能失败时返回 std::optional<T>

int pop(std::vector<int>& data) {
  if (data.empty()) {
    throw std::underflow_error("pop from empty stack");
  }
  int value = data.back();
  data.pop_back();
  return value;
}

std::optional<int> find(const std::vector<int>& data, int key) {
  for (int x : data) if (x == key) return x;
  return std::nullopt;
}

异常适合表达违反前置条件的操作，例如空栈 pop。
optional 适合表达正常业务中的“可能没有”，例如查找失败。

输入输出与代码组织

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

标准输入：适合在线评测和小规模测试
文件输入：适合批量实验和复现实验结果
标准错误：适合输出调试信息
头文件、命名空间和测试入口：适合组织容器类和测试代码

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

顺序文件读取

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

std::ifstream fin("input.txt");
std::string line;
while (std::getline(fin, line)) {
  std::istringstream iss(line);
  int value;
  if (iss >> value) {
    process(value);
  }
}

算法函数不应直接依赖文件名。更好的做法是让 I/O 层把数据读成容器，再交给算法层。

包、命名空间和异常类

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

include/：数据结构头文件
src/：实现文件或示例程序
tests/：测试入口
namespace ds：避免名字冲突
Underflow、Overflow：表达容器下溢和上溢

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

本章小结

本章建立了全课程的基本语言：

数据结构 = 数据对象 + 关系 + 操作
逻辑结构、物理结构、操作实现要分开看
ADT 让接口与实现分离
算法需要可终止、确定、有效
复杂度分析关心增长速度
递归要能画出调用树和调用栈
泛型、异常、I/O 是可复用代码的工程基础

习题 1：二进制中 1 的个数

题目：递归求非负整数二进制表示中 1 的个数。

思路：

n == 0 时答案是 0
最低位是否为 1 由 n % 2 决定
其余位的问题变成 n / 2

习题 1：递归追踪

习题 1：代码

int countOnes(unsigned n) {
  if (n == 0) return 0;
  return countOnes(n / 2) + (n % 2);
}

复杂度：

递归深度等于二进制位数
时间复杂度：\(\Theta(\log n)\)
栈空间：\(\Theta(\log n)\)

习题 2：递归求数组最大值和平均值

数组问题常见的递归分解方式是：先解决前 n-1 个元素，再把第 n 个元素合并进去。

最大值：

int maxRange(const std::vector<int>& a, int n) {
  if (n == 1) return a[0];
  return std::max(maxRange(a, n - 1), a[n - 1]);
}

求和后再除以元素个数：

int sumRange(const std::vector<int>& a, int n) {
  if (n == 0) return 0;
  return sumRange(a, n - 1) + a[n - 1];
}

平均值为 sumRange(a, a.size()) / static_cast<double>(a.size())。