【王道考研·数据结构】第一章 绪论（整合版）

引言

第一章虽然叫“绪论”，但它并不是可有可无的铺垫。恰恰相反，这一章决定了你后面学习整本《数据结构》的观察角度。

这一章真正要解决的是三个问题：

  1. 什么是数据结构
  2. 什么是算法
  3. 怎么评价一个算法好不好

如果说后面的线性表、树、图是在讲“具体有哪些结构”，那么第一章讲的就是：

你应该用什么语言和标准去理解这些结构。

本篇基于现有旧文章 30 与 31 合并整理，形成真正完整的第一章整合版。

图像化理解（Mermaid）

一句话理解：第一章就是整本数据结构的“评价体系”，后面每章都在用这套体系。

一、数据结构的基本概念

1. 数据（Data）

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

它的范围非常广：

  • 数值
  • 字符
  • 图像符号
  • 其他可以输入计算机的表示形式

2. 数据元素（Data Element）

数据元素是数据的基本单位，通常作为一个整体进行处理。

例如：

  • 排队系统中的一位顾客
  • 学生信息表中的一条记录

3. 数据项（Data Item）

数据项是构成数据元素的不可分割的最小单位。

例如一位顾客这个数据元素，可能由：

  • 排号
  • 取号时间
  • 就餐人数

等多个数据项组成。

4. 数据对象（Data Object）

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

简单理解：

  • 数据元素是“一个个个体”
  • 数据对象是“一类个体的集合”

5. 数据结构（Data Structure）

数据结构是：

相互之间存在特定关系的数据元素集合。

注意重点不在“元素本身长什么样”，而在：

  • 元素之间有什么关系
  • 如何存这些关系
  • 如何对这些元素和关系做操作

这也是为什么数据结构这门课不是“背概念课”，而是“组织和处理数据的方法课”。

二、数据类型与抽象数据类型

1. 数据类型（Data Type）

数据类型可以理解为：

值的集合 + 定义在这个集合上的运算

常见分类：

（1）原子类型

值不可再分，例如：

  • bool
  • int
  • char

（2）结构类型

值可以进一步分解成若干成分，例如：

  • 数组
  • 结构体 struct

2. 抽象数据类型（ADT）

抽象数据类型（Abstract Data Type）强调的是：

  • 只描述数据对象的逻辑结构
  • 只描述允许进行哪些操作
  • 不关心底层究竟如何实现

也就是说，ADT 更关注的是：

做什么，而不是 怎么做。

例如“栈”这个 ADT，只要求你知道：

  • 可以进栈
  • 可以出栈
  • 后进先出

但至于它是用数组实现还是链表实现，属于实现层的问题。

3. ADT 的核心特点

  • 信息隐藏
  • 封装
  • 与具体硬件和实现方式无关

这也是后面你会反复看到“逻辑结构”和“物理结构”分开的原因。

三、数据结构三要素

第一章里最核心的框架之一就是：

数据结构三要素 = 逻辑结构 + 物理结构（存储结构） + 数据运算

1. 逻辑结构

逻辑结构描述的是：

数据元素之间在逻辑上的关系

它与计算机中的实际存放位置无关。

逻辑结构通常分四类：

（1）集合结构

元素之间除了“同属一个集合”外，没有其他关系。

（2）线性结构

元素之间是一对一关系：

  • 除首元素外，每个元素有唯一前驱
  • 除尾元素外，每个元素有唯一后继

例如：

  • 线性表
  • 栈
  • 队列

（3）树形结构

元素之间是一对多关系，具有明显层次。

例如：

  • 树
  • 二叉树

（4）图结构

元素之间是多对多关系，形成网状连接。

例如：

  • 图

2. 物理结构（存储结构）

物理结构讨论的是：

数据元素在计算机内存中到底怎么存。

常见有四类：

（1）顺序存储

  • 逻辑上相邻的元素，物理位置也相邻
  • 必须占用一块连续存储空间

（2）链式存储

  • 逻辑上相邻的元素，物理位置可以不相邻
  • 通过指针表示逻辑关系

（3）索引存储

  • 额外建立索引表
  • 索引项常写成 (关键字, 地址)

很像书本目录。

（4）散列存储（Hash）

  • 通过散列函数直接计算存储地址
  • 查找速度通常很快
  • 但可能发生哈希冲突

3. 数据运算

数据运算也分两个层次：

（1）运算定义

站在逻辑结构层面，描述“要完成什么功能”。

例如：

  • 插入
  • 删除
  • 查找

（2）运算实现

站在存储结构层面，描述“具体怎么做”。

例如同样是插入：

  • 顺序表要移动元素
  • 链表要改指针

4. 三要素之间的关系

这一点一定要理解透：

  1. 逻辑结构决定运算定义
  2. 物理结构决定运算实现
  3. 同一种逻辑结构可以对应多种物理结构

比如线性表：

  • 可以顺序存储成顺序表
  • 也可以链式存储成链表

逻辑结构没变，但实现方式完全不同。

四、算法的基本概念

在数据结构里有一句非常经典的话：

程序 = 数据结构 + 算法

其中：

  • 数据结构解决“数据怎么组织”
  • 算法解决“数据怎么处理”

所以后面每学一种数据结构，最终都要落到算法上。

1. 算法的五大特性

一个过程要被称为“算法”，必须同时满足以下五个特性：

（1）有穷性

算法必须在有穷步之后结束，并且每一步都能在有穷时间内完成。

注意区分：

  • 算法必须有穷
  • 程序不一定有穷

比如操作系统、服务器程序可以长期运行，但它们不影响算法“必须结束”这个要求。

（2）确定性

算法中的每一步都必须有明确含义，不能出现二义性。相同输入必须得到相同输出。

（3）可行性

算法中的操作必须能够通过已经实现的基本运算在有限次内完成。

（4）输入

算法可以有 0 个或多个输入。

很多同学会误以为算法必须“至少有 1 个输入”，这是错误的。

（5）输出

算法必须有 1 个或多个输出。

2. 算法五大特性的常见易错点

  • 把“正确性”“可读性”“健壮性”误当成算法五大特性
  • 把程序和算法混为一谈
  • 忘记“输入可以为 0 个”

五、好算法的标准

满足五大特性，只能说明它是一个算法；但一个“好算法”还应该进一步满足下面这些标准。

1. 正确性

能正确解决问题。

这是最基本的底线。

2. 可读性

算法逻辑清晰、便于理解。

可读性强意味着：

  • 更容易检查
  • 更容易维护
  • 更容易修改

3. 健壮性

面对非法输入或异常情况时，算法能合理处理，而不是直接崩溃。

4. 高效率

也就是时间复杂度尽可能低。

5. 低存储量需求

也就是空间复杂度尽可能低。

6. 为什么考研最关注“效率”

在考试中，算法是否正确通常由题目目标隐含决定，而真正区分优劣的往往是：

  • 时间复杂度
  • 空间复杂度

因此第一章后半部分的重点几乎都在复杂度分析。

六、时间复杂度

1. 什么是时间复杂度

时间复杂度不是“程序运行了多少秒”，而是：

当问题规模 n 增大时，算法执行次数增长的数量级。

它关注的是增长趋势，不是某次具体运行时的绝对时间。

2. 为什么不用真实运行时间衡量

因为真实运行时间会受到很多外部因素影响：

  • 机器性能
  • 编译器
  • 语言实现
  • 系统负载

时间复杂度则更能反映算法本身的优劣。

七、大 O 记法与常见计算规则

1. 大 O 记法的本质

大 O 记法只保留执行次数中的：

  • 最高阶项

并忽略：

  • 常数项
  • 低阶项
  • 常数系数的影响

例如：

1
3n^2 + 5n + 100 -> O(n^2)

2. 加法规则

若算法由前后两个部分组成，则：

1
O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

例如前一部分 O(n)、后一部分 O(n^2)，则总体为 O(n^2)。

3. 乘法规则

若是嵌套结构，则：

1
O(f(n)) * O(g(n)) = O(f(n)g(n))

例如：

  • 外层 n 次
  • 内层 log2 n 次

总体为：

1
O(n log2 n)

4. 常见复杂度排序

必须熟记：

1
O(1) < O(log2 n) < O(n) < O(n log2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

旧文给出的记忆口诀是：

常对幂指阶

5. 最坏与平均时间复杂度

  • 最坏时间复杂度：最差情况下的性能
  • 平均时间复杂度：所有输入等概率出现时的期望性能

在考研中，通常默认优先考虑最坏时间复杂度。

八、典型复杂度推导模型

1. 对数阶

例如：

1
2
3
4
int i = 1;
while (i <= n) {
    i = i * 2;
}

设执行 x 次，则：

1
2^x > n

所以：

1
x = log2 n

复杂度为：

1
O(log2 n)

2. 平方根阶 / 立方根阶

若循环条件为：

1
(x + 1)^2 <= n

则执行次数量级约为：

1
O(sqrt(n))

若条件为：

1
i^3 <= n

则复杂度约为：

1
O(n^(1/3))

3. 双层循环

例如：

1
2
3
for(i = 0; i < n; i++)
    for(j = 0; j < m; j++)
        a[i][j] = 0;

复杂度为：

1
O(mn)

4. 等比求和型循环

例如：

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

总次数为：

1
1 + 2 + 4 + ... + 2^k < 2n

因此总体复杂度是：

1
O(n)

5. 三角求和型循环

例如：

1
2
3
for(i = 1; i <= sqrt(n); i++)
    for(j = 1; j <= i; j++)
        count++;

执行次数为：

1
1 + 2 + ... + sqrt(n)

其数量级为：

1
O(n)

这类题很容易被误判成 O(sqrt(n))，因为只看了外层范围，忽略了内层累加。

九、递归与复杂度

分析递归时要分清两件事：

  1. 时间复杂度：总共做了多少工作
  2. 空间复杂度：递归栈有多深

1. 阶乘递归

1
2
3
4
int fact(int n) {
    if(n <= 1) return 1;
    return n * fact(n - 1);
}

每层常数工作，递归深度为 n，因此：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

2. 分治递归

例如：

1
T(n) = 2T(n/2) + n

根据旧文分析：

  • 共 log2 n 层
  • 每层工作量为 O(n)

所以总时间复杂度：

1
O(n log2 n)

3. 递归空间复杂度的核心结论

递归算法的空间复杂度通常等于递归深度。

这是第一章里非常高频的结论。

十、空间复杂度

1. 什么是空间复杂度

空间复杂度描述的是算法运行过程中，额外辅助空间随问题规模增长的数量级。

2. 原地工作

若算法只需要有限个局部变量，且这些变量数量与 n 无关，则空间复杂度为：

1
O(1)

这类算法通常称为：

原地工作

3. 递归空间开销

递归每深入一层，系统都要开辟新的函数调用栈帧，因此递归空间复杂度往往不低。

这也是为什么有些递归虽然写起来简洁，但不一定节省空间。

十一、图像化总览（Mermaid）

1. 三要素关系图

2. 逻辑结构分类图

3. 复杂度增长对比图（从快到慢）

4. 递归时间/空间拆分图

十二、易错点与易混淆点（详细版）

A. 易混淆点（A vs B）

  1. 数据项 vs 数据元素

    • 数据元素：一条完整记录（如“一个学生”）
    • 数据项：记录内部字段（如“学号/姓名/年龄”）
    • 记忆法：元素是“对象”，数据项是“属性”。

  2. 逻辑结构 vs 存储结构

    • 逻辑结构：数学关系（谁和谁相邻/父子/连通）
    • 存储结构：内存实现（连续/链式/索引/散列）
    • 同一逻辑结构可对应多种存储结构（这是高频考点）。

  3. ADT vs 具体实现

    • ADT：接口和语义（做什么）
    • 实现：代码和内存（怎么做）
    • 例如“栈”是 ADT；顺序栈、链栈是实现。

  4. 算法五特性 vs 好算法标准

    • 五特性是“是不是算法”的门槛
    • 好算法标准是“好不好”的评价
    • 最常错：把“正确性”误记到五特性里。

  5. 时间复杂度 vs 实际运行时间

    • 复杂度看增长阶，不看某台机器跑几秒
    • 实际时间受语言、编译器、硬件影响很大
    • 考试默认比较复杂度，不比较具体秒数。

B. 易错点（为什么错 + 怎么改）

  1. 误写“算法必须有输入”

    • 错因：把“常见情况”当“定义”。
    • 正解：输入可以是 0 个或多个；输出必须至少 1 个。

  2. 把 O(1) 理解成“不占空间/不耗时”

    • 错因：把数量级误解成绝对值。
    • 正解：O(1) 表示与 n 无关，不代表常数很小。

  3. 加法/乘法法则混用

    • 错因：看见两个循环就机械相乘。
    • 正解：
      • 前后顺序执行：取大项（加法）
      • 内外嵌套执行：相乘（乘法）

  4. 只看外层循环就下结论

    • 错因：忽略内层求和变化。
    • 正解：像三角求和 1+2+...+sqrt(n) 结果是 O(n)，不是 O(sqrt(n))。

  5. 递归只看一层，不看总层数

    • 错因：只盯着递推式里的“+n”。
    • 正解：总时间=每层工作量 × 层数；空间还要单算栈深度。

C. 这一章做题速查顺序

1
2
3
4
5
6
7
8
9
先分清：概念题 or 复杂度题
  |
  +-- 概念题：先判类别（逻辑/存储/ADT/算法特性）
  |
  +-- 复杂度题：
        1) 找基本操作
        2) 写执行次数
        3) 抽最高阶
        4) 再判递归栈空间

十三、书签级思维导图复现（第一章，Mermaid）

下面按全书 PDF 书签结构，把第一章再细化成可直接背诵的导图。

十四、PDF 例题与知识点补充（绪论）

本节按“概念题 -> 推导题 -> 代码题”补齐第一章高频例题。

例题 1：数据项 / 数据元素 / 数据对象区分

题目：学生记录 {"学号", "姓名", "年龄"} 中，哪个是数据项，哪个是数据元素，哪个是数据对象？

答案：

  • 数据项：学号、姓名、年龄
  • 数据元素：一条完整学生记录
  • 数据对象：全体学生记录构成的集合

详细解析：

  1. 数据项是“不可再分的最小字段”，因此每个字段本身是数据项。
  2. 数据元素是“业务处理的基本单位”，即一条完整记录。
  3. 数据对象是“同类数据元素的集合”，即所有学生记录。
  4. 记忆顺序是：字段 -> 记录 -> 集合。

例题 2：逻辑结构判断

题目：以下场景分别属于哪类逻辑结构？

  1. 班级点名顺序
  2. 公司组织架构
  3. 地铁换乘网络

答案：

  1. 班级点名顺序 -> 线性结构
  2. 公司组织架构 -> 树形结构
  3. 地铁换乘网络 -> 图结构

详细解析：

  1. 点名顺序是单链式前后关系，属于一对一。
  2. 组织架构是上下级关系，一个上级可对应多个下级，属于一对多。
  3. 地铁站之间可形成多对多连接和回路，属于图结构。

例题 3：同一逻辑结构的多种存储

题目：线性表是否只能顺序存储？

答案：否。

详细解析：

  1. 线性表是逻辑结构，描述的是元素逻辑关系。
  2. 顺序表和链表是两种不同的存储实现。
  3. 同一逻辑结构可对应多种存储结构，这是数据结构三要素的常考点。

例题 4：算法五特性辨析

判断正误：

  1. 算法必须有输入。
  2. 算法必须有输出。
  3. 程序必须有穷。

答案：

  1. 错（输入可为 0 个）
  2. 对（至少 1 个输出）
  3. 错（程序可长期运行）

详细解析：

  1. 算法定义中输入是“0 个或多个”，不是“至少 1 个”。
  2. 输出是“1 个或多个”，必须有输出。
  3. 算法强调有穷性，但程序可作为系统服务长期运行。

例题 5：循环复杂度 I

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

答案：时间复杂度 O(log n)。

详细解析：

  1. 每轮循环 i 乘以 3，第 x 轮后 i = 3^x。
  2. 循环结束条件是 3^x > n。
  3. 解得 x = log3 n，在大 O 中底数忽略，写为 O(log n)。

例题 6：循环复杂度 II

1
2
3
for (i = 1; i <= n; i++)
  for (j = 1; j <= i; j++)
    count++;

答案：时间复杂度 O(n^2)。

详细解析：

  1. 外层执行 n 次。
  2. 第 i 次外层时，内层执行 i 次。
  3. 总执行次数为 1+2+...+n = n(n+1)/2。
  4. 最高阶为 n^2，故复杂度 O(n^2)。

例题 7：循环复杂度 III（易误判）

1
2
3
for (i = 1; i * i <= n; i++)
  for (j = 1; j <= i; j++)
    count++;

答案：时间复杂度 O(n)。

详细解析：

  1. 由 i*i <= n 得外层上界是 sqrt(n)。
  2. 内层执行次数是 1+2+...+sqrt(n)。
  3. 该和式为 sqrt(n)*(sqrt(n)+1)/2，数量级是 n。
  4. 所以不是 O(sqrt(n))，而是 O(n)。

例题 8：递归复杂度 I

1
T(n)=T(n-1)+O(1)

答案：时间复杂度 O(n)。

详细解析：

  1. 递推式 T(n)=T(n-1)+O(1) 表示每层做常数工作。
  2. 递归深度约 n 层。
  3. 累加后是 n 个常数项，总体 O(n)。

例题 9：递归复杂度 II

1
T(n)=2T(n/2)+O(n)

答案：时间复杂度 O(n log n)。

详细解析：

  1. T(n)=2T(n/2)+O(n) 属于典型分治递推。
  2. 递归树高度约 log n。
  3. 每一层的总工作量都约为 n。
  4. 总工作量为 n * log n，即 O(n log n)。

例题 10：递归空间复杂度

1
2
3
4
int f(int n){
  if(n<=1) return 1;
  return f(n-1)+1;
}

答案：

  1. 时间复杂度 O(n)
  2. 空间复杂度 O(n)

详细解析：

  1. 每次调用仅做常数操作，递归深度是 n，时间 O(n)。
  2. 调用栈会保留 n 层栈帧，辅助空间 O(n)。
  3. 本题核心是区分“总调用次数”和“最大栈深”。

例题 11：大 O 加法法则

1
2
for(i=0;i<n;i++) a++;
for(i=0;i<n*n;i++) b++;

答案：总复杂度 O(n^2)。

详细解析：

  1. 第一段是 O(n)，第二段是 O(n^2)。
  2. 串行执行时复杂度相加：O(n) + O(n^2)。
  3. 大 O 保留主导项，最终是 O(n^2)。

例题 12：大 O 乘法法则

1
2
3
for(i=0;i<n;i++)
  for(j=0;j<log2(n);j++)
    c++;

答案：总复杂度 O(n log n)。

详细解析：

  1. 外层循环 n 次。
  2. 内层循环约 log2(n) 次。
  3. 嵌套结构按乘法法则：O(n) * O(log n)。
  4. 得到 O(n log n)。

十五、第一章必背清单（可直接自测）

A. 概念必背

  1. 数据结构定义。
  2. 数据结构三要素。
  3. 四类逻辑结构。
  4. 四类存储结构。
  5. 算法五特性。

B. 公式必背

  1. 1+2+...+n = n(n+1)/2
  2. 1+2+4+...+2^k = 2^(k+1)-1
  3. 常见复杂度序：
1
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

C. 高频易错口令

1
2
3
4
输入可为0，输出至少1
程序可无穷，算法必须有穷
同逻辑结构可多存储实现
递归空间看深度，不看总调用次数

总结

第一章真正建立的是整个《数据结构》的分析框架：

  1. 先看对象是什么：数据、数据元素、数据结构、ADT
  2. 再看结构是什么：逻辑结构、物理结构、数据运算
  3. 最后看算法怎么样：五大特性、复杂度、效率评价

如果把第一章压缩成一句话，那就是：

后面所有数据结构问题，最终都要落回“结构 + 算法 + 复杂度”这套分析框架。

只要这一章打牢，后面学线性表、栈、队列、树、图时，你就会知道自己到底在分析什么。

作者：[Austoin]
参考来源：基于现有旧文章整理