第 1 章 绪论

下面按 408 数据结构第 1 章《绪论》 的知识体系来讲，并结合资料与第 1 章模拟题。资料给出的考纲只有三块：数据结构基本概念、算法基本概念、时间复杂度和空间复杂度；其中复杂度分析是绝对重点，资料还标出了它在大量年份的统考算法题和选择题中反复出现。

一、第 1 章到底在学什么？

这一章看起来概念很多，但本质上只回答三个问题：

数据怎么组织？算法怎么描述？算法效率怎么衡量？

可以把整个第 1 章压缩成：

数据
 ↓
数据元素之间存在关系
 ↓
数据结构
 ├─ 逻辑结构：数据“逻辑上”是什么关系
 ├─ 存储结构：数据“物理上”怎么放进内存
 └─ 运算：要对这些数据做什么

算法
 ↓
解决问题的一系列有限步骤
 ↓
评价算法
 ├─ 时间复杂度 ★★★★★
 └─ 空间复杂度 ★★★★

其中真正决定这一章考试得分的，是后半部分的复杂度分析。

二、数据结构的基本概念

1. 数据、数据元素、数据项

这三个词经常混淆。

假设学校数据库中有：

那么：

数据是整个可以被计算机处理的信息集合。

数据元素是我们处理数据时的基本单位，例如：

1001 张三 20

这一整条学生记录，就是一个数据元素。

一个数据元素内部还可以继续拆：

学号
姓名
年龄

这些叫做数据项。

所以层次关系是：

数据
 └── 数据元素
       └── 数据项

资料中的定义是：数据元素通常作为一个整体考虑和处理，而数据项是构成数据元素的不可分割的最小单位。

三、数据对象和数据类型

1. 数据对象

数据对象是具有相同性质的数据元素的集合。

例如整数：

这就是一个数据对象。

可以简单理解：

数据元素是“一个东西”，数据对象是一类这样的东西。

2. 数据类型

资料定义：

数据类型 = 一个值的集合 + 定义在这个集合上的一组操作。

例如 C 语言中的 int：

值：
-2、-1、0、1、2……

操作：
+
-
*
/
比较
……

所以类型不只是说“能存哪些值”，还包括：

这些值允许怎样操作。

资料把数据类型分为原子类型、结构类型以及抽象数据类型 ADT。

四、抽象数据类型 ADT 是什么？

ADT 是第一章比较抽象、但非常重要的思想。

ADT 可以理解为：

我只规定一种数据结构“是什么、能干什么”，暂时不规定它底层怎么实现。

比如定义一个“栈”：

数据：
若干元素

操作：
Push(x)
Pop()
GetTop()
Empty()

这里没有规定栈一定用数组还是链表。

所以：

栈这个概念
    ↓
是抽象的

顺序栈
链栈
    ↓
是具体实现

以后你学第 3 章时会发现：

ADT Stack
       ↓
 ┌─────┴─────┐
顺序栈       链栈
数组实现     链表实现

这就是抽象和实现分离。

五、数据结构到底是什么？

资料给出的定义是：

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

但考试时最重要的不是背这句话，而是理解：

数据结构有三要素

数据结构
│
├── 逻辑结构
├── 存储结构
└── 数据的运算

这是第一章最重要的概念框架之一。

六、第一要素：逻辑结构

逻辑结构只研究：

元素之间是什么关系。

它不管这些数据实际放在内存哪个位置。

资料将逻辑结构分为四类。

1. 线性结构为什么叫“一对一”？

例如：

A → B → C → D

B 有一个直接前驱 A，一个直接后继 C。

所以元素之间主要表现为：

一个前驱 ↔ 一个后继

典型代表：

线性表
栈
队列
串

2. 树为什么叫“一对多”？

例如：

        A
      /   \
     B     C
   /  \
  D    E

A 可以对应多个孩子。

所以：

父结点 → 多个子结点

即一对多。

3. 图为什么叫“多对多”？

例如：

A —— B
| \  |
|  \ |
C —— D

一个顶点可能和很多其他顶点连接。

于是就是：

多对多。

七、第二要素：存储结构

逻辑结构解决：

数据之间是什么关系？

存储结构解决：

这种关系在内存里怎么实现？

资料给出四种常见存储结构。

其中 408 最重要的显然是：

顺序存储和链式存储。

八、逻辑结构和存储结构一定要分清

这是第一章最经典的概念陷阱。

例如：

线性表

描述的是：

元素之间是一对一关系。

所以它属于逻辑结构。

而：

顺序表
链表

描述的是：

线性表在计算机中如何存储。

所以属于存储结构。

关系是：

          线性表
        （逻辑结构）
          /    \
         /      \
      顺序表    链表
     顺序存储   链式存储

千万不要说：

“顺序表和线性表是两种数据结构。”

严格说，两者不是同一个层次。

九、顺序存储与链式存储的本质区别

顺序存储

例如：

逻辑：
A → B → C → D

内存：
1000 A
1004 B
1008 C
1012 D

逻辑相邻的数据，物理地址也相邻。

最大的好处：

可以直接计算某元素地址。

所以可以随机访问。

链式存储

可能是：

1000 A → 8000
8000 B → 3000
3000 C → 9000
9000 D → NULL

物理地址完全可以不连续。

关系通过指针表达。

于是想找 C：

A
↓
B
↓
C

必须沿指针一路走过去。

所以资料总结链式存储具有额外指针开销，且只能顺序存取。

这个区别会贯穿整个第二章。

十、第三要素：数据的运算

例如线性表可以有：

插入
删除
查找
排序
遍历

但是有两个层次：

运算的定义
     ↓
逻辑层面

运算的实现
     ↓
存储层面

例如：

“删除第 5 个元素”

这个需求本身与底层数组还是链表无关。

但实现不同：

顺序表
删除后移动后续元素

链表
修改指针

所以资料有一句非常重要的话：

算法的设计取决于逻辑结构，而算法的实现依赖于存储结构。

可以理解为：

我要做什么
↓
逻辑结构

具体怎么做
↓
存储结构

十一、算法是什么？

资料定义：

算法是对特定问题求解步骤的描述，是一个有穷的指令序列。

例如求 1 到 n 的和：

sum = 0;
for (i = 1; i <= n; i++)
    sum += i;

这就是一个算法。

算法不是：

C 语言代码本身

算法是一种问题求解思想和步骤。

它可以：

用 C 写
用 C++ 写
用伪代码写
用自然语言描述

十二、算法的五个基本特征

这是选择题考点。

资料给出五个特征：

特别注意：

输入可以没有，但输出一定要有。

十三、经典陷阱：可读性是不是算法基本特征？

不是。

题库中第 1 章第一道题就是：

不属于算法主要特征的是：有穷性、可行性、确定性、可读性。

答案：

D，可读性。

因为：

有穷性
确定性
可行性
输入
输出

是算法的基本特征。

而：

正确性
可读性
健壮性
高效率
低存储量

属于：

好算法追求的目标。

这是非常典型的概念偷换。

十四、“好算法”的四个目标

资料给出：

其中 408 最关心最后一个：

时间
↓
时间复杂度

空间
↓
空间复杂度

十五、本章最重要内容：时间复杂度

这一部分一定要真正理解，而不是背结论。

资料明确把时间复杂度分析标为本章核心，并记录了其在 2011—2014、2017、2019、2022、2025 等统考年份出现；算法题的复杂度分析也在很多年份反复考查。

十六、为什么不能直接用“运行了几秒”评价算法？

假设同一个程序：

电脑 A：0.1 秒
电脑 B：0.8 秒

到底算法快还是慢？

无法判断。

因为运行时间受到：

CPU
内存
编译器
编译优化
编程语言
操作系统

影响。

所以算法分析不关心：

“到底运行 0.001 秒还是 0.01 秒。”

而关心：

随着数据规模 n 增长，运算次数增长得有多快。

这就是渐近复杂度。

十七、大 O 到底是什么？

假设某算法执行次数：

当 n 非常大时：

增长速度远远超过：

和常数项。

因此只关注最高阶：

大 O 的核心不是精确计算时间，而是描述：

增长数量级。

十八、为什么常数可以忽略？

例如：

n 较小时第二个可能更大。

但当 n 无限增大：

最终一定超过：

所以复杂度研究的是：

n 很大时的增长趋势。

十九、必须背熟的复杂度增长顺序

资料给出：

这一串一定要熟。

直觉上：

O(1)        极好
O(log n)    极好
O(n)        好
O(n log n)  常见高效算法
O(n²)       n 大后明显变慢
O(2ⁿ)       爆炸
O(n!)       更恐怖

排序章节中你会大量遇到：

O(n²)
O(n log n)

图算法中也会频繁比较不同复杂度。

二十、最简单的复杂度：O(1)

例如：

x = a + b;
y = x * 2;

无论 n 多大：

运行次数基本不变

所以：

注意：

执行 1 次
执行 100 次
执行 10000 次

只要次数不随 n 增大：

都是常数复杂度。

二十一、单层循环：O(n)

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

sum++ 执行 n 次：

于是：

二十二、普通双重循环：O(n²)

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        sum++;

外层 n 次。

每次外层：

内层 n 次

因此：

所以：

二十三、加法规则和乘法规则

这是分析复杂度最基础的方法。

顺序执行：看最大项

例如：

for (...)       // O(n)
    ...

for (...)       // O(n²)
    for (...)
        ...

总复杂度：

这叫加法规则。

嵌套执行：相乘

外循环 O(n)
    ↓
里面再执行 O(n)

于是：

这叫乘法规则。

二十四、高频类型一：变量乘法增长

这是 408 最喜欢考的一种。

例如：

i = 1;
while (i <= n)
    i *= 2;

不要一看 while 就认为 O(n)。

设循环执行 t 次。

则：

开始 i=1

第1次后 2
第2次后 4
第3次后 8
……

即：

循环停止时：

所以：

因此：

二十五、模拟题：i 每次乘 3

题库有：

i = 2;
while (i < n / 3)
    i = i * 3;

设循环执行 t 次：

需要满足：

于是 t 与：

同阶。

因此：

选项写：

同样正确。

因为复杂度中对数底数无所谓：

二者只差一个常数。

二十六、重要结论：对数底数不用纠结

因此：

考试通常统一写：

二十七、模拟题：从 n² 不断除以 2

i = n * n;
while (i != 1)
    i = i / 2;

执行 t 次后：

到 1：

即：

取对数：

所以：

忽略常数 2：

这说明一个非常重要的判断：

循环变量乘常数或除常数，通常意味着对数复杂度。

二十八、高频类型二：循环条件不是简单的 i<n

资料专门举例：

int y = 5;
while ((y + 1) * (y + 1) < n)
    y++;

很多人看到：

y++

直接选 O(n)。

这是错的。

设循环执行 t 次：

循环条件：

代入：

于是：

所以：

真正的方法是：

不要只看 i++，而要看“什么时候停止”。

二十九、一个非常实用的循环分析方法

遇到这种代码：

while (...)
    x = ...

统一这样做：

① 设循环执行 t 次
② 写出 t 次之后变量是多少
③ 代入循环终止条件
④ 解 t 与 n 的关系
⑤ 得出复杂度

比死背规律可靠得多。

三十、高频类型三：两层循环不一定 O(n²)

题库有一道非常典型的题：

for(i=1;i<=n;i++){
    for(j=2*i;j<=n;j++){
        y += i*j;
    }
}

很多人第一眼：

两个 for → O(n²)。

虽然本题最终确实是 O(n²)，但这种判断方法是不严谨的。

对于固定 i：

j 从 2i 到 n

因此执行次数大约：

当：

内层甚至完全不运行。

因此总次数是：

展开：

最高阶仍然：

所以：

答案 B。

真正需要掌握的是：

嵌套循环要看内层循环次数是否依赖外层变量。

三十一、非常重要：双指针为什么可以 O(n)？

题库中的滑动窗口题：

int getK(int k) {
    int cnt = 0, left = 0;
    for (int right = 0; right < n; right++) {
        if (nums[right] == 1) cnt++;
        while (left <= right && cnt >= k) {
            if (nums[left] == 1) cnt--;
            left++;
        }
    }
}

表面看：

for
里面 while

似乎：

但这是典型陷阱。

看 right

right 从 0 到 n−1：

最多移动 n 次。

再看 left

虽然 while 位于 for 内部，但：

left++;

一旦增加就不会退回。

整个程序从头到尾：

left 最多从 0 走到 n

因此 left 总共也只移动 O(n) 次。

所以总操作：

最终：

答案 B。

三十二、这是一个必须掌握的思想：总次数，而不是代码层数

以后你看到：

for 里面有 while

不能自动推出：

应该问：

while 在整个程序中累计执行多少次？

如果一个指针一生只能：

向右移动 n 次

那么即使它写在嵌套循环中，也可能只有：

这就是双指针、滑动窗口经常能做到 O(n) 的原因。

三十三、高频类型四：递归时间复杂度

例如资料题库：

int maxFunc(TreeNode* root){
    if (root == NULL) return 0;
    return max(maxFunc(root->left),
               maxFunc(root->right)) + 1;
}

这个函数是在求树高。

很多人看到两个递归调用：

f(left)
f(right)

误以为：

这是错误的。

为什么？

每一个树结点：

只会被访问一次

假设树共有 n 个结点。

整个递归过程：

访问结点 1
访问结点 2
……
访问结点 n

所以：

答案 B。

三十四、判断递归复杂度不能只数“有几个递归调用”

例如：

f(left);
f(right);

关键不是：

“有两个递归调用。”

而是：

所有递归调用合起来处理了多少问题规模？

树遍历：

左子树所有结点
+
右子树所有结点
+
根

合计仍然：

所以：

三十五、递归中的空间复杂度是大坑

题库中斐波那契：

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

它的时间复杂度非常高，大约指数级。

但是空间复杂度不是指数级。

为什么？

关键：空间复杂度看“同时存在”的调用

递归会形成调用树：

             f(n)
           /      \
       f(n-1)     f(n-2)
       / ...

虽然总共可能产生非常多次调用，但 CPU 实际执行时：

先一路递归下去

最长链：

f(n)
f(n-1)
f(n-2)
...
f(1)

最多同时存在约 n 层栈帧。

所以：

而不是：

这是本章极高频陷阱。

三十六、动态规划版本为什么也是 O(n) 空间？

题库另一函数：

int f2(int n) {
    int dp[n + 2], i;
    dp[0] = 0;
    dp[1] = 1;
    for (i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

它直接建立：

dp[n+2]

辅助数组大小与 n 成正比：

因此题目答案：

即 C。

三十七、时间复杂度和空间复杂度一定分开看

递归斐波那契大致是：

时间：指数级
空间：线性级

原因：

时间
看总共调用多少次

空间
看同一时刻最多保存多少层

这是理解递归复杂度最重要的一句话。

三十八、另一个典型递归空间题

题库：

int fun(int *arr, int m, int n) {
    if (m == n)
        return 1;
    else {
        int mid = (m + n) / 2;
        return fun(arr, m, mid)
             + fun(arr, mid + 1, n);
    }
}

每次问题规模减半：

n
↓
n/2
↓
n/4
↓
n/8
↓
...
↓
1

设递归深度为 h：

于是：

所以：

因此调用栈最大深度：

答案 A。

注意：

虽然整个递归树一共有 O(n) 个调用，但同时压在调用栈中的只有一条根到叶子的路径。

三十九、再讲一道非常容易误判的模拟题

int sum = 0;
for (int i = 2; i <= n; i *= i)
    for (int j = 1; j <= i; j++)
        sum++;

i 的变化：

2
4
16
256
65536
...

不是：

2
4
6
8

而是不断平方。

外层次数其实非常少。

但是内层分别执行：

2
4
16
256
...

总执行次数：

由于增长极快，总和被最后一项主导，而最后一项不超过 n。

因此考试中归为：

答案 B。

这里再次体现：

不要根据循环层数判断复杂度，要算基本操作总执行次数。

四十、最好、最坏、平均时间复杂度

资料举了逆序查找例子：

i = n - 1;

while (i >= 0 && A[i] != k)
    i--;

return i;

假设从数组最后开始找 k。

最好情况

如果：

A[n-1] 就是 k

第一下就找到。

复杂度：

最坏情况

如果：

整个数组都没有 k

需要检查 n 个元素：

平均情况

如果 k 在不同位置出现的概率相同，那么平均大约要检查：

但忽略常数后：

四十一、408 为什么通常更关注最坏复杂度？

因为最坏复杂度给出了：

算法运行时间的确定上界。

比如说：

这个算法最坏只需要 O(n)

意味着无论输入多糟糕，都不会突然变成：

O(n²)

所以通常最坏复杂度最有分析价值。

四十二、空间复杂度到底计算什么？

资料强调：

空间复杂度主要关注算法额外使用的辅助空间。

例如：

void f(int A[], int n) {
    int i, sum = 0;
}

虽然输入数组 A 有 n 个元素，但数组 A 是：

输入本身。

不是算法为解决问题额外申请的。

这里只额外用了：

i
sum

固定数量变量。

因此：

四十三、辅助数组

例如：

int B[n];

额外创建一个长度 n 的数组。

那么：

四十四、二维辅助数组

例如：

int dp[n][n];

需要：

个元素。

所以：

四十五、原地算法是什么意思？

如果算法只使用固定数量的辅助变量：

int temp;
int i;
int j;

无论 n 多大都不增加额外空间，则：

资料称这种算法为：

原地工作。

以后排序中会大量出现：

原地排序
非原地排序

例如很多交换排序只需要一个临时变量，因此辅助空间是 O(1)。

四十六、时间复杂度分析最常见的 6 种题型

可以直接形成这套判断框架：

但一定注意：

这些只能帮助快速判断，真正可靠的方法还是计算基本操作的执行总次数。

四十七、第 1 章模拟题全部归纳

你这里的模拟选择题在第 1 章主要集中于复杂度，这与教材标出的考试重点完全一致。

这 9 个点基本把第 1 章真正能出有区分度的题型覆盖得很完整。

四十八、本章最容易犯的 8 个错误

第一，看到两层循环就认为 O(n²)。 错。必须看内层到底累计执行多少次，滑动窗口就是典型反例。

第二，看到递归两次就认为 O(2ⁿ)。 错。二叉树遍历虽然左右各递归一次，但所有结点总共只访问一次，所以 O(n)。

第三，递归调用次数 = 空间复杂度。 错。空间看最大递归深度。

第四，i++ 一定是 O(n)。 错。循环条件可能是平方，例如：

while ((i+1)*(i+1) < n)
    i++;

实际上是 O(√n)。

第五，*i=2 也是 O(n)**。 错，是 O(log n)。

第六，log₂n 和 log₃n 是不同复杂度。 错，在大 O 中只差常数。

第七，可读性属于算法五大特征。 错，它属于好算法的评价目标。

第八，线性表 = 顺序表。 错：

线性表：逻辑结构

顺序表：
线性表的顺序存储实现

四十九、考场上分析代码复杂度的标准流程

以后看到复杂度题，不要凭直觉乱猜，可以固定按照：

第一步：找“基本操作”
        ↓
最深层、真正反复执行的语句

第二步：设它执行 t 次
        ↓
分析循环变量/递归规模如何变化

第三步：建立 t 与 n 的关系
        ↓
例如：
2^t ≈ n
t² ≈ n

第四步：解 t
        ↓
log n
√n
n
n²
……

第五步：只保留最高阶
        ↓
忽略常数
忽略低阶项

对于递归则多问一步：

时间：
所有调用总共做多少工作？

空间：
最深的一条递归路径多长？

这两问能避免绝大多数递归复杂度错误。

五十、把第一章压缩成最终背诵框架

考前复习时其实可以只记下面这张图：

第1章 绪论
│
├─ 一、数据结构基本概念
│   │
│   ├─ 数据
│   ├─ 数据元素
│   ├─ 数据项
│   ├─ 数据对象
│   ├─ 数据类型
│   └─ ADT
│
├─ 二、数据结构三要素
│   │
│   ├─ 逻辑结构
│   │   ├─ 集合
│   │   ├─ 线性结构
│   │   ├─ 树形结构
│   │   └─ 图结构
│   │
│   ├─ 存储结构
│   │   ├─ 顺序
│   │   ├─ 链式
│   │   ├─ 索引
│   │   └─ 散列
│   │
│   └─ 运算
│
└─ 三、算法 ★★★★★
    │
    ├─ 五大特征
    │   ├─ 有穷性
    │   ├─ 确定性
    │   ├─ 可行性
    │   ├─ 输入
    │   └─ 输出
    │
    ├─ 时间复杂度 ★★★★★
    │   ├─ 顺序：加法规则
    │   ├─ 嵌套：乘法规则
    │   ├─ 倍增：log n
    │   ├─ 累加：求和
    │   ├─ 双指针：看总移动次数
    │   └─ 递归：看总调用工作量
    │
    └─ 空间复杂度 ★★★★
        ├─ 辅助变量
        ├─ 辅助数组
        └─ 递归最大深度

五十一、这一章你真正要达到什么水平？

不是把定义全背下来，而是达到三个层次：

第一层，概念不混淆。

看到：

线性表
顺序表
链表
逻辑结构
存储结构
ADT

立即知道它们分别在哪个层次。

第二层，复杂度能快速看出来。

例如看到：

i *= 2;

马上想到：

看到双指针都只向前：

看到递归每次规模减半：

最大递归深度首先想到 O(log n)。

第三层，也是 408 算法题最重要的能力：能把理由写出来。

不要只写：

时间复杂度 O(n²)。

而应该能说明：

基本操作总执行次数为某个求和式，其最高阶项为 n²，因此时间复杂度为 O(n²)。

资料在“归纳总结”中也特别强调：很多考生能一眼看出答案，却无法规范说明推导过程，而 408 算法题需要你具备这种严谨分析能力。

如果只从考试收益排序，第 1 章建议你按：

时间复杂度 > 递归空间复杂度 > 数据结构三要素 > 算法五大特征 > 其余概念

来复习。尤其把上面模拟题中的 滑动窗口 O(n)、递归“时间看总工作量/空间看最大深度”、倍增循环 O(log n) 三类真正吃透，后面线性表、树、图、查找、排序的复杂度分析都会直接用到。