数据结构第一章绪论

本章框架

本章包含两大部分：1 数据结构（1.1 逻辑结构、1.2 存储结构）与 2 算法（2.1 时间复杂度、2.2 空间复杂度）。
程序 = 数据结构 + 算法。

1 数据结构

数据与数据元素

数据：外界信息进入计算机后，统称为数据；一般分为数值型（int, float）和非数值型（bool, char, string）。
数据元素：是数据处理的基本单位，通常作为整体处理的一个数据个体；不可再分的字段通常称为数据项。
示例：定义 Student 类（含 name、age、studentID 三个成员）并创建对象后，student 可视为一个数据元素（数据个体），student.age 是该元素的一个成员字段/数据项。

代码

class Student {
public:
    string name;      // 姓名
    int age;          // 年龄
    string studentID; // 学号
};

int main() {
    Student student{"Alice", 20, "S123456"};
    cout << student.age << endl; return 0;
}

数据结构的定义与研究内容

数据结构：一组具有特定关系的同类数据元素的集合。
数据结构的研究内容包括三方面：
- 逻辑结构：由生活经验总结而来、与计算机无关的数据间关系；
- 存储结构：逻辑关系的存储（例如：数组存储、链表存储）；
- 基本操作：对于特定的逻辑关系和存储实现，数据上定义的操作（例如：增加数据、删除数据）。
实例（图书馆书架）：每本书可视为一个数据元素；书按主题分类摆放（如文学、历史）属于集合关系（相同类别的书属于同一个集合），即逻辑结构；存储结构可用数组或链表存储书的信息；基本操作如查找某本书是否属于某个类别、查看某类别下所有书的名字。
代码实例：定义 Book 类（数据元素，含 name、publisher 与 print() 方法）；书分历史、文学两个主题，对应两个集合；存储实现用 std::vector（数组）存储（std::vector<Book> history; std::vector<Book> literature;）；操作为向集合 push_back 添加书籍并打印历史类所有书的名字。

1.1 逻辑结构

逻辑结构：指类型相同的一组元素和元素间的关系。根据关系不同，可分为四种：

类型	定义	资料举例
集合关系	不同元素除了同属于一个集合，相互间无其他关系，次序任意	水果的集合、动物的集合、颜色的集合；同班级中同学间的关系
线性关系	元素间呈现你先我后的顺序，是一种一对一的关系	一天里要上的课、排队、一段话里所有的词、大语言模型生成的 token（如 [LLM, is, based, on, next, token, prediction]）
树形关系	元素间呈现一对多的关系	公司团队架构、文件系统、大模型对话上下文；家谱中成员间关系
图关系	元素间呈现多对多的关系	社交网络、航线网络、贸易网络

前驱与后继（讲稿备注补充）：
- 线性关系中（如队列）：除了队首，每个元素有一个唯一的直接前驱元素（简称前驱）；除了队尾，每个元素有一个唯一的直接后继元素（简称后继）。
- 树形关系中：一个人可以有多个孩子，却只能有一个父亲；把父亲看作前驱、孩子看作后继，则树中每个元素可以有多个后继，除了根，每个元素有唯一的前驱。
- 图关系中：每个元素可以有多个前驱，也可以有多个后继（如上海、北京、西安三个城市中任何两个城市间都有直飞航线）。
四种关系的示意图：(a) 集合关系——若干散落节点同属一框、互不相连；(b) 线性关系——节点连成一条链；(c) 树形关系——节点呈一对多的分层分叉；(d) 图关系——节点间多对多互连成网。

定义在数据上的基本操作

操作	含义
创建	创建一个数据结构
清除	删除一个数据结构
插入（增）	向数据结构中增加一个数据元素
删除（删）	将数据结构中的一个数据元素删除
更新（改）	将数据结构中的一个数据元素的值进行修改
查找（查）	访问数据结构中的一个数据元素
遍历	访问数据结构中的每一个数据元素，且使得每个数据元素仅被访问一次

备注示例：对队列而言，建队操作、数队列中元素个数、观察队列首部是哪个元素、进队操作、出队操作、逐一访问队列中的每个元素，都是基本操作。

1.2 存储结构

什么是存储结构

数据要得到处理首先必须进入内存。内存中不仅要存储数据元素的值，还要存储元素间的关系。
任何一种数据结构基本操作的设计取决于其逻辑结构，但基本操作的实现依赖其存储结构。
元素及其关系在内存中用什么结构存储，原则是存储方式要有利于基本操作的实现。
关系的两种表示方式：在数组中，元素间的关系通常以存储空间连续性表示；在链表中，元素间的关系通常通过指针表示。
示意（一队人）：数组将"第一个人、第二个人、第三个人……"放在连续单元中；链表用箭头（指针）从一个人指向下一个人。访问第二个人的信息：数组写作 people[1].info，链表写作 people.next.next.info。
课堂类比（备注）：试卷题——数组；密室逃脱游戏——链表。

顺序存储

顺序存储：用一块连续的空间存储数据，不直接表示数据之间的关系，而是借助空间地址上的有序性存储元素间的关系（例如，用存储地址上的先后顺序表示数据之间的先后顺序）。
高级语言中，数组是地址连续的空间，有助于实现顺序结构。
数组还可表达更复杂的关系：用二维数组表示图中节点的相连关系——示例图中节点 0–1、1–2 相连，对应 graph[0][1]=1; graph[1][0]=1; graph[1][2]=1; graph[2][1]=1;，整体构成 0/1 矩阵（第 0 行 0 1 0、第 1 行 1 0 1、第 2 行 0 1 0）。
备注延伸：完全二叉树也可以通过数组方式表示。
数组的存储结构：设首地址为 a、每个数组元素占 k 个存储单元（如 int16 对应 k=16），则序号 0、1、2、…、5 的元素地址依次为 a、a+k、a+2k、a+3k、a+4k、a+5k（图中元素 a0–a3 依次存放在前四个位置），即序号为 i 的元素地址为 a+i·k。
数组中不同元素所占内存空间是连续的。
- 优点：可以直接通过序号访问（a[0], a[1] 等）。
- 缺点：① 需要预先声明数组占据的空间大小；② 需要连续的内存空间；③ 对于插入和删除的效率低。

链式存储

链式存储：不要求不同数据存储的内存空间连续，元素间的关系显式地存储在对应的空间中（例如，用链表中的指针表示元素间的关系）。典型代表：链表。
链表的存储结构：表头指针指向第一个结点；每个结点含数据（a1、a2、a3）和指针域，指针域指向下一个结点，最后一个结点的指针域为 NULL。
链表中不同元素所占内存空间是不连续的。
- 优点：① 可以动态地增加或缩短链表的长度；② 插入删除操作高效；③ 不同节点可以存储在内存的不同位置上，存储利用率更高。
- 缺点：① 无法通过序号直接访问，为了访问一个元素，需要从头遍历；② 为了存储一个元素，还需要对应消耗一个指针域的空间。
备注示例（队列的两种存储）：用数组存队列时，可让队列中元素的先后顺序和数组下标顺序一致（第一个元素存下标 0、第二个存下标 1，以此类推）；用链式结构存队列时，先声明一个结构数据类型，每个变量称作一个结点，结点含一个存储元素值的字段和一个指针字段，指针字段存储队列中下一个元素结点的地址（指向下一个结点）。

常见存储方式总结与思考

逻辑关系：集合结构、线性结构、树型结构、图型结构；操作：创建、清除、增删改查、遍历、其它；存储方式：顺序存储、链式存储、其它。
思考题：如果一个数据结构在使用时的随机查询操作极多、插入删除操作极少，应该选择数组还是链表？——依据"数组可直接通过序号访问、链表随机访问需从头遍历"，应选数组。
后续课程的基本逻辑（以树型结构为例）：① 树型结构的逻辑关系定义；② 树型结构上可以进行的操作类型；③ 树型结构用数组和链表分别如何存储、如何实现各种操作。

2 算法

算法的定义与五个特性

算法：是解决一个具体问题的方法和步骤。
算法具有 5 个特性：

特性	含义	资料中的反例/说明
确定性	每一步有确定的含义，没有二义性	"If a 比 b 大很多, then …"、"If a 是一张猫的图像, then …"
有穷性	每一步在有限的时间内完成，整个算法必须在有限步之后完成	`While True: Print("Hello World");`
可行性	每一步都是经过有限次基本操作可以完成，自身没有复杂的算法	`a=power(2, +∞);`
有输入	一个算法可以有零个或者若干个输入作为解决问题的已知条件	—
有输出	通常应有一个或若干个可观察输出（返回值、打印或状态改变等）作为算法运行结果	—

备注：无穷算法是"一种最简单的病毒"；思考——什么算法可以没有输出？有意义吗？

算法的基本要求

要求	含义
正确性	准确反映并能满足具体问题的要求（答案正确）
可读性	可供人们阅读的容易程度（详细的注释，易维护）
健壮性	对各种不同的输入都要有相应的反应（注意边界条件，特殊值）
时间效率	算法的执行时间（OJ 系统中的 Time Limit Exceed）
空间效率	算法执行期间所需要最大内存空间（OJ 中的 Memory Limit Exceed）

健壮性的形象说明——"测试工程师走进酒吧"系列笑话与其对应的测试含义（备注给出对应关系）：

笑话情形	测试类型	测试目的
要了一杯啤酒	正常功能测试	验证系统能处理标准有效输入
要了一杯咖啡	边界值测试	测试系统对菜单外项目的处理
要了 0.7 杯啤酒	无效输入测试	检查系统对小数数量（非整数）的容错
要了 -1 杯啤酒	异常输入测试	验证系统对负数的处理（应报错或拒绝）
要了 2^32 杯啤酒	压力/溢出测试	测试极大数值是否导致整数溢出或资源耗尽
要了一杯洗脚水	荒谬输入测试	检查系统对完全无意义物品的响应
要了一杯蜥蜴	无效数据类型测试	测试非饮品输入
要了一份乱码字符	安全测试（注入攻击）	检测系统是否容易受到攻击或病毒注入
什么也没要	空输入测试	验证系统对空订单的处理
从非常规路径进出	安全性/路径测试	模拟非标准操作流程，检测安全漏洞

时间效率（算法的执行时间）——影响运行时间的主要因素：① 问题的规模（数据量的大小，如 100 条数据 vs 1,000,000 条数据）；② 程序采用的算法的优劣；③ 编译器生成的目标代码的质量；④ 计算机系统的性能（AI 研究中的显卡）。其中前两项为幻灯片重点标示。

算法效率引例：二分查找 vs 从前向后查找

问题：对一个有序序列（A–Z 共 26 个字母，下标 0–25），查找字母 P 的位置。
二分查找过程：
- 第一步：从中间的字母开始找，(0+25)/2=12.5，取整得 12，对应 M；M 在 P 的前面，所以 P 仅会在 [13,25] 出现。
- 第二步：(13+25)/2=19，对应 T；T 在 P 的后面，所以 P 仅会在 [13,18] 出现。
- 第三步：(13+18)/2=15.5，取整得到 15，对应 P，成功找到。
- 仅需要三次操作就可以找到，最多需要 $\log_2(N)+1$ 次。
从前向后查找：从数组中第一个元素开始比较，A, B, C, D, E…, O, P，一共访问 16 次；最差情况下，需要访问 N=26 次。
对比结论：同样的查找操作，二分法最多需要 $\log_2 N+1$ 次访问，从前向后查找最多需要 N 次访问。当 N=10000 时，后者访问的次数是前者的 1000 倍还多。
不同时间函数的增长对比（以计算机 1 秒处理 1000 条指令估算）：

时间函数	N=20	N=50	N=100	N=500
$N$	0.02秒	0.05秒	0.1秒	0.5秒
$N\log(N)$	0.09秒	0.3秒	0.6秒	4.5秒
$N^2$	0.4秒	2.5秒	10秒	250秒
$N^3$	8秒	2分	17分	35小时
$2^N$	约17.5分钟	约 $3.6\times 10^4$ 年	约 $4.0\times 10^{19}$ 年	约 $1.0\times 10^{140}$ 年

2.1 时间复杂度

时间频度

用算法中基本语句的执行次数来度量运行时间：基本语句执行次数越多，时间花费越多，执行次数称时间频度；时间频度和处理的数据规模 n 有关，可表示为 n 的函数 T(n)。
例：

代码

s = 0;
for (i=0; i<n; i++)
    s = s + i;

s=0 执行 1 次，i=0 执行 1 次，i<n 执行 n+1 次，i++ 执行 n 次，s=s+i 执行 n 次，共计执行标准操作 3n+3 次，时间频度为 T(n)=3n+3。

度量原则：
- 循环语句：需要计算实际运行的次数，不是看语句书写的次数。
- 分支语句：按照执行语句多的那个分支计算。
分支例：

代码

if (n>0) {
  for (i=0; i<n; i++)
    cout<<i;
}
else
  cout<<"n<=0!";

n>0 时为 3n+3 次；n<=0 时为 2 次；时间频度取 3n+3。

渐进表示法：大 O 表示法

定义：如果存在常数 C 和 $n_0$ ，满足当 $n > n_0$ 时， $T(n) \le C \cdot F(n)$ ，则 $T(n)$ 可以表示为 $O(F(n))$ ，称为算法的时间复杂度。
例： $T(n)=3n+3 \le C\cdot n$ ，所以可以表示为 $O(n)$ ； $T(n)=\log_2 n + 1 \le C\cdot \log_2 n$ ，所以可以表示为 $O(\log_2 n)$ ，也可以近似写为 $O(\log n)$ 。
对数底数可略去的依据是换底公式（备注提示）。
时间复杂度由时间频度函数中的最高次项决定，不带系数。

时间复杂度的计算

两条简化规则：① 执行次数和数据规模 n 的变化没有关系的语句，可不计入；② 当内外循环次数没有关联时，只需要看循环体的执行次数即可。
例（内外循环无关联）：

代码

s=0;
for (i=0; i<n; i++)
    for (j=0; j<n; j++)
        { s=s+i+j;   cout<<s; }

只需计算循环体执行次数 $\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} 1 = \sum_{i=0}^{n-1} n = n^2$ ，时间复杂性为 $O(n^2)$ 。

例（内外循环次数相互关联）：

代码

s=0;
for (i=0; i<n; i++)
    for (j=0; j<i; j++)
        { s=s+i+j;   cout<<s; }

循环体执行次数： $\sum_{i=0}^{n-1}\sum_{j=0}^{i-1} 1 = \sum_{i=0}^{n-1} i = n(n-1)/2$ ，故时间复杂度 $O(n^2)$ 。

计算方法总结：
1. 找算法中和数据规模 n 有关的循环语句，计算循环体的执行次数获得时间频度函数。
2. 观察时间频度函数中关于 n 的最高次项，去掉其系数，即是时间复杂度的大 O 表示。
特殊地：如果算法中无执行次数和数据规模 n 相关的语句，即时间频度函数是一个常量，则时间复杂度为 O(1)。

常见算法的时间复杂度

常见量阶（按时间效率由高到低排列）：常量阶 $O(1)$ 、对数阶 $O(\log_2 n)$ 、线性阶 $O(n)$ 、线性对数阶 $O(n\log_2 n)$ 、平方阶 $O(n^2)$ 、立方阶 $O(n^3)$ 、幂阶 $O(2^n)$ 、阶乘阶 $O(n!)$ 、N 幂阶 $O(n^N)$ 。注意：不仅限于这几种。
到达立方阶之后，一旦数据规模大些，时间就已经是不能忍受了，是一个顽性算法；从常量级到平方级，通常称易性算法。
增长曲线图：横轴为规模、纵轴为耗时，O(1) 与 O(log n) 几乎水平，O(n)、O(n log n) 平缓上升，O(x²)、O(x³)、O(2ˣ)、O(n!) 依次陡峭爆炸式上升。

计算时间复杂度的简化工具：两个定理

求和定理：假定 $T_1(n)$ $T_{1} (n)$ 、 $T_2(n)$ $T_{2} (n)$ 是程序 P1、P2 的运行时间，并且 $T_1(n)$ $T_{1} (n)$ 是 $O(f(n))$ $O (f (n))$ 的，而 $T_2(n)$ $T_{2} (n)$ 是 $O(g(n))$ $O (g (n))$ 的。那么，先运行 P1、再运行 P2 的总的运行时间是： $T_1(n)+T_2(n)=O(\mathrm{MAX}(f(n), g(n)))$ $T_{1} (n) + T_{2} (n) = O (MAX (f (n), g (n)))$ 。
- 例：第一段 for (i=0; i<n; i++) a[i]=0;，第二段为双重循环 for (i...) for (j...) a[i]=i+j;，按照求和定理为 $O(\max(n, n^2))=O(n^2)$ 。
求积定理：如果 $T_1(n)$ $T_{1} (n)$ 和 $T_2(n)$ $T_{2} (n)$ 分别是 $O(f(n))$ $O (f (n))$ 和 $O(g(n))$ $O (g (n))$ 的，那么 $T_1(n)\times T_2(n)$ $T_{1} (n) \times T_{2} (n)$ 是 $O(f(n)\times g(n))$ $O (f (n) \times g (n))$ 的。
- 例：双重 n 次循环按照求积定理为 $O(n\times n)=O(n^2)$ 。
当内外循环次数相互关联时，也可利用求积公式简化：外层 for (i=0; i<n; i++) 为 $O(n)$ ，内层 for (j=0; j<i; j++) 最坏是 i=n 时为 $O(n)$ ，按照求积公式，时间复杂度为 $O(n\cdot n)=O(n^2)$ 。

量阶与三种情况

$O(f(n))$ 并不描述运行时间的精确值，只给出一个数量级。它表示：当问题规模很大时，算法运行时间的增长受限于哪一个数量级的函数，简称为量阶。
通常考虑三个方面：最好、最坏和平均情况的时间复杂度；一般用最坏情况作为算法的时间复杂度。
备注类比：考虑最坏情况，就像上课需要照顾没有任何基础的同学。

2.2 空间复杂度

算法的空间消耗包括三个方面：① 实现算法的程序本身需要占据存储空间；② 待处理的数据需要在内存中存储，占据一定的空间；③ 处理数据的过程中需要一些额外的辅助空间。通常一和二是不可避免的，在设计算法时主要关注额外的辅助空间。
渐进空间复杂度（也称空间复杂度）：是当数据规模 n 趋于无穷时使用辅助空间的量阶，计为 $S(n)=O(f(n))$ 。
示例（数据序列逆置）——方法一，借助辅助数组：

代码

int a[10]={1,6,2,5,8,9,5,4,3,12},b[10];
int i;
for (i=0; i<10; i++)
    b[i] = a[10-i-1];
for (i=0; i<10; i++)
    a[i] = b[i];

为完成 n=10 个元素的逆置，使用了具有 n 个元素空间的数组 b 作为辅助空间，空间复杂度为 O(n)。

方法二，原地交换：

代码

int a[10]={1,6,2,5,8,9,5,4,3,12};
int t, i;
for (i=0; i<5; i++)
{   t=a[i];
    a[i]=a[10-i-1];
    a[10-i-1]=t;
}

使用的辅助空间为一个临时变量 t，辅助空间数量和元素个数没有关系，故其空间复杂度为 O(1)。

延伸：无需临时变量的两数交换的四种方案：

代码

// 方案一（加减）          // 方案二（乘除）
a = a + b;                a = a * b;
b = a - b;                b = a / b;
a = a - b;                a = a / b;

// 方案三（异或）
a = a ^ b;
b = a ^ b;
a = a ^ b;
// 不建议写成链式 a ^= b ^= a ^= b;

代码

# 方案四（Python）
a, b = b, a

注意：加减和乘除方案可能溢出；乘除方案还要求参与除法时除数非 0；异或方案只适用于整数，且链式 a ^= b ^= a ^= b 在旧 C/C++ 标准中有求值顺序风险，复习时以三行写法为准。
说明：在内存足够大的情况下，算法更加注重时间效率，忽略空间复杂度的计算；或者仅当算法的时间复杂度一致的情况下，才可能比较空间复杂度的优劣。

延伸：时间与空间的相互转换

用空间换时间——哈希算法：把任意长度的输入通过散列算法变换成键值（例如位置编号），该输出就是散列值。为了降低"哈希冲突"（两个数据算出同一个位置），哈希表必须保持大量空位（浪费空间）来保证运转效率。
- 示意图：Keys（152、104、212）经哈希函数 $h(x)=x \bmod 10$ 映射到哈希表位置；152 与 212 求模后落在同一位置，图中标红为 Collision（冲突）。
- 备注：哈希表常用于集合/字典类数据的快速查找；不应理解为只能用于“集合关系”。
用时间换空间——操作系统的虚拟内存：操作系统会把硬盘划出一部分，假装它是内存来用，把当前不常用的数据悄悄移到硬盘上，腾出真正的内存给急需的程序。硬盘的读写速度比真实的内存慢成百上千倍，当程序突然需要用到被放进硬盘的数据时，系统必须花费大量时间去硬盘里把它"搬"回内存——这就是为什么内存不够时电脑会变得非常卡顿：系统在用卡顿（时间）来弥补内存不足（空间）。
- 示意图：Physical RAM（Fast, Limited Space）与 Hard Disk / Swap Space（Slow, Huge Space）之间通过 Swap Out（Free up space）与 Swap In（Time Penalty）交换页面。

本章小结

数据元素及元素间关系称作数据结构。
数据结构研究具有某种制约关系的一组元素及元素间关系在内存中如何存储、在各种存储方式下关系操作如何实现，以及各种数据结构的典型应用。
具体研究分逻辑结构及基本操作、物理结构、基本操作实现、典型应用四个方面。
在分析逻辑结构和基本操作时，要完全脱离计算机而仅仅依赖现实生活中的元素特征来分析元素、元素关系及基本操作，最后给出用伪代码描述的抽象数据类型。
在物理结构分析阶段，讨论元素及元素关系在内存中如何存储。存储可以分顺序存储和链式存储：顺序存储使用一块连续的空间存储元素和元素之间的关系；链式存储使用各自独立的空间存储每个元素，并在每个独立的空间中附加字段以存储元素之间关系。
在基本操作实现分析阶段，研究在各种存储方式下基本操作的实现方法和步骤即算法。对于算法提出了时间复杂度和空间复杂度的概念及计算方法，并以此为依据，对不同算法进行性能比较。
在典型应用阶段，给出所研究的数据结构最适合的实际应用问题。

数据结构 第一章 绪论