数据结构第 1 章：绪论——概念、存储结构与复杂度分析
绪论这一章看着像名词解释，其实是整门课的坐标系。后面每一章都会反复用到这里的三个东西：逻辑结构与存储结构的区分、抽象数据类型的定义方式、复杂度怎么算。这三个东西没建立起来，学链表时会把"结构"和"实现"混在一起，写算法时也说不清自己写的好不好。
一、四个基本概念要分清
数据、数据元素、数据项是三个不同层级。数据是所有能输入计算机并被处理的符号集合；数据元素是数据的基本单位，在程序里通常当作一个整体处理（比如一条学生记录）；数据项是构成数据元素的不可分割的最小单位（学号、姓名）。
最容易混的是数据对象：它是性质相同的数据元素的集合，是数据的一个子集。比如"所有整数"是数据对象，"某个班的学生记录"也是。
二、逻辑结构与存储结构：这门课最重要的一次区分
逻辑结构是数据元素之间的关系，和计算机无关，只有四类：
- 集合结构：元素之间除"同属一个集合"外没有别的关系
- 线性结构：一对一，除首尾外每个元素有唯一前驱和后继
- 树形结构：一对多，层次关系
- 图形结构：多对多
存储结构（物理结构）是逻辑结构在计算机里的表示，依赖具体语言，核心是用存储单元的地址表示关系：
- 顺序存储：用相邻的物理位置表示逻辑相邻，靠"地址连续"这一性质，可随机存取
- 链式存储：用指针（地址）表示逻辑关系，存储位置不必相邻
- 索引存储：附加索引表，用关键字定位
- 散列存储：由关键字直接算出地址
一句话记住：逻辑结构说的是"谁挨着谁"，存储结构说的是"怎么让它挨着"。后面讨论顺序表和链表时，"插入删除要移动元素"是存储结构导致的结果，不是逻辑结构的性质。
三、数据类型与抽象数据类型
数据类型 = 值的集合 + 定义在这组值上的一组操作。C 语言里的 int、float 都是数据类型。
抽象数据类型（ADT）是把"数据类型"里的实现细节隐藏掉，只保留逻辑特性和操作定义。数学上它是一个三元组 (D, S, P)：D 是数据对象，S 是 D 上的关系集，P 是对 D 的基本操作集。
ADT 的意义在于先定义接口再实现。比如"栈"这个 ADT 规定了 init、push、pop、isEmpty 这些操作，至于用数组还是链表实现，那是后面的事。学本书时看到一个 ADT，要能立刻想清楚：它允许什么操作？允不允许重复元素？有没有容量上限？
四、算法：五个特性、四个要求
算法是对特定问题求解步骤的描述，必须具备五个特性：
- 有穷性：执行有限步后结束（注意程序可以死循环，算法不行）
- 确定性：每条指令含义明确，无二义性
- 可行性：每步都能通过已实现的基本运算执行有限次完成
- 输入：有零个或多个输入
- 输出：有一个或多个输出
设计上还要求正确性、可读性、健壮性、高效率与低存储需求。前三个是底线，后两个是这门课的主线。
五、时间复杂度：只会背 O(n²) 是不够的
时间复杂度不是"程序跑了多久"，而是基本语句执行次数随问题规模 n 增长的量级。用大 O 记号表示上界：若存在正常数 C 和 n₀，使 n ≥ n₀ 时 f(n) ≤ C·g(n)，则记作 f(n) = O(g(n))。
常见阶从低到高：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
三条实用规则：
- 加法规则：O(f) + O(g) = O(max(f, g))，并列的循环取最大的那层
- 乘法规则：O(f) × O(g) = O(f·g)，嵌套循环相乘
- 只看最高阶项、去掉系数：3n² + 100n + 7 是 O(n²)
注意 log 一律指以 2 为底（二分、树的高度都来自折半）。
分析时还要区分最好、最坏、平均三种情况。顺序查找最好 O(1)、最坏 O(n)、平均 O(n)；快速排序平均 O(n log n)、最坏 O(n²)。考试和面试默认问最坏情况，但要能说清三者。
六、空间复杂度与原地工作
空间复杂度 S(n) 是算法额外占用的存储空间随 n 的增长量级，不含输入本身占的空间。
如果额外空间是常数个变量，称原地工作，S(n) = O(1)。后面会看到：冒泡、堆排序、直接插入都是 O(1) 额外空间；归并排序要 O(n) 辅助数组；快排递归栈平均 O(log n)。
这一章在整门课里的位置
- 第 2~6 章讲的是逻辑结构如何用顺序/链式存储实现（线性表→栈队列→串数组→树→图）
- 第 7~8 章讲的是在这些结构上做排序与查找，评价标准就是本章的复杂度
易错点
- 把逻辑结构当成了存储结构。判断"这是线性结构还是树形结构"只看元素间关系，与它在内存里怎么放无关；反过来"顺序存储/链式存储"也不改变逻辑结构。
- 说"算法必须有输入"是错的——输入可以是零个（比如打印固定图形），但输出必须有一个以上。
- 时间复杂度只看量级不看常数，但常数在工程里会决定谁更快。n 很小时 O(n²) 可能比 O(n log n) 快，这也是快排在小区间改用插入排序的原因。
- 空间复杂度不含输入本身占的空间，只算额外开销。把"输入数组"算进去是最常见的错。
O(log n)的底数是 2 还是 10 对量级没影响（只差常数倍），但不能因此把 O(log n) 当成 O(1)。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 数据结构与算法（93讲） 93 讲