第1章绪论（自学版）¶

章节定位：全书入口章

这一章负责搭建术语、算法评价和后续各章共同使用的分析语言。
第一次学习建议整章顺读；复习时重点回看数据结构三要素、算法五特性、时间复杂度与空间复杂度。

适用原文：DS.pdf 第 13-23 页

这一版的目标不是“摘重点”，而是让你只看这一份内容，也能完成第 1 章的学习、理解和复习。

1. 本章定位¶

1.1 本章讲什么¶

本章主要解决两个最基础的问题：

什么是数据结构
什么是算法，以及怎样评价算法的好坏

如果把整本书比作一栋楼，那么这一章就是地基。

后面学线性表、树、图、查找、排序，本质上都在研究“数据如何组织”和“操作这些数据的方法如何设计”。
如果这一章没吃透，后面的内容虽然也能往下学，但会经常出现“会做题，但不知道自己到底在做什么”的情况。

1.2 学完本章后你应该会什么¶

学完这一章后，至少应该能做到：

区分 数据、数据元素、数据项、数据对象
说清楚 数据结构三要素 是什么
区分 逻辑结构 和 存储结构
解释什么是 抽象数据类型（ADT）
说出算法的 五个特性
理解 时间复杂度、空间复杂度 的基本含义
会分析最基础的循环和递归程序的时间复杂度

1.3 学这一章前最好先知道什么¶

几乎不需要前置知识，但最好知道：

什么是程序
什么是数组、变量、循环
什么叫“输入”和“输出”

如果这些也不熟，不影响开始学，但看算法复杂度时会稍微吃力一些。

2. 本章结构总览¶

本章分两大部分：

2.1 第一部分：数据结构的基本概念¶

核心是回答：

研究对象是什么
数据之间有什么关系
这些关系怎样在计算机里表示

2.2 第二部分：算法和算法评价¶

核心是回答：

什么叫算法
一个算法好不好看什么
怎样从时间和空间角度评价它

2.3 建议学习顺序¶

推荐按下面顺序学：

先吃透“术语”
再理解“数据结构三要素”
再学“算法的概念”
最后集中攻“时间复杂度”和“空间复杂度”

原因很简单：

不懂术语，后面所有句子都会看得发飘
不懂三要素，就不知道数据结构到底在研究哪三件事
不懂算法概念和五个特性，就无法真正理解复杂度是在评价什么

3. 核心概念总览¶

本章最重要的关键词如下：

术语	一句话理解
数据	能被计算机识别和处理的符号集合，是加工对象
数据元素	数据的基本单位，通常作为一个整体处理
数据项	构成数据元素的最小不可分单位
数据对象	具有相同性质的数据元素集合
数据类型	值的集合以及定义在其上的操作
抽象数据类型 ADT	从“逻辑上做什么”来描述数据，而不关心具体怎么实现
数据结构	具有特定关系的数据元素集合
逻辑结构	数据元素之间“在逻辑上是什么关系”
存储结构	这些关系“在计算机里怎么存”
数据运算	对数据做什么操作
算法	求解特定问题的有限指令序列
时间复杂度	算法执行时间随问题规模增长的变化趋势
空间复杂度	算法额外占用空间随问题规模增长的变化趋势

4. 1.1 数据结构的基本概念¶

4.1 本节学习目标¶

学完这一节，你要能回答：

数据结构到底是什么
为什么数据结构不只是“存数据”
逻辑结构、存储结构、数据运算三者之间是什么关系

4.2 1.1.1 基本概念和术语¶

4.2.1 数据¶

原书核心意思：

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被程序识别和处理的符号的集合。数据是程序加工的原料。

白话解释：

数据就是“程序要处理的东西”。
它不一定只是数字，也可以是字符、图片、记录、状态、坐标、编号等。

更直观地说：

学生成绩表里的分数是数据
聊天软件里的消息内容是数据
地图导航里的坐标点是数据
游戏里角色的血量、位置、装备也是数据

核心理解：

“数据”强调的是：计算机拿来处理的对象。

4.2.2 数据元素¶

原书核心意思：

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

白话解释：

如果说“数据”是一堆材料，那么“数据元素”就是这堆材料里一个一个被拿来处理的基本单位。

例如：

学生信息表中，“一个学生”通常就是一个数据元素
图书管理系统中，“一本书”通常就是一个数据元素

注意：

数据元素是“处理单位”，不是最小拆分单位。

4.2.3 数据项¶

原书核心意思：

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

白话解释：

数据元素还能继续拆。
拆到不能再拆、而且还保留实际含义的那一小项，就是数据项。

例如：

一个学生记录是数据元素
学号、姓名、性别、年龄，这些就是数据项

最容易混淆的点：

数据元素 是“一个整体对象”
数据项 是“这个对象内部的字段”

可以类比成：

一个学生档案 = 数据元素
档案里的“姓名”“学号”“班级” = 数据项

4.2.4 数据对象¶

原书核心意思：

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

白话解释：

数据对象就是“同一类数据元素组成的集合”。

例如：

所有整数构成一个整数数据对象
所有学生记录构成一个学生数据对象

注意：

“对象”在这里不是面向对象程序设计里的 class/object 那个“对象”，不要混淆。

4.2.5 数据类型¶

原书核心意思：

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

这句话非常重要，要慢慢理解。

它的含义不是“数据长什么样”，而是两件事一起定义：

这种数据能取哪些值
对这些值允许做哪些操作

例如：

int 的值域是一批整数
你可以对它做加减乘除、比较大小等操作

原书把数据类型分为三类：

原子类型
值不可再分
例如整数、字符、布尔值
结构类型
值可以继续分解成若干成分
例如数组、结构体
抽象数据类型 ADT
一个数学模型以及定义在该模型上的一组操作

4.2.6 抽象数据类型（ADT）¶

这是本章最值得反复理解的概念之一。

原书核心意思：

抽象数据类型是一个数学模型以及定义在该数学模型上的一组操作。

白话解释：

ADT 关心的是“逻辑上是什么”和“能做什么”
它暂时不关心“具体怎么存”和“代码怎么写”

这很像我们先定规则，再谈实现。

比如“栈”这个东西：

逻辑规则是“后进先出”
基本操作有“入栈、出栈、取栈顶、判空”
至于它底层是用数组实现还是链表实现，那是后话

所以可以把 ADT 理解成：

先从使用者视角定义接口和行为，再考虑底层实现

这对后面学各种结构都非常重要。

4.2.7 数据结构¶

原书核心意思：

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

继续往深处理解：

数据结构不是“把数据放在那里”这么简单
真正关键的是：这些数据之间有什么关系

例如：

一组学生排成一列，这是线性关系
一个公司组织架构，是层次关系
地铁站之间相互连接，是网络关系

所以“结构”这个词的重点不是“数据本身”，而是“数据之间的组织方式”。

原书进一步指出，数据结构包括三方面内容：

逻辑结构
存储结构
数据的运算

这就是后面要学的“数据结构三要素”。

4.3 1.1.2 数据结构三要素¶

这部分是本节的核心。

如果你只能带走一句话，那就是：

数据结构 = 逻辑结构 + 存储结构 + 数据运算

4.3.1 逻辑结构¶

原书核心意思：

逻辑结构是指数据元素之间的逻辑关系，是从逻辑关系上描述数据的，与存储无关，独立于计算机。

白话解释：

逻辑结构回答的是：“这些数据之间从概念上是什么关系？”
它不关心放在内存哪里，也不关心代码怎么写。

就像你在纸上画关系图时，先考虑“谁和谁有关”，而不是先考虑“变量开在哪个地址”。

原书把逻辑结构分成四类：

集合结构
元素之间除了“同属于一个集合”外，没有其他关系
关键词：无明显次序
线性结构
元素之间是一对一关系
关键词：前驱、后继
典型例子：线性表、栈、队列、串
树形结构
元素之间是一对多关系
关键词：层次
典型例子：树、二叉树
图状结构（网状结构）
元素之间是多对多关系
关键词：网络连接
典型例子：图

最重要的理解方式：

线性结构像排队
树形结构像家谱或组织架构
图状结构像城市交通网或社交关系网

4.3.2 存储结构¶

原书核心意思：

存储结构是数据结构在计算机中的表示，也称物理结构。它包括数据元素的表示和关系的表示。

白话解释：

逻辑结构说的是“逻辑上怎么组织”
存储结构说的是“在计算机里怎么落地”

可以把它理解成：

逻辑结构像建筑设计图
存储结构像真正盖楼时钢筋水泥怎么摆

原书给出的四种主要存储结构：

1. 顺序存储¶

定义：

把逻辑上相邻的元素，存到物理位置上也相邻的单元里

优点：

支持随机存取
存储密度高

缺点：

需要一整块连续空间
插入删除时可能需要移动大量元素
可能产生外部碎片

直觉类比：

像一排连续编号的座位
你知道第 5 个位置，就能很快找到第 5 个元素

2. 链式存储¶

定义：

逻辑上相邻的元素不要求物理上也相邻
用指针或引用表示元素之间的逻辑关系

优点：

空间利用灵活
插入删除方便
不要求连续存储

缺点：

需要额外指针空间
一般不能随机存取，只能顺序访问

直觉类比：

像寻宝图，每张纸条告诉你“下一个宝箱在哪”

3. 索引存储¶

定义：

在存元素的同时，额外建立索引表

优点：

检索快

缺点：

索引表额外占空间
插删时索引也要跟着改

直觉类比：

像书后面的索引页，先查关键词，再定位页码

4. 散列存储（Hash 存储）¶

定义：

根据关键字直接计算出存储地址

优点：

检索、插入、删除通常很快

缺点：

可能发生冲突
冲突处理会增加额外开销

直觉类比：

像按身份证号直接分配储物柜号
但不同人可能“算到”同一个柜子，就发生冲突

4.3.3 数据的运算¶

原书核心意思：

数据的运算包括运算的定义和实现。运算的定义针对逻辑结构，指出运算的功能；运算的实现针对存储结构，指出具体操作步骤。

这是特别容易被忽略、但实际上非常重要的一点。

你可以把它理解成两层：

定义
我要做什么
例如：查找、插入、删除、遍历
实现
我具体怎么做
例如：如果底层是数组，插入要移动元素；如果底层是链表，插入要改指针

一句话总结：

同一个逻辑操作，在不同存储结构下，代码实现和效率可能完全不同。

这句话其实就是后面很多题的根源。

4.4 1.1 节最容易混淆的点¶

4.4.1 数据元素 vs 数据项¶

数据元素：整体处理单位
数据项：构成这个整体的最小字段

例子：

一个学生记录 = 数据元素
学号、姓名 = 数据项

4.4.2 逻辑结构 vs 存储结构¶

逻辑结构：数据之间“概念上”是什么关系
存储结构：这种关系在计算机里“怎么表示”

同一个逻辑结构，可以有不同存储结构。

例如线性表：

可以顺序存储
也可以链式存储

4.4.3 抽象数据类型 vs 具体实现¶

ADT 关注“功能和规则”
具体实现关注“代码和存储方式”

栈就是最典型的例子：

栈这种结构本身是抽象的
顺序栈、链栈是具体实现

4.5 1.1 节原书题目整理与增强解析¶

为了让你不回原书也能自查，这里把原书本节题目所考的核心点整理出来。

自测 1¶

什么可以用来定义一个完整的数据结构？

正确结论：

抽象数据类型（ADT）

原因：

ADT 不只描述数据对象
还描述数据关系和基本操作集
所以它能从“逻辑层面”定义一个完整的数据结构

自测 2¶

树是不是线性结构？

正确结论：

不是
树是典型非线性结构

原因：

线性结构是一对一关系
树是典型一对多关系

自测 3¶

顺序表、哈希表、单链表、有序表中，哪个更偏向“逻辑结构”？

关键理解：

顺序表、哈希表、单链表都带有实现色彩
有序表强调的是“元素按关键字有序”，更偏逻辑关系描述

自测 4¶

数据的逻辑结构是否独立于存储结构？

正确结论：

是

但反过来不能说：

存储结构独立于逻辑结构

因为：

存储结构本来就是逻辑结构在计算机中的映射

自测 5¶

存储数据时，只存值就够了吗？

不够。

还必须存：

数据元素之间的关系

否则结构信息就丢了。

典型综合题结论¶

问题 1：不同数据结构的逻辑结构或物理结构一定不同吗？¶

不一定。

关键点：

数据结构不只包括逻辑结构和物理结构
还包括数据运算
即使逻辑结构和物理结构相同，如果运算定义不同，也可以视为不同数据结构

问题 2：同一逻辑结构在不同存储方式下，运算效率会一样吗？¶

不会。

典型例子：

线性表顺序存储时，插入删除通常要移动元素
线性表链式存储时，插入删除只需改指针

所以：

逻辑结构相同，不代表实现效率相同。

5. 1.2 算法和算法评价¶

5.1 本节学习目标¶

学完这一节，你要能回答：

什么是算法
算法的五个特性是什么
如何评价一个算法
时间复杂度和空间复杂度到底在衡量什么
为什么我们更关注“增长趋势”而不是精确运行秒数

5.2 1.2.1 算法的基本概念¶

5.2.1 算法的定义¶

原书核心意思：

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

白话解释：

算法就是“解决问题的步骤说明书”
而且这份说明书必须能真的执行完

注意这句话里有两个关键词：

特定问题
算法不是胡乱写步骤
它必须对应明确的问题
有限序列
步骤不能无限做下去

5.2.2 算法的五个重要特性¶

原书给出五个特性，这五个特性非常常考。

1. 有穷性¶

含义：

算法必须在有限步之后结束
每一步也必须在有限时间内完成

白话解释：

不能写出“永远做不完”的流程

2. 确定性¶

含义：

算法中的每条指令都必须有确切含义
相同输入应得到相同输出

白话解释：

步骤不能模糊到“你自己看着办”

3. 可行性¶

含义：

算法中描述的操作都能通过已经实现的基本操作执行有限次得到

白话解释：

不能写出“理论上美好，但机器根本做不到”的步骤

4. 输入¶

含义：

一个算法有零个或多个输入

说明：

有的算法不需要外部输入也能运行
但一般求解问题的算法都会有输入

5. 输出¶

含义：

一个算法有一个或多个输出

白话解释：

算法总得有结果
否则就不能叫“求解”

5.2.3 好算法还应具备哪些目标¶

除了“定义上必须具备的五个特性”，原书还强调一个“好算法”通常应追求：

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

这部分很重要，因为考试喜欢考“算法五个特性”和“好算法的评价标准”的区别。

不要混淆：

五个特性：算法“能成立”的基本要求
正确性、可读性、健壮性、高效率：算法“好不好”的评价标准

5.2.4 本节常见误区¶

误区 1：

“可读性、正确性、可靠性”也是算法定义的五个特性

这是错的。

正确的是：

算法定义的五个特性是：有穷性、确定性、可行性、输入、输出

误区 2：

只要程序能运行，就是算法

也不对。

因为：

可能没有明确输出
可能无限循环
可能步骤不确定

5.3 1.2.2 算法效率的度量¶

这一节是全章重点，也是整本书最常反复用到的基础工具。

5.3.1 为什么要学复杂度¶

很多同学一开始会问：

直接运行程序看快不快，不就行了吗？

不够。

因为程序运行时间受很多因素影响：

机器性能
编译器优化
输入数据分布
常数项大小

而复杂度更关注：

当问题规模变大时，算法开销增长得快不快

所以复杂度研究的是：

增长趋势

而不是某一次运行恰好用了多少毫秒。

5.3.2 时间复杂度¶

1. 语句频度¶

原书先讲“语句频度”：

一条语句在算法中被重复执行多少次，就叫它的频度

如果把所有语句频度加起来，可得到总执行次数。

但真正分析时，通常不用把每一句都精确算到死。

我们更关注：

执行次数最高
对整体增长趋势起决定作用

的那部分操作。

2. 基本运算¶

原书强调：

通常把最深层循环中的语句看作基本运算

因为它往往执行次数最多，决定整体复杂度级别。

3. 时间复杂度的本质¶

原书核心思想：

若算法执行次数函数是 T(n)，时间复杂度关注的是 T(n) 的数量级

所以：

忽略低阶项
忽略常数系数
只看增长最快的主导项

例如：

n^3 + n + 2 的时间复杂度是 O(n^3)
5n + 100 的时间复杂度是 O(n)

4. 三种常见时间复杂度¶

最坏时间复杂度¶

在最坏情况下，算法的时间复杂度

这是最常用、也最常考的。

原因：

它给出的是上界保证
能保证程序不会比这更慢

平均时间复杂度¶

所有可能输入在等概率出现时的期望运行时间

最好时间复杂度¶

在最好情况下的时间复杂度

考试中通常默认优先分析：

最坏时间复杂度

5. 一个很重要的认识¶

原书专门提醒：

算法时间复杂度不仅与问题规模 n 有关，还与输入数据本身的状态有关。

例如顺序查找：

如果目标就在第一个位置，复杂度接近 O(1)
如果根本找不到，可能要找完整个表，复杂度接近 O(n)

所以同一个算法，输入不同，执行次数也会不同。

5.3.3 时间复杂度的运算规则¶

1. 加法规则¶

如果一段程序由几部分顺序执行，那么总复杂度取最大项。

也就是：

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

直觉解释：

增长最快的那部分，最终会主导整体开销

2. 乘法规则¶

如果一段程序是多层嵌套，那么复杂度通常相乘。

也就是：

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

例如：

外层循环 n 次
内层循环 n 次
总复杂度通常是 O(n^2)

5.3.4 常见复杂度的大小关系¶

原书给出了常见渐近时间复杂度的增长顺序。

从小到大大致可以记成：

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

你可以把它理解成：

前面这些通常还能接受
到指数级、阶乘级就会爆炸得非常快

5.3.5 空间复杂度¶

原书核心意思：

空间复杂度是算法所需存储空间的数量级，它也是问题规模 n 的函数。

白话解释：

它衡量的是：算法运行时额外要占多少空间

要特别注意“额外”两个字。

一般分析时，我们通常不把：

程序本身代码占的空间
输入数据本来就占的空间

算作重点，而更关注算法运行时新申请的辅助空间。

例如：

只用了几个变量：空间复杂度通常是 O(1)
新开了一个长度为 n 的辅助数组：空间复杂度通常是 O(n)

原地工作（In-place）¶

原书强调：

如果算法所需辅助空间是常量级，则称为原地工作

也就是：

空间复杂度为 O(1)

这在排序等章节里会非常重要。

5.4 复杂度分析方法总结¶

这一部分是根据原书“归纳总结”整理出来的，非常适合自学时反复看。

5.4.1 类型一：循环变量直接参与循环终止条件¶

典型形式：

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

分析思路：

设循环执行了 t 次
写出第 t 次后的变量表达式
由终止条件建立不等式
解出 t 和 n 的关系

上例中：

每循环一次，i 乘 2
执行 t 次后，i = 2^t
终止前满足 2^t <= n
所以 t = O(log n)

因此时间复杂度为：

O(log n)

5.4.2 类型二：多层循环直接累计次数¶

典型形式：

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

分析思路：

外层 n 次
内层每次 n 次
总次数 n * n

所以时间复杂度：

O(n^2)

5.4.3 类型三：递归程序¶

最基础的递归分析，先看：

递归调用几层
每层做多少工作

例如：

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

这里：

递归深度约为 n
每层工作量为常数

所以总复杂度：

O(n)

而像下面这种：

int func(int n){
  if(n == 1) return 1;
  return 2 * func(n / 2) + n;
}

如果只看递归深度：

n -> n/2 -> n/4 -> ... -> 1
深度约为 log n

很多基础题就是先这么判断。

5.5 1.2 节原书题目整理与增强解析¶

这一节原书题比较多，我这里把核心考法整理成“自学训练点”。

训练点 1：算法的五个特性¶

你必须准确记住：

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

常见陷阱：

把“正确性”“可读性”“健壮性”误记成五个特性的一部分

训练点 2：时间复杂度 `O(n^2)` 的含义¶

它不表示：

实际运行时间一定等于 n^2

它表示：

当 n 增大时，执行时间与 n^2 同数量级增长

训练点 3：空间复杂度 `O(1)` 的含义¶

它不表示：

完全不占空间

它表示：

额外辅助空间与 n 无关，是常量级

训练点 4：循环复杂度分析¶

看到下面几类代码要有直觉：

每次 i++
常见是 O(n)
每次 i *= 2
常见是 O(log n)
两层 for
常见是 O(n^2)
外层倍增、内层累计
要分开分析再合并

训练点 5：原书中常见真题型结论¶

类型 A：`i *= 2`¶

常见答案：O(log n)

类型 B：`i * i * i < n`¶

常见答案：O(n^{1/3})

因为：

若循环执行 t 次，满足 t^3 < n
所以 t = O(n^{1/3})

类型 C：`sum = sum + ++i`¶

常见答案：O(n^{1/2})

因为：

累加 1 到 t 得到约 t^2 / 2
若要达到 n，则 t 大约是 sqrt(n)

类型 D：外层倍增、内层跑到当前外层值¶

例如：

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

总次数约为：

1 + 2 + 4 + ... + 2^k

这是等比数列，和约为：

O(n)

这类题很经典，很容易误判成 O(n log n)，要小心。

6. 本章重点结论¶

这一部分建议直接背熟。

6.1 数据结构三要素¶

逻辑结构
存储结构
数据运算

6.2 四类逻辑结构¶

集合结构
线性结构
树形结构
图状结构

6.3 四类主要存储结构¶

顺序存储
链式存储
索引存储
散列存储

6.4 算法五个特性¶

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

6.5 算法评价常看什么¶

正确性
可读性
健壮性
时间效率
空间效率

6.6 时间复杂度本质¶

关注执行次数的数量级
忽略低阶项和常数项
通常分析最坏时间复杂度

6.7 空间复杂度本质¶

关注额外辅助空间的数量级
O(1) 表示常量辅助空间，不表示“不占空间”

7. 本章易错点¶

易错点 1¶

把 数据元素 和 数据项 混为一谈。

正确区分：

数据元素：整体单位
数据项：元素内部字段

易错点 2¶

把 逻辑结构 和 存储结构 混为一谈。

正确区分：

逻辑结构：关系
存储结构：表示方式

易错点 3¶

认为一个逻辑结构只能有一种存储结构。

错误。

例如线性表就可以：

顺序存储
链式存储

易错点 4¶

把“算法五个特性”和“好算法评价标准”混在一起。

易错点 5¶

看到 O(n^2) 就误以为运行时间“等于” n^2。

正确理解：

只是同数量级增长

易错点 6¶

把 O(1) 理解成“不需要空间”。

正确理解：

只是不随 n 增长

易错点 7¶

分析复杂度时把每条语句都死扣，结果越算越乱。

更好的做法：

先找基本运算
再看执行次数如何随 n 变化

8. 本章复习提纲¶

考前快速回顾时，可以直接看这一部分。

8.1 术语链¶

数据 -> 数据元素 -> 数据项 -> 数据对象 -> 数据类型 -> 抽象数据类型 -> 数据结构

8.2 数据结构三问¶

数据之间逻辑上怎么组织
在计算机里怎么存
要对它做哪些运算

8.3 逻辑结构四类¶

集合
线性
树形
图状

8.4 存储结构四类¶

顺序
链式
索引
散列

8.5 算法五特性¶

有穷
确定
可行
输入
输出

8.6 复杂度口诀¶

顺序执行取最大
多层循环通常相乘
i *= 2 常见 log n
双重循环常见 n^2
只开常数个辅助变量是 O(1)

9. 本章自学检查¶

如果你学完这一章，应该能独立回答下面这些问题。

9.1 概念检查¶

数据元素和数据项有什么区别？
为什么说数据结构不只是“数据的存放方式”？
逻辑结构和存储结构分别解决什么问题？
ADT 为什么“抽象”？

9.2 判断检查¶

树是不是线性结构？
顺序表是不是逻辑结构？
时间复杂度 O(n) 是否表示程序一定执行 n 次？
空间复杂度 O(1) 是否表示程序不占空间？

9.3 能力检查¶

你应该能分析出下面几类复杂度：

单层 for
双层 for
while(i < n) i *= 2
while(i * i < n) i++
递归深度为 n 的简单递归

如果这些还做不到，建议先别急着进第 2 章，先把本章最后的复杂度分析方法再看一遍。

10. 本章一句话总结¶

第 1 章的本质，就是先搞清楚“数据怎么组织”，再搞清楚“解决问题的步骤怎么评价”；后面整本书，其实都建立在这两个问题之上。

11. 原书关键定义保留层¶

这一节专门把本章最值得保留的原书定义集中放在一起。

这样做的目的有两个：

方便你在复习时直接看“严谨表述”
方便你在自学时区分“教材原意”和“辅助解释”

11.1 数据¶

原书关键定义：

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

你要抓住的关键词：

信息的载体
能被程序识别和处理
是程序加工的原料

11.2 数据元素¶

原书关键定义：

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

抓法：

“基本单位”是关键词
“整体处理”是重点

11.3 数据项¶

原书关键定义：

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

抓法：

数据项比数据元素更细
数据项是字段级概念

11.4 数据对象¶

原书关键定义：

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

抓法：

强调“相同性质”
强调“集合”

11.5 数据类型¶

原书关键定义：

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

抓法：

不是只有“值”
还包括“操作”

11.6 抽象数据类型 ADT¶

原书关键定义：

抽象数据类型是一个数学模型及定义在该数学模型上的一组操作。

抓法：

数学模型
一组操作
不急着谈具体实现

11.7 数据结构¶

原书关键定义：

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

原书继续强调：

数据结构包括逻辑结构、存储结构和数据的运算。

这两句合在一起记，效果最好。

11.8 逻辑结构¶

原书关键定义：

逻辑结构是指数据元素之间的逻辑关系，是从逻辑关系上描述数据的，与数据的存储无关，是独立于计算机的。

你要牢牢记住：

逻辑结构不等于代码实现
它描述的是“关系”

11.9 存储结构¶

原书关键定义：

存储结构是指数据结构在计算机中的表示，也称物理结构。

原书进一步指出：

它包括数据元素的表示和关系的表示。

11.10 算法¶

原书关键定义：

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

抓法：

求解步骤
指令序列
有限

11.11 算法五个特性¶

原书给出的五个特性：

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

这是原书层面最需要原封不动记住的一组结论。

11.12 时间复杂度¶

原书核心意思整理：

时间复杂度主要分析算法执行次数的数量级。

进一步说：

一般取基本运算执行次数的数量级作为算法时间复杂度
常写成 T(n) = O(f(n))

11.13 空间复杂度¶

原书核心意思整理：

空间复杂度是算法所需存储空间的数量级，它也是问题规模 n 的函数。

抓法：

关注的是存储开销的增长趋势
实际分析时更关注辅助空间

12. 原书知识框架复原版¶

为了让这一章更接近“脱离 PDF 也能看”，这里把原书开头那张知识框架用文字重新搭起来。

12.1 数据结构部分¶

数据结构主要看三件事：

逻辑结构
存储结构
数据的运算

其中逻辑结构又可以分为：

线性结构
线性表
栈
队列
串
数组
非线性结构
树
图
集合

12.2 算法部分¶

算法这一块主要看：

算法定义
算法五个特性
时间复杂度
空间复杂度

原书这一章的真正重点，不在名词记忆，而在：

复杂度分析

13. 原书题目整理版¶

这一节是把原书题目区尽量补进来，让你不回 PDF 也能继续练。

13.1 1.1 节题目整理版¶

单项选择题 1¶

可以用什么定义一个完整的数据结构？

答案：

抽象数据类型 ADT

原因：

ADT 同时给出数据对象、数据关系、基本操作集
比单独的数据元素、数据对象、数据关系都更完整

单项选择题 2¶

下列结构中，哪一个是非线性数据结构？

正确结论：

树

原因：

树是一对多关系
属于典型非线性结构

单项选择题 3¶

属于逻辑结构的是哪一个？

正确结论：

有序表

原因：

有序表强调的是元素之间的有序关系
它可以采用不同存储方式
所以更偏逻辑层

单项选择题 4¶

关于数据结构，正确的说法是什么？

正确结论：

数据的逻辑结构独立于其存储结构

错误点提醒：

存储结构不能脱离逻辑结构单独存在
逻辑结构也不能唯一决定某一种存储结构

单项选择题 5¶

在存储数据时，除了存储数据元素的值，还必须存什么？

正确结论：

数据元素之间的关系

综合应用题 1¶

对于两种不同的数据结构，逻辑结构或物理结构一定不同吗？

标准理解：

不一定

原因：

数据结构不只包括逻辑结构和物理结构
还包括数据运算
即使前两者相同，只要运算定义不同，也可能形成不同的数据结构

综合应用题 2¶

举例说明：相同逻辑结构、相同运算，在不同存储方式下实现时，效率可以不同。

标准例子：

线性表

分析：

顺序存储时，插入删除通常要移动大量元素
链式存储时，插入删除通常主要修改指针

这道题最想考的不是背答案，而是让你建立一个重要意识：

逻辑结构相同，不代表操作效率相同。

13.2 1.2 节题型全覆盖整理版¶

这一部分原书题量较大，我按“题型 + 结论 + 为什么”重组，尽量做到既完整又适合自学。

题型 1：算法的五个特性¶

常考问法：

算法应该具有什么重要特性？

标准答案：

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

高频误区：

把正确性、可读性、健壮性混进去

题型 2：如何评价算法优劣¶

标准理解：

不能只看时间效率和空间效率
还要看正确性、可读性、健壮性

但如果题目问“算法定义上的五个特性”，则不能答这些评价标准。

题型 3：时间复杂度 `O(n^2)` 的含义¶

正确理解：

表示执行时间与 n^2 同数量级增长

不表示：

时间就等于 n^2
问题规模变成了 n^2

题型 4：空间复杂度 `O(1)` 的含义¶

正确理解：

所需辅助空间大小与 n 无关

不表示：

不需要任何空间

题型 5：多个函数中谁的复杂度最小¶

原书这类题的核心考法是：

不看常数
不看低阶项
只看主导项

例如：

20000 log n 的复杂度仍然优于 n
n log n 仍然优于 n^2

题型 6：`while(i <= n) i = i * 2`¶

结论：

时间复杂度为 O(log n)

原因：

每次翻倍
执行次数约等于能翻倍多少次才达到 n

题型 7：`while(iii < n) i++`¶

结论：

时间复杂度为 O(n^{1/3})

原因：

若执行 t 次，则大致满足 t^3 < n

题型 8：冒泡排序式双层循环中的交换频度¶

结论：

最坏情况下是 O(n^2)

原因：

交换次数约为 (n-1) + (n-2) + ... + 1

题型 9：带分支的双层循环¶

结论：

复杂度分析通常取分支中的较大者

也就是：

看最耗时的那条执行路径

题型 10：递归不断减半¶

典型形式：

Func(n/2)

结论：

若每层工作量为常数，则复杂度常见为 O(log n)

题型 11：递归不断减一¶

典型形式：

fact(n-1)

结论：

若每层工作量为常数，则复杂度常见为 O(n)

题型 12：`x = 2*x`¶

结论：

复杂度常见为 O(log n)

题型 13：`sum += ++i`¶

结论：

常推出 1 + 2 + ... + t ≈ n
所以 t = O(n^{1/2})

题型 14：外层倍增，内层跑满当前外层值¶

典型形式：

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

结论：

总复杂度为 O(n)

原因：

总次数是 1 + 2 + 4 + ... + 2^k
等比数列求和仍然是 O(n)

题型 15：平方或开方型循环¶

典型形式：

while((x+1)*(x+1) <= n) x++;

结论：

复杂度为 O(n^{1/2})

题型 16：多层循环拆分分析¶

核心方法：

先找基本运算
算单层执行次数
再组合
最后取数量级

题型 17：综合应用题¶

原书这部分实际上在训练你两种核心能力：

通过循环变量建立不等式
通过求和计算总执行次数

这两种能力一旦熟了，后面很多复杂度题都会顺很多。

14. 归纳总结增强版¶

这一节是对原书“归纳总结”的扩写版，专门为自学设计。

14.1 为什么很多人会“看懂答案，但不会自己做”¶

因为复杂度分析不是只靠感觉，而是要有流程。

很多人平时会这样：

看见题，觉得大概是 n^2
但真让他写推导过程，又说不清

所以你要练的是：

判断 + 推导 + 表达

三件事一起会。

14.2 自学时建议固定使用的分析流程¶

每次做复杂度题，都按下面顺序走：

找基本运算
设它执行了 t 次
写出循环变量或递归规模变化规律
建立和 n 的关系式
解出 t
写成大 O 形式

14.3 两类最常见题型¶

第一类：变量直接参与循环终止条件¶

例子：

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

就设：

执行 t 次后 i = 2^t

再由终止条件推 t = O(log n)。

第二类：多层循环累计次数¶

例子：

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

就看总次数：

0 + 1 + 2 + ... + (n-1)
所以是 O(n^2)

14.4 这章最该形成的直觉¶

不是背结论，而是形成下面这些直觉：

每次加 1，通常是线性级
每次乘 2，通常是对数级
两层都跑 n 次，通常是平方级
等比数列求和经常还是线性级
等差数列求和经常变成平方级

15. 思维拓展增强版¶

原书本章最后给了一个思维拓展：

斐波那契数列可以用递归算法和非递归算法求解
试分析两种算法的时间复杂度

这里将内容整理为完整自学版。

15.1 递归求斐波那契¶

最朴素递归：

F(n) = F(n-1) + F(n-2)

特点：

会产生大量重复计算
递归树会快速膨胀

复杂度直觉：

指数级

通常可记为：

O(2^n) 量级

15.2 非递归求斐波那契¶

如果用循环从前往后推：

for(i = 2; i <= n; i++)

特点：

每个状态只算一次

复杂度：

时间复杂度 O(n)
若只保留前两项，空间复杂度 O(1)

15.3 这个思维拓展真正想告诉你什么¶

不是只让你比较两个答案。

它真正想让你理解：

同一个数学问题
不同算法设计
时间复杂度可能差很多

这其实就是整本书后面“查找、排序、图算法”反复在讲的思想。

继续阅读¶

下一章：第2章线性表 →

第1章 绪论（自学版）¶

1. 本章定位¶

1.1 本章讲什么¶

1.2 学完本章后你应该会什么¶

1.3 学这一章前最好先知道什么¶

2. 本章结构总览¶

2.1 第一部分：数据结构的基本概念¶

2.2 第二部分：算法和算法评价¶

2.3 建议学习顺序¶

3. 核心概念总览¶

4. 1.1 数据结构的基本概念¶

4.1 本节学习目标¶

4.2 1.1.1 基本概念和术语¶

4.2.1 数据¶

4.2.2 数据元素¶

4.2.3 数据项¶

4.2.4 数据对象¶

4.2.5 数据类型¶

4.2.6 抽象数据类型（ADT）¶

4.2.7 数据结构¶

4.3 1.1.2 数据结构三要素¶

4.3.1 逻辑结构¶

4.3.2 存储结构¶

1. 顺序存储¶

2. 链式存储¶

3. 索引存储¶

4. 散列存储（Hash 存储）¶

4.3.3 数据的运算¶

4.4 1.1 节最容易混淆的点¶

4.4.1 数据元素 vs 数据项¶

4.4.2 逻辑结构 vs 存储结构¶

4.4.3 抽象数据类型 vs 具体实现¶

4.5 1.1 节原书题目整理与增强解析¶

自测 1¶

自测 2¶

自测 3¶

自测 4¶

自测 5¶

典型综合题结论¶

问题 1：不同数据结构的逻辑结构或物理结构一定不同吗？¶

问题 2：同一逻辑结构在不同存储方式下，运算效率会一样吗？¶

5. 1.2 算法和算法评价¶

5.1 本节学习目标¶

5.2 1.2.1 算法的基本概念¶

5.2.1 算法的定义¶

5.2.2 算法的五个重要特性¶

1. 有穷性¶

2. 确定性¶

3. 可行性¶

4. 输入¶

5. 输出¶

5.2.3 好算法还应具备哪些目标¶

5.2.4 本节常见误区¶

5.3 1.2.2 算法效率的度量¶

5.3.1 为什么要学复杂度¶

5.3.2 时间复杂度¶

1. 语句频度¶

2. 基本运算¶

3. 时间复杂度的本质¶

4. 三种常见时间复杂度¶

最坏时间复杂度¶

平均时间复杂度¶

最好时间复杂度¶

5. 一个很重要的认识¶

5.3.3 时间复杂度的运算规则¶

1. 加法规则¶

2. 乘法规则¶

5.3.4 常见复杂度的大小关系¶

5.3.5 空间复杂度¶

原地工作（In-place）¶

5.4 复杂度分析方法总结¶

5.4.1 类型一：循环变量直接参与循环终止条件¶

5.4.2 类型二：多层循环直接累计次数¶

5.4.3 类型三：递归程序¶

5.5 1.2 节原书题目整理与增强解析¶

训练点 1：算法的五个特性¶

训练点 2：时间复杂度 O(n^2) 的含义¶

训练点 3：空间复杂度 O(1) 的含义¶

训练点 4：循环复杂度分析¶

训练点 5：原书中常见真题型结论¶

第1章绪论（自学版）¶

训练点 2：时间复杂度 `O(n^2)` 的含义¶

训练点 3：空间复杂度 `O(1)` 的含义¶

类型 A：`i *= 2`¶

类型 B：`i * i * i < n`¶

类型 C：`sum = sum + ++i`¶

题型 3：时间复杂度 `O(n^2)` 的含义¶

题型 4：空间复杂度 `O(1)` 的含义¶

题型 6：`while(i <= n) i = i * 2`¶

题型 7：`while(iii < n) i++`¶