概论

1. 导学：课程位置与知识地图

对应课件第 1–3 页。

数据结构研究数据在计算机中的组织方式，以及建立在这种组织方式上的运算如何实现。它回答两个问题：现实对象怎样表示成计算机能够存储和处理的形式；同一问题的不同解法为什么在时间与空间上相差悬殊。这两个问题贯穿课程始终。

本课程先建立数据、数据元素、数据对象等概念，再讨论元素之间的逻辑关系，即逻辑结构；随后讨论逻辑结构在存储器中的实现，即存储结构；在此基础上给出抽象数据类型的描述方法；最后讨论算法的特性、设计目标与复杂度分析。线性表、栈、队列、树与图将在后续各章按这一框架展开。

学习时应把定义与实现分开：逻辑结构回答元素之间是什么关系，存储结构回答关系在内存中怎样保存，操作回答允许对数据做什么。

2. 从现实问题到计算机表示

对应课件第 4–9 页。

课件用三个场景说明数据结构的作用。城市交通管理要记录车辆、道路与路口，计算路况并规划路线；民航运输要管理飞机与航班，安排飞行计划并进行空中交通管制；社交网络要表示用户之间的好友关系，并完成推荐与查询。三者对象不同，任务却相同：把现实中的对象及对象间的关系抽取成计算机可以保存和计算的形式。城市交通关注路口与路段的连接，民航关注航班与机场的衔接，社交网络关注用户之间的好友关系。

这些例子揭示两个根本问题。第一是表示问题：对象及其联系如何转化为计算机中的数据和关系。第二是计算问题：在给定表示上如何设计算法完成查询、插入、删除、优化，并使代价可以接受。数据结构解决第一个问题，算法分析解决第二个问题。仅仅把数据存进计算机并不等于完成表示，还必须保存对求解有用的关系；仅仅写出能运行的步骤也不等于解决计算问题，还必须说明规模增大时是否仍然可用。

Wirth 在 1976 年将其著作命名为《算法 + 数据结构 = 程序》，概括了这种关系：数据结构提供问题的静态模型，算法给出在这个模型上求解的动态过程。数据结构是操作系统、数据库、编译原理、人工智能等后续课程的直接基础，既训练抽象建模能力，也训练对程序效率进行定量分析的能力。

3. 数据、数据元素、数据项与数据对象

对应课件第 10–18 页。

数据是对客观事物的符号表示，是程序加工的原料。它可以是数值，也可以是非数值：整数、实数、字符、图像、声音都可以作为数据。进入计算机后都要表示成二进制位串，但数据结构讨论的重点不是编码细节，而是数据元素及其关系。

数据元素是数据的基本单位，通常作为一个整体参与处理。它可以是一条学生成绩记录、一张扑克牌、一个整数，也可以是更复杂的对象。数据元素并不等于不可再分的最小单位，它是否继续分解，取决于当前问题的处理粒度。

数据项是数据元素中具有独立含义的最小单位。以学生成绩记录为例，姓名、学号、课程名、成绩都是数据项；以扑克牌为例，花色和点数是数据项。数据项在逻辑上被视为不可再分，但在别的问题中它本身又可能是复合的，例如“出生日期”可以继续拆成年、月、日。

数据对象是性质相同的数据元素的集合，是数据的一个子集。整数对象是全体整数的集合，字符对象是全体字符的集合，全校学生记录构成学生对象。数据对象只强调“同类元素的集合”，还没有规定元素之间除同属一类之外的任何关系，因此是构造数据结构的原料。

四个概念构成由粗到细的层次：数据是总称，数据对象是同类数据元素的集合，数据元素是集合中的个体，数据项是元素内部的单位。划分是相对的：关心整张牌时，牌是元素、花色与点数是数据项；只关心花色分布时，花色本身也可当作元素。粒度是否合适，标准是能否支持当前问题的操作。

4. 数据结构的定义：元素、关系与操作

对应课件第 19–21 页。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。若用 D 表示数据元素集合、S 表示 D 上关系的集合，则数据结构可记为二元组 (D, S)；教材对数据结构采用这一口径，逻辑结构与存储结构分别是在抽象层次与物理层次上说明 (D, S)。若再把定义在其上的一组基本操作 P 纳入描述，得到抽象数据类型，记作三元组 (D, S, P)。操作属于 ADT 的定义，不是数据结构二元组的第三项；研究数据结构时总要结合操作与算法，但定义层面应区分二者。

逻辑结构是数据元素之间的抽象关系，不依赖编程语言和存储器，只回答“哪些元素相关、以什么方式相关”。例如把路口抽象成顶点、道路抽象成边，得到图状结构。存储结构又称物理结构，是逻辑结构在存储器中的表示，必须同时解决元素的值存在哪里、元素之间的关系怎样保存。顺序存储用相邻单元隐式表示关系，链式存储用指针显式表示关系。

逻辑结构是抽象建模的第一步，存储结构是实现的第一步。同一个逻辑结构可以有多种存储结构，例如线性表既可用数组实现，也可用链表实现；同一个存储结构也可承载不同的逻辑结构，例如数组既可表示线性表，也可作为完全二叉树的顺序存储。存储结构的选择直接影响操作的时间与空间代价，“逻辑结构相同”并不意味着“效率相同”。

(D, S) 描述数据对象在某一时刻的形态，而 ADT 中的操作 P 描述它随时间的变化。以栈为例，它仍是线性结构，但“只能在栈顶插入和删除”的限制使它区别于普通线性表；限制由逻辑定义给出，不是存储方式带来的。

5. 逻辑结构的四种类型

对应课件第 22–25 页。

若把元素间的关系看成有序对的集合 S ⊆ D × D，则可根据有序对的结构把逻辑结构分为四类。分类只看关系本身，不看元素的值与存储方式。

集合结构中，元素之间除“同属一个集合”外没有其他关系，S 为空。整数集合、字符集合都是集合结构。它是最弱的结构，通常不单独设章，但“判定元素是否属于集合”是许多算法的基础问题。

线性结构中，元素之间存在一对一的次序关系：除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。学生按学号排成的表、排队等候的队列、相连的列车车厢都是线性结构。栈和队列也是线性结构，只是对插入、删除的位置加了额外限制。

树形结构中，元素之间存在一对多的层次关系：除根结点外，每个结点有且仅有一个直接前驱（双亲），一个结点可以有零个或多个直接后继（孩子）。家谱、文件目录、组织机构图都是树形结构，适合表示分类与包含关系。

图状结构中，元素之间存在多对多的任意关系，任意两个元素之间都可能有边，边可带方向与权值。社交网络的好友关系、城市交通网络的道路、课程的先修关系都是图状结构。图是最一般的结构，线性结构与树形结构都可看成图的特例。

线性、树形、图状结构都可用有序对描述邻接关系，常被统称为有序对结构；集合结构没有这种有序对。四类的复杂程度依次递增，但复杂不等于高级，选择取决于问题中真实存在的关系与需要支持的操作。它们依次对应本课程第 2–4 章、第 5 章与第 6 章。

同一批数据也可以有不同的逻辑结构。学生记录按学号排成表是线性结构，按“学校—学院—专业—班级”组织是树形结构，再记录选课关系则得到图状结构。设计的首要任务是从问题中辨认真正有用的关系，而不是把所有关系都塞进模型。

6. 物理存储的基本方式

对应课件第 26–30 页；索引与散列两种存储另见第 63–67 页小结。

顺序存储把逻辑上相邻的元素存放在物理地址相邻的单元中，关系由地址连续性隐式表示。设元素占 c 个单元、首地址为 base，则第 i 个元素（从 0 编号）的地址为 base + i × c，因此可随机访问：给出下标即可在常数时间内存取，记 O(1)。代价是插删需移动元素，最坏移动 n 个，记 O(n)；空间通常预先分配，不足时扩容搬迁，存储密度较高。

链式存储把元素存放在任意位置的结点中，结点除数据域外还保存指向后继（或前驱）的指针，逻辑关系由指针显式表示，物理上不必相邻。按序号访问须从表头沿指针查找，最坏走过 n 个结点，记 O(n)；已知前驱或插入位置时，插删只需修改常数个指针，记 O(1)。它按需申请结点、规模灵活，但需额外指针空间，存储密度较低。

顺序存储适合数组、顺序表、栈、队列与堆，链式存储适合链表、树的孩子表示与图的邻接表。二者的选择可概括为：逻辑关系用地址隐式表示还是用指针显式表示，决定了随机访问与插删效率的互补。

课件第 63–67 页小结把存储概括为顺序、链式、索引、散列四类。索引另建关键字与地址的索引表，散列由关键字直接计算地址、平均接近 O(1) 但须处理冲突。这里只需知道存储不止顺序与链式两种。

选择存储方式看操作频率与规模变化：以下标随机访问、查找多而插删少、规模稳定者宜顺序存储；插删频繁、规模变化大、操作多在已知位置附近者宜链式存储。实际系统常把两者结合，如顺序表加索引、链表加尾指针。

上述复杂度都有前提：O(1) 随机访问以元素等长、地址可计算为前提；链式存储的 O(1) 插入以已定位前驱为前提，若还须按序号查找，总代价仍是 O(n)。第 2 章将约定单链表带头结点，其数据域不使用，指向首元结点，便于统一表头与表中的插删。

7. 数据类型与抽象数据类型

对应课件第 31–33 页。

数据类型是一组性质相同的值的集合，以及定义在这组值上的一组操作的总称。它规定变量可以取哪些值、可以进行哪些运算。例如 C 语言的 int 类型规定整数的表示范围（常见实现为 [-2³¹, 2³¹−1]）以及加、减、乘、除、取模等操作。数据类型可分为基本类型（原子类型）和结构类型：前者不可再分，后者由基本类型按某种方式组合而成。

抽象数据类型（ADT）是用户定义的、用于表示应用问题的数据模型，以及定义在该模型上的一组操作。它只描述数据对象是什么、元素之间是什么关系、允许执行哪些操作、每个操作的效果是什么，不规定数据如何存放，也不规定操作如何实现。ADT 最重要的性质是抽象：使用与实现分离，封装与信息隐藏。使用者只需了解外部视图，即类型名称、数据对象说明和操作语义；实现者才关心内部视图，即存储结构与算法细节。

ADT 是概念层次的模型，类是实现 ADT 的一种常用机制：私有数据成员对应内部视图，公有成员函数对应操作接口。但 ADT 不等同于类：它可用结构体加函数实现，也可用其他语言实现。同一个 ADT 可有多种表示，例如复数既可用直角坐标，也可用极坐标，只要外部语义不变。

8. ADT 的表示格式与操作约定

对应课件第 34–35 页。

课件用三元组 (D, S, P) 描述 ADT：D 是数据对象，S 是 D 上关系的集合，P 是基本操作集合；其中的 (D, S) 就是第 4 节的数据结构二元组，ADT 在此基础上增加操作。书写格式通常为：

ADT 名称 {
    数据对象：D = { ... }            // 元素的取值范围与性质
    数据关系：S = { ... }            // 元素之间的逻辑关系
    基本操作：P = { ... }            // 操作名、参数、初始条件、操作结果
} ADT 名称

每个操作的规格包含三部分：操作名与参数表、初始条件、操作结果。初始条件说明调用前必须满足的前提；操作结果说明前提满足时数据对象与返回值的变化。若初始条件不满足，操作应失败并返回出错信息，而不应继续执行产生无意义的结果。

按对数据对象的影响，基本操作分为三类：初始化与销毁类，如 Init、Destroy、Clear；访问型操作，如查询、读取、遍历，只读而不改变数据对象状态；加工型操作，如插入、删除、修改，会改变数据对象状态。分类标准是“是否改变数据对象”，不是“是否返回值”。

本课程以类 C/C++ 伪代码为主，接口与代码片段采用 C 风格：结构体、指针与状态返回值，不把 C++ 引用当作 C 语法，也不要求代码可原样编译。需先说明三个约定。第一，状态返回值：统一用 typedef int Status; 表示操作状态，约定 OK 为 1、ERROR 为 0、OVERFLOW 为 −1；失败时返回相应状态，数据结果通过参数带回。第二，参数方向：赋值参数按值传递，修改形参不影响实参；需要写回的输出或输入输出参数用指针传递，调用时对实参变量取地址，函数内通过 *p、p->成员 写回。第三，位序与下标：ADT 位置采用位序，从 1 开始，范围 1..n；C 数组下标从 0 开始，范围 0..n-1，ADT 的“第 i 个元素”对应 A[i-1]。后续线性表、栈、队列的 ADT 均按位序描述，代码按下标实现，阅读时必须区分。栈、队列的具体指针约定（动态顺序栈 pTop 指向下一空位，共享数组双端栈的 top 直接表示元素下标，循环队列 front 指队首、rear 指下一空位）将在第 3 章结合实现明确，不能混用。

参数表里写 T &x 是 C++ 引用，不是 C 语法；本课程统一改用 T *x，并在调用处写 &x（取地址）。看到 & 时要根据位置判断：出现在调用实参前是取地址，出现在类型后则是 C++ 引用——本课程代码不使用后一种写法。关键是理解参数方向：只读用值参数，需要写回用指针参数，调用者负责取地址，被调函数负责解引用。

9. 复数 ADT：从定义到 C 风格实现

对应课件第 36–42 页。

课件以复数为例给出完整的 ADT 定义与实现。复数由实部和虚部组成，可写成 a + bi，其中 a、b 为实数。按课件第 36–37 页的分量模型，数据对象是一个个复数，每个复数由实部与虚部两个实数分量构成；若把内部表示写成有序对 (a, b)，则：

D = { (a, b) | a, b ∈ Real }          // 对象集合：每个复数由两个实数分量组成
S = { <a, b> | a 是实部、b 是虚部 }    // 同一对象内两个分量的角色与次序

这里 D 的元素是“复数对象”，S 约束的是同一对象内两个分量之间的关系；(a, b) 与 <a, b> 都是内部表示层面的记法。对外部使用者，复数仍是一个整体值，只能通过操作观察它；分量的区分属于实现细节，不能把两个分量当成两个独立的数据对象。基本操作包括初始化与销毁、读取实部与虚部、打印、修改实部、修改虚部、加法与减法；其中初始化、销毁和修改类操作需要写回，读取与打印只读。

对应的 C 风格实现如下。结构体保存两个 double 成员，Status 统一表示操作状态。

typedef double ElemType;

typedef struct {
    ElemType real;        /* 实部 */
    ElemType imaginary;   /* 虚部 */
} ComplexNumber;

typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1

Status InitComplex(ComplexNumber *Z, ElemType a, ElemType b) {
    Z->real = a;
    Z->imaginary = b;
    return OK;
}

Status DestroyComplex(ComplexNumber *Z) {
    Z->real = 0.0;
    Z->imaginary = 0.0;
    return OK;
}

Status GetComplex(ComplexNumber Z, ElemType *a, ElemType *b) {
    *a = Z.real;
    *b = Z.imaginary;
    return OK;
}

Status PrintComplex(ComplexNumber Z) {
    printf("(%.2f, %.2f)\n", Z.real, Z.imaginary);
    return OK;
}

Status PutReal(ComplexNumber *Z, ElemType a) {
    Z->real = a;
    return OK;
}

Status PutImaginary(ComplexNumber *Z, ElemType b) {
    Z->imaginary = b;
    return OK;
}

Status AddComplex(ComplexNumber *Z, ComplexNumber X, ComplexNumber Y) {
    Z->real = X.real + Y.real;
    Z->imaginary = X.imaginary + Y.imaginary;
    return OK;
}

Status SubComplex(ComplexNumber *Z, ComplexNumber X, ComplexNumber Y) {
    Z->real = X.real - Y.real;
    Z->imaginary = X.imaginary - Y.imaginary;
    return OK;
}

调用这些操作时，输出参数要对实参取地址：

ComplexNumber z;
ElemType re, im;

InitComplex(&z, 1.0, 2.0);        /* 写回 z */
GetComplex(z, &re, &im);          /* 读取分量到 re、im */
AddComplex(&z, z, z);             /* 写回 z */

这段实现有几处值得体会。第一，InitComplex 的 Z 必须用指针参数，调用时取地址；若按值传递，初始化的只是副本，调用者的复数仍未设置。第二，GetComplex 的 Z 用值参数表示只读，a、b 用指针参数，因为函数只有一个返回值，无法同时带回两个分量；调用时写 GetComplex(z, &re, &im)。第三，AddComplex 的 X、Y 只读，Z 需写回，因此 Z 用指针。参数方向精确表达了操作对数据的影响，不能随意选择。

第四，DestroyComplex 在静态存储下只是清零，存储随作用域结束自动回收；若实现中使用了动态申请的资源，Destroy 就必须释放，否则造成内存泄漏。ADT 只规定“销毁后对象不可用”，具体怎样销毁由实现决定。第五，统一用 Status 返回状态，使不同操作有一致的错误处理方式；本例通常只返回 OK，接口仍保留状态返回值，便于扩展。

从 ADT 角度看，使用者只需知道复数是两个实数组成的有序对，支持初始化、读取、修改、加减，不需要知道内部是结构体还是两个分离变量。若把内部表示改成极坐标，只要外部语义不变，使用者代码就不必修改。这正是抽象与信息隐藏的价值。

10. 算法的定义及其与数据结构的关系

对应课件第 43–44 页。

算法是对特定问题求解步骤的描述，是指令的有限序列。每条指令表示一个或多个操作，整个序列在有限步内结束并产生结果。算法与程序不同：算法是解决问题的方法与步骤，独立于具体语言；程序是算法在某种语言中的实现，还受语法、运行环境与工程约束影响。同一个算法可以用不同语言实现。

算法与数据结构的关系可概括为：数据结构为算法提供操作对象和操作集合，算法在数据结构上完成求解；结构的选择决定算法能利用哪些性质，算法的需求又反过来决定结构应提供哪些操作。以查找为例，在无序数组中查找只能逐个比较，最坏需要 n 次；在有序数组中可利用有序性进行二分查找，最坏只需约 log₂ n 次。但二分查找要求能随机访问中间元素；若把同样的有序数据放在链表中，虽然逻辑上有序，却无法在 O(1) 时间内定位中点，二分查找的优势便无法直接实现。可见算法好坏不能脱离数据组织方式评价。

课件用 Wirth 的名言概括这种关系，并指出数据结构与算法密切相关、不可分离：结构的优劣要通过实现其操作的算法来体现，算法的效率又依赖结构提供的访问方式。学习数据结构不能只画结构图，也不能只背算法代码，而要把“结构—操作—代价”作为整体分析。

11. 算法的五个特性

对应课件第 45–47 页。

一个算法必须同时满足五个特性，缺一不可。

有穷性：算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成。循环必须有终止条件，递归必须有终止条件并保证问题规模向终止条件靠近。有穷性不等于实用性：需要执行 2¹⁰⁰ 步的算法在理论上有穷，实际却无法在可接受时间内完成。

确定性：每条指令必须有确切含义，不能有二义性；相同输入必须产生相同输出，并走相同的执行路径。诸如“取一个合适的初值”“随机选择一个数”这样的描述，若不把随机源纳入输入或明确约定，就破坏了确定性。

可行性：算法中的操作必须能由已经实现的基本运算执行有限次来完成。不能把“求解一个困难问题”直接当作一条基本指令，每一步都应分解为计算机可以执行的基本操作。

输入：算法有零个、一个或多个输入，输入取自特定的对象集合。输入为零是允许的，例如输出固定常量的算法不需要输入，但输入必须有明确的类型与范围。

输出：算法至少有一个输出，输出与输入之间存在确定的对应关系。没有输出的步骤序列无法称为算法，因为无法判断它解决了什么问题。

课件用有序序列查找说明不同算法的差异：穷举查找逐个比较，最坏比较 n 次；二分查找每次把候选区间缩小一半，最坏比较次数约为 log₂ n。两者都满足五个特性，但效率相差一个数量级。正确性只是基本要求，效率分析才是本章后半部分的重点。

12. 算法设计的目标与正确性层次

对应课件第 48–51 页。

算法设计通常追求四个目标：正确性、可读性、健壮性和高效性。四者可能冲突，工程中需要权衡，但正确性始终优先。

正确性要求算法对合法输入给出符合规格的结果。课件把正确性分为四个层次：第一层是语法正确、能够运行；第二层是对常规输入得到满足规格的结果；第三层是对精心选择的苛刻数据（包括边界数据）也能得到正确结果；第四层是对一切合法输入都能证明正确。本课程要求达到第三层，即通过系统测试覆盖常规与边界情形；第四层需要形式化证明，成本较高，通常只在关键系统中采用。

可读性要求结构清晰、命名有意义、逻辑易于理解。程序不仅给机器执行，也供人阅读与维护；过度追求技巧会增加维护成本。

健壮性要求对非法输入适当处理，如返回错误状态、给出明确提示，而不是打印错误后中止。无法处理的输入应明确拒绝，并保持数据对象处于可接受状态。

高效性要求占用较少的执行时间与存储空间。规模较小时差异可能不明显，规模增大后低效算法可能完全不可用。提高效率常“以空间换时间”，如预建索引、缓存、散列表；也可压缩存储、按需计算。选择取决于系统对时间、空间与实现复杂度的约束。

13. 复杂度度量：时间、空间与语句频度

对应课件第 52–54 页。

算法的效率不能直接用运行秒数比较，因为运行时间依赖机器速度、编译器和语言。为刻画算法本身的代价，我们统计基本操作的执行次数，作为时间复杂度的度量。

时间复杂度 T(n) 表示规模为 n 时基本操作的次数，主要取决于算法策略（最关键）、问题规模 n、语言与编译质量、机器速度。后两者只影响常数因子，前两者决定增长阶。分析时只统计执行最频繁的语句，称为基本操作或原操作，其重复次数与总时间成正比。

空间复杂度 S(n) 表示规模为 n 时所需存储空间，包括指令、常数与变量、输入数据及辅助空间。通常只关心随 n 增长的辅助空间；若额外空间相对输入为常数，则称原地工作，记 S(n) = O(1)。它不是不使用空间，而是额外空间不随 n 增长。

课件例 1.3 统计方阵按行求和并取最大值。设矩阵为 n × n。行和可能全为负数，因此 max_sum 的初值不能无条件取 0；下面先用首行行和初始化，并检查 n 的合法范围。代码与频度如下：

#define MAXN 100
typedef double ElemType;
typedef int Status;

Status MaxRowSum(ElemType A[][MAXN], int n, ElemType *max_sum) {
    if (n <= 0 || n > MAXN)               /* 1 次 */
        return ERROR;
    *max_sum = 0;                         /* 1 次 */
    for (int j = 0; j < n; j++)           /* 判断 n+1 次 */
        *max_sum += A[0][j];              /* n 次：首行行和作初值 */
    for (int i = 1; i < n; i++) {         /* 判断 n 次 */
        ElemType sum = 0;                 /* n−1 次 */
        for (int j = 0; j < n; j++)       /* 判断 n²−1 次 */
            sum += A[i][j];               /* n²−n 次 */
        if (sum > *max_sum)               /* n−1 次 */
            *max_sum = sum;               /* 最多 n−1 次，未计入下表 */
    }
    return OK;                            /* 1 次 */
}

其中 sum += A[i][j] 执行 n² − n 次，*max_sum += A[0][j] 执行 n 次，最频繁的仍是内层累加，故作为基本操作有 T(n) = n²，忽略常数与低次项得 O(n²)。if 成立时的赋值最多执行 n−1 次，不改变最高次项。若 n ≤ 0 或 n > MAXN，函数返回 ERROR，调用者不得再使用 max_sum。语句频度的数值随统计口径变化，增长阶则稳定；这段代码对全负矩阵同样正确，例如 1 × 1 矩阵的元素为 −3 时返回 −3，而不是 0。

14. 大 O 记法与常见增长阶

对应课件第 55–57 页。

精确的 T(n) 往往含常数因子与低次项，不同机器上的实际时间也不同。为抓住主要矛盾，我们比较函数在 n 趋于无穷时的增长趋势，使用渐近记号。

定义：设 f(n)、g(n) 是定义在正整数上的非负函数。若存在正常数 c 和 n₀，使得对所有 n ≥ n₀ 都有

f(n) ≤ c · g(n)

则称 f(n) 的阶不超过 g(n) 的阶，记作 f(n) = O(g(n))。O(g(n)) 给出渐近上界：n 足够大时，f(n) 不超过 g(n) 的某个常数倍。

以例 1.3 的 T(n) = 2n² + 4n + 1 为例。当 n ≥ 1 时，2n² + 4n + 1 ≤ 7n²，取 c = 7、n₀ = 1 即得 O(n²)；当 n ≥ 5 时不超过 3n²，取 c = 3、n₀ = 5 也可。两种取法都合法，说明大 O 界不唯一，习惯取简单而紧的上界。

大 O 忽略常数因子：3n² 与 100n² 都是 O(n²)，只差常数倍，增长阶相同。常数因子仍影响实际时间，但比较算法优劣时增长阶更本质。

严格地说，O(g(n)) 是一个函数集合，f(n) = O(g(n)) 是“f 属于这个集合”的惯用写法，等号不表示左右相等，也不可随意反向使用。O 只给出上界，线性算法写成 O(n²) 虽正确但不紧。为表达紧界，引入 Θ 记号：若存在正常数 c₁、c₂ 和 n₀，使得对所有 n ≥ n₀ 都有

c₁ · g(n) ≤ f(n) ≤ c₂ · g(n)

则称 f(n) = Θ(g(n))，即 f 与 g 同阶。例 1.3 是 Θ(n²)，不是 Θ(n³)。若上下界一致，用 Θ 更精确；只关心最坏上界时，用 O 更常见。本章后续若未特别说明，O 均指尽量紧的上界。

常见增长阶及其典型来源如下表。增长速度由慢到快为 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)。

这些阶在规模小时差异不明显，规模增大后迅速拉开。图 1-3 左侧示意趋势，右侧列出 n = 10、100、1000 的近似运算量：n² 在 n = 1000 时为一百万次，2ⁿ 已达约 10³⁰¹，远超任何计算机的能力。因此规模可能很大时，必须避免指数阶与阶乘阶算法，或通过约束、近似、动态规划降低复杂度。

log₂ n、log₁₀ n 与 ln n 只差常数因子（换底公式），大 O 下不加区分，简写为 log n。输入规模 n 必须明确：遍历数组时是元素个数，处理整数时可能是位数或数值大小，复杂度含义不同。

15. 最好、平均与最坏情况

对应课件第 58 页。

同一算法在不同输入上的执行次数可能不同，因此需要区分三种情况。最好情况是在所有规模为 n 的输入中使代价最小的输入；最坏情况是使代价最大的输入；平均情况是按某种输入分布求期望代价。三者都是 n 的函数。

课件以冒泡排序为例：最好情况为正序，时间复杂度 O(n)；平均情况为随机排列，O(n²)；最坏情况为逆序，O(n²)。这里需说明算法版本：课件的 O(n) 最好情况对应带“本趟没有发生交换就提前结束”优化的冒泡排序，正序时第一趟比较 n−1 次便结束；若使用不设标志的朴素双重循环，任何输入都要比较 n(n−1)/2 次，最好情况仍是 O(n²)。考试或工程中比较复杂度前，应先明确算法版本与统计口径。

工程上更关注最坏情况：它给出确定上界，便于判断极端输入下是否可接受，实时系统与数据库事务尤其如此。平均情况更贴近长期吞吐量，但需要知道输入分布，否则“平均”没有意义。空间复杂度也类似：若辅助空间依赖输入，应按最坏情况估计，递归算法的栈深度尤其要按最坏递归深度计算。

16. 复杂度分析实例、技巧与易错点

对应课件第 59–62 页。

分析复杂度的基本步骤是：明确问题规模 n；找出执行最频繁的基本操作；写出频度表达式；化简并取增长阶。

例 1：两层独立循环。

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        x = x + 1;

外层执行 n 次，内层对每个 i 都执行 n 次，基本操作共 n² 次，故为 O(n²)。乘法规则只在内外层独立时直接成立。

例 2：内层上界依赖外层。

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        x = x + 1;

i = 0 时内层执行 n 次，i = 1 时 n−1 次，依此类推，总频度 n + (n−1) + … + 1 = n(n+1)/2，仍为 O(n²)，常数约为独立双循环的一半。若内层写成 j = i + 1，总频度为 n(n−1)/2，阶不变。

例 3：倍增循环。

int i = 1;
while (i < n) {
    x = x + i;
    i = i * 2;
}

i 依次取 1, 2, 4, 8, …，每轮翻倍，循环次数为 ⌈log₂ n⌉，故为 O(log n)。若每次变为原来的三分之一，循环次数为 log₃ n，换底后仍记 O(log n)。与之对称，每次把规模减半的递归或循环也属于对数阶。

下面的静态推演以 n = 5 为例，完整展示“逐层求和—写出通式—取阶”的过程。设算法统计所有满足 0 ≤ j < i < n 的下标对个数（即严格左下方的下标对，不含对角线）：

int CountPairs(int n) {
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            count++;
    return count;
}

i = 0 时内层不执行；i = 1 时执行 1 次；i = 2 时 2 次；i = 3 时 3 次；i = 4 时 4 次。总数为 0+1+2+3+4 = 10 = 5×4/2。一般地，count++ 频度为 n(n−1)/2。当 n ≥ 2 时，n(n−1)/2 ≥ n²/4（因为 n−1 ≥ n/2），同时 n(n−1)/2 ≤ n²/2，所以 T(n) 与 n² 同阶，既是 O(n²)，也是 Θ(n²)。这里与上面例 2 的区别要分清：例 2 的内层从 j = i 开始，包含对角线，统计 n(n+1)/2 个下标对（n=5 时为 15）；本段内层从 j = 0 到 j = i−1，不含对角线，统计 n(n−1)/2 个（n=5 时为 10），两者相差 n 个对角线位置，但都是 Θ(n²)。

分析时常见的误区有以下几类。

• 把执行时间当时间复杂度：秒数受机器与语言影响，复杂度刻画基本操作次数随 n 的增长阶。
• 认为嵌套循环一定 O(n²)：内层上界依赖外层时可能是 n(n+1)/2，每轮减半时可能是 O(n log n)。
• 把 O(1) 当成不花时间：它只表示次数与 n 无关，常数可能很大。
• 把上界当紧界：线性算法写成 O(n²) 成立却不说明效率，应尽量给紧界。
• 忽略最坏情况：只按最好或平均情况估计会低估极端代价，平均情况还须说明分布。
• 空间算错对象：通常只统计辅助空间，递归栈空间要计入。
• 纠结对数底数：底数只差常数因子，统一写 log n。

再看查找：无序数组顺序查找最坏 n 次，为 O(n)；有序数组二分查找最坏约 log₂n + 1 次，为 O(log n)，但要求有序且随机访问；有序链表无法直接二分。算法复杂度依赖数据结构提供的操作能力。

17. 本章小结与知识结构

对应课件第 63–67 页。

本章建立了数据结构的共同语言。概念上，数据是总称，数据对象是同类数据元素的集合，数据元素是基本单位，数据项是元素内部的最小单位。数据结构是数据元素集合 D 与关系集合 S 组成的二元组 (D, S)，含逻辑结构与存储结构两层：逻辑结构分四类，存储结构有顺序、链式、索引、散列等，操作效率取决于结构与实现。

抽象数据类型把使用与实现分离，用 (D, S, P) 描述数据对象、关系与基本操作，以外部视图隐藏内部细节。复数 ADT 展示了从定义、接口到 C 风格实现的过程，也说明参数方向、状态返回值与位序/下标约定的重要性。

算法是对求解步骤的有限描述，须满足有穷性、确定性、可行性、输入与输出。设计追求正确、可读、健壮、高效；分析用 T(n)、S(n)，以语句频度找基本操作，用大 O 刻画增长阶，并区分最好、平均与最坏情况。典型解题流程为：分析对象与关系，确定逻辑结构；按操作选择存储结构；用 ADT 定义接口；实现操作；验证复杂度与边界。后续各章按此展开。

18. 练习与参考解答

对应课件第 68–73 页。以下题干按知识点重述，不逐字照录；答案与解析供自查。

选择题

1. 抽象数据类型通常包括哪些方面？A. 数据对象　B. 数据关系　C. 基本操作　D. 计算机主频
2. 下列属于数据逻辑结构范畴的是？A. 元素间的先后关系　B. 元素间的层次关系　C. 元素在内存中的地址　D. 元素占用的字节数
3. 对 n 个记录排序，归并排序、堆排序等高效算法在平均情况下的时间量级是？A. O(n)　B. O(n²)　C. O(n log n)　D. O(log n)
4. 工程上评价时间性能通常关注？A. 最好情况　B. 平均情况　C. 最坏情况　D. 某一次随机运行的时间
5. 预建索引以减少查找时间，主要体现什么策略？A. 降低空间复杂度　B. 以空间换时间　C. 提高时间复杂度　D. 减少输入规模
6. 算法应具备的特性包括？A. 有穷性　B. 确定性　C. 可行性　D. 输入与输出
7. 影响实际执行时间但不改变复杂度量级的是？A. 程序设计语言与编译器　B. 机器速度　C. 问题规模 n　D. 算法策略

第 2 题中，先后与层次关系属逻辑关系，地址与字节数属存储实现；第 7 题中，语言、编译器与机器速度只影响常数因子。

8. 语句频度：求 for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) x++; 中 x++ 的频度与时间复杂度。

内层对每个 i 执行 n−1−i 次，总数为 (n−1) + (n−2) + … + 1 = n(n−1)/2，故为 O(n²)。

9. 复杂度排序：把 O(n²)、O(log n)、O(1)、O(n log n)、O(2ⁿ)、O(n) 按增长速度由慢到快排列。

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。

10. 查找算法：分别写出无序数组与有序数组的查找算法，说明复杂度与前提。

int SearchUnordered(const int A[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (A[i] == key)
            return i;          /* 找到，返回下标 */
    return -1;                 /* 未找到 */
}

int SearchOrdered(const int A[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   /* 防止 low+high 溢出 */
        if (A[mid] == key)
            return mid;
        if (A[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

无序查找不要求有序，最坏比较 n 次，平均成功约 (n+1)/2 次，均为 O(n)；有序查找要求升序且支持随机访问（通常用数组），最坏比较约 log₂n + 1 次，为 O(log n)。若用链表存储，即使有序也无法按下标取中点，二分不适用，只能顺序查找，最坏 O(n)。

11. 成绩统计：某年级 4000 名学生的百分制整数成绩需要统计最高分、最低分、平均分与降序第 2000 名的分数。设计数据结构与高效算法。

注意“降序第 2000 名”是次序统计量，不是通常意义的中位数：4000 为偶数时，统计学的中位数取中间两个分数的平均，而本题只要一个具体分数。把名次作为参数 rank，问题就是求降序第 rank 名的分数；rank = 1 得最高分，rank = n 得最低分。

成绩是 0..100 的整数，范围小且固定，适合用计数数组代替排序：count[s] 记录得分为 s 的人数。一次遍历得到总分、最高分、最低分，同时校验成绩范围；再从 100 到 0 累加人数，累计达到 rank 时的分数就是所求。时间复杂度 O(n + 101)，即 O(n)；辅助空间 O(101)，相对 n 为常数。

Status ScoreStats(const int score[], int n, int rank,
                  int *max_s, int *min_s, double *avg, int *rank_s) {
    if (n <= 0 || rank < 1 || rank > n) return ERROR;
    int count[101] = {0};
    long long total = 0;
    *max_s = -1;
    *min_s = 101;
    for (int i = 0; i < n; i++) {
        if (score[i] < 0 || score[i] > 100)
            return ERROR;                 /* 先校验，再计数 */
        count[score[i]]++;
        total += score[i];
        if (score[i] > *max_s) *max_s = score[i];
        if (score[i] < *min_s) *min_s = score[i];
    }
    *avg = (double)total / n;
    int seen = 0;
    for (int s = 100; s >= 0; s--) {
        seen += count[s];
        if (seen >= rank) {
            *rank_s = s;
            break;
        }
    }
    return OK;
}

若改用比较排序求第 rank 名，通常需 O(n log n) 时间；基于比较的排序下界是 Ω(n log n)，说“至少为 O(n log n)”并不准确——O 是上界记号，这里要用 Ω。计数法利用“范围固定且很小”这一额外信息，把排序的 O(n log n) 降为 O(n)，是典型的以空间换时间。实现时必须先检查 n > 0 与成绩范围，否则 avg 会除以 0 或 count[score[i]] 越界；平均分用 double 保存，避免整数除法截断。

19. 延伸阅读：学科脉络与人物

对应课件第 74–80 页。

渐近记号（O、Ω、Θ）来自 19 世纪末至 20 世纪初的解析数论与分析学，20 世纪中期以后被系统地引入算法分析；计算复杂性在 20 世纪 60 年代前后成为独立的研究方向。

数据结构与算法分析的体系，是伴随编译器、操作系统和大型程序的发展逐步形成的：线性表、栈、队列、树、图等结构及其上的算法在 20 世纪 50—60 年代被大量研究并整理成教材；Knuth 的《计算机程序设计艺术》从 1960 年代末起陆续出版，对这一体系影响很大；Wirth 以“算法 + 数据结构 = 程序”为题写作教材，Hoare 在快速排序、程序逻辑与并发理论等方面有重要贡献。更详细的年表与人物资料可查阅课件第 74–80 页列出的文献，本讲义不再展开考据。

课件列出的参考文献包括 Wirth 的《Algorithms + Data Structures = Programs》、Knuth 的《The Art of Computer Programming》、Horowitz 与 Sahni 的《Fundamentals of Data Structures》、Aho 等的《Data Structures and Algorithms》及严蔚敏、吴伟民的《数据结构（C 语言版）》。可结合这些著作深化对存储结构、算法证明与工程实现的理解。