（适用于：备考数据结构期末考试，日常学习理解，面试复习，考研辅助理解）
写在前面
想象一个场景。
你走进一个图书馆。书架上所有的书按类别排列：文学在一层，科技在一层，历史在一层。每本书有编号，有位置。你找一本书，不会迷路。
现在想象另一个场景。同样是这个图书馆，书被随意堆在地上，没有分类，没有编号。你想找一本《C++ Primer》——只能一本一本翻。
哪个图书馆你愿意去？
数据结构，就是第一种图书馆。
它研究的是：数据怎么组织、怎么存放、怎么高效地存取，也就是对数据的整理归纳。
一、数据结构是什么？
1.1 定义
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
拆开看：
- 数据：程序处理的对象（数字、文字、图片、音频…）
- 结构：这些对象之间的关系
你写一个学生管理系统。每个学生有学号、姓名、成绩。多个学生放在一起，你怎么存？
- 用一个数组？→ 顺序结构
- 用一个链表？→ 链式结构
- 用一张树形表格？→ 树形结构
不同的存法，就是不同的数据结构。
1.2 两个维度：逻辑结构 vs 物理结构
这两个词很重要，搞混了后面全乱。
| 维度 | 意思 | 比喻 |
|---|---|---|
| 逻辑结构 | 数据之间是什么关系（从你的角度看） | 家庭关系：你知道谁是爸爸、谁是儿子 |
| 物理结构 | 数据在内存里怎么存放（从计算机的角度） | 房子地址：爸爸住101，儿子住102，还是住隔壁楼 |
同一套逻辑关系，可以用不同的物理方式存放。
二、四种基本逻辑结构
2.1 集合结构
关系：数据元素之间没有关系。就像一麻袋土豆，每个土豆是独立的。
应用：哈希表。
2.2 线性结构
关系：一对一。每个元素有一个前驱、一个后继（除了第一个和最后一个）。
应用：数组、链表、栈、队列（第二章和第三章的内容）。
2.3 树形结构
关系：一对多。一个节点有多个子节点，但每个子节点只有一个父节点。
应用：文件系统、HTML的DOM树、二叉搜索树（第六章）。
2.4 图形结构
关系：多对多。任意两个节点之间都可能连接。
应用：地图导航（地铁线路）、社交网络（好友关系）、网络路由（第七章）。
三、算法是什么？
有了数据，你要操作它们——查找、插入、删除、排序。
算法：解决特定问题的步骤描述。
做一道菜需要菜谱。解一道题需要算法。
3.1 算法的五个特性
| 特性 | 含义 |
|---|---|
| 有穷性 | 必须能在有限步内结束，不能死循环 |
| 确定性 | 每一步没有歧义，同一种输入得到同一种输出 |
| 可行性 | 每一步都能在有限时间内执行完 |
| 输入 | 有0个或多个输入 |
| 输出 | 至少有1个输出 |
3.2 好算法的标准
- 正确：能解决问题
- 可读：别人（或三个月后的你）看得懂
- 健壮：输入非法数据不会崩溃
- 高效：跑得快、占内存少
后面两个（快和少），就是复杂度分析要解决的问题。
四、时间复杂度：你的算法跑得有多快？
4.1 为什么要分析时间复杂度？
写两个算法解决同一个问题。一个跑1秒，一个跑1小时。区别在哪里？
不是看代码长短，是看操作次数随输入规模增长的速度。
4.2 大O表示法
我们不看具体的执行时间（跟机器、语言有关）。我们看操作次数随n增长的趋势。
用大O表示：忽略常数项、忽略低次项。
| 代码示例 | 执行次数 | 时间复杂度 |
|---|---|---|
int a = 10; | 1次 | O(1) |
for(int i=0;i<n;i++){ sum+=i; } | n次 | O(n) |
for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ sum++; } } | n²次 | O(n²) |
4.3 常见复杂度曲线（最重要的一张图）
- O(1)：水平线
- O(log n)：平缓上升，越来越平
- O(n)：斜线
- O(n log n)：比斜线稍陡
- O(n²)：快速上升的抛物线
- O(2^n)：像跳楼一样垂直上升
]
看到这张图，你就能理解为什么O(2^n)的算法在n=100时，宇宙毁灭了都跑不完。
4.4 最好、最坏、平均情况
以顺序查找为例（在一个数组里找一个数）：
- 最好情况：第一个就是 → O(1)
- 最坏情况：最后一个才是，或者没有 → O(n)
- 平均情况：大概在中间 → O(n)
我们一般关心最坏情况。因为写程序要保证任何时候都不会崩。
4.5 计算复杂度的小技巧
// 例子1：O(1)intsum=0;sum=a+b;// 例子2：O(n)for(inti=0;i<n;i++){sum+=i;}// 例子3：O(n²)for(inti=0;i<n;i++){for(intj=0;j<n;j++){sum++;}}// 例子4：O(log n)inti=1;while(i<n){i=i*2;// i每次翻倍，循环次数是log₂n}口诀：
- 看循环嵌套层数（一层O(n)，两层O(n²)）
- 看循环变量变化（每次乘2 → O(log n)）
- 顺序执行，取量级最大的
五、空间复杂度：你的算法占多少内存？
时间复杂度的兄弟：空间复杂度。
也是用大O表示，分析额外占用的内存随n增长的趋势。
// O(1) 空间：只用了几个变量，跟n无关intsum=0;for(inti=0;i<n;i++){sum+=i;}// O(n) 空间：申请了一个大小为n的数组int*arr=newint[n];for(inti=0;i<n;i++){arr[i]=i;}delete[]arr;时间换空间 / 空间换时间：
- 用一个额外数组记录中间结果，可以少循环几次 → 空间换时间
- 不申请新数组，直接在原数组上操作 → 时间换空间
没有绝对的好坏。内存够大时，优先优化时间。嵌入式系统内存紧张时，优先优化空间。
六、本章总结（背下来）
| 概念 | 一句话解释 |
|---|---|
| 数据结构 | 数据怎么组织 |
| 算法 | 问题怎么解决 |
| 逻辑结构 | 数据之间是什么关系（集合/线性/树/图） |
| 物理结构 | 数据在内存里怎么放（顺序/链式） |
| 时间复杂度 | 跑多快（大O表示） |
| 空间复杂度 | 占多少内存（大O表示） |
📌 本章必考必背知识点清单
一、核心概念（背定义）
| 术语 | 定义 | 考法 |
|---|---|---|
| 数据 | 所有能输入计算机并能被程序处理的符号总称 | 选择题：下列哪个属于数据？ |
| 数据元素 | 数据的基本单位，通常作为一个整体考虑 | 填空题：数据的基本单位是____ |
| 数据项 | 数据元素的最小组成单位，不可再分 | 选择题：数据项vs数据元素的关系 |
| 数据对象 | 性质相同的数据元素的集合 | 判断题：数据对象是数据的一个子集 |
| 数据结构 | 相互之间存在特定关系的数据元素的集合 | 简答题：数据结构的定义 |
数据元素、数据项、数据对象的关系图（必考）：
举例：学生表（数据对象）
→ 每个学生记录（数据元素）
→ 学号、姓名、成绩（数据项）
二、逻辑结构与物理结构对比（必背）
| 对比维度 | 逻辑结构 | 物理结构（存储结构） |
|---|---|---|
| 定义 | 数据元素之间的逻辑关系 | 数据在内存中的存放方式 |
| 与计算机无关？ | ✅ 是（抽象层面） | ❌ 否（硬件层面） |
| 分类 | 集合、线性、树形、图形 | 顺序存储、链式存储 |
| 考法 | 判断题：逻辑结构是面向问题的 | 选择题：数组对应哪种物理结构 |
四种逻辑结构速记表：
| 结构 | 关系 | 举例 | 考法 |
|---|---|---|---|
| 集合 | 无关系 | 哈希表 | 选：哪个是无关系结构 |
| 线性 | 一对一 | 数组、链表 | 选：排队属于哪种 |
| 树形 | 一对多 | 文件目录、家族树 | 选：文件夹结构 |
| 图形 | 多对多 | 地铁图、社交网络 | 选：好友关系属于哪种 |
三、算法相关（必背）
| 术语 | 定义 | 考法 |
|---|---|---|
| 算法 | 解决特定问题的步骤描述 | 简答题：算法的定义 |
| 有穷性 | 算法必须在有限步内结束 | 判断题：死循环是否满足有穷性？ |
| 确定性 | 相同输入得到相同输出 | 选择题：确定性含义 |
| 可行性 | 每一步都能在有限时间内完成 | 判断题 |
| 正确性 | 算法能解决问题 | 简答题：好算法的标准 |
| 健壮性 | 输入非法数据不会崩溃 | 简答题 |
| 高效性 | 时间少、空间少 | 简答题 |
四、时间复杂度计算（期末必考大题）
时间复杂度 = 基本操作执行次数 与 n 的函数关系
可以这么理解：
在i次循环内，n从0->n，i=n
在i次循环内，n从1->2的i次方，i=log2n
所以，时间复杂度，其实就是i和n的关系
4.1 大O表示法规则
| 规则 | 说明 | 例子 |
|---|---|---|
| 常数项忽略 | O(1) 就是 O(1) | 10 → O(1) |
| 只保留最高次项 | 去掉低次项 | n² + n → O(n²) |
| 忽略系数 | 去掉常数乘数 | 2n → O(n) |
4.2 常见复杂度大小关系（必背顺序）
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
4.3 复杂度计算模板（背下来）
| 代码模式 | 复杂度 | 判断方法 |
|---|---|---|
int a = 0; | O(1) | 没有循环 |
for(i=0;i<n;i++){...} | O(n) | 一层循环 |
for(i=0;i<n;i++){ for(j=0;j<n;j++){...} } | O(n²) | 两层循环（次数独立） |
for(i=0;i<n;i++){ for(j=0;j<i;j++){...} } | O(n²) | 两层循环（求和 1+2+…+n = n(n+1)/2） |
while(i<n){ i=i*2; } | O(log n) | 循环变量乘2除2 |
for(i=0;i<n;i++){ while(j<n){ j++; } } | O(n) | j不重置，总共n次 |
| 二分查找 | O(log n) | 每次砍一半 |
| 递归斐波那契（无记忆） | O(2ⁿ) | 递归树节点数 |
4.4 典型例题（背解法）
例题1：
intsum=0;for(inti=0;i<n;i++){for(intj=0;j<i;j++){sum++;}}答案：O(n²) —— 因为 1+2+…+n-1 = n(n-1)/2
例题2：
inti=1;while(i<n){i=i*2;}答案：O(log n) —— 2^k = n → k = log₂n
例题3：
for(inti=0;i<n;i++){for(intj=0;j<100;j++){sum++;}}答案：O(n) —— 内层固定100次，常数忽略
例题4：
for(inti=0;i<n;i++){for(intj=i;j<n;j++){sum++;}}答案：O(n²) —— n + (n-1) + … + 1 = n(n+1)/2
五、空间复杂度（常考）
| 代码 | 空间复杂度 | 原因 |
|---|---|---|
int a; | O(1) | 单个变量 |
int arr[100]; | O(1) | 固定大小，与n无关 |
int* p = new int[n]; | O(n) | 大小随n增长 |
int arr[n][n]; | O(n²) | 二维数组 |
空间换时间：用额外数组换速度
时间换空间：不用额外数组，慢一点
下一章预告
第二章：线性表。我们会讲数组和链表的爱恨情仇，包括它们怎么插入、删除、查找，以及什么时候用数组、什么时候用链表。
思考题（检验你有没有读懂）
- 以下代码的时间复杂度是多少？
for(inti=0;i<n;i++){for(intj=0;j<i;j++){cout<<"*";}}逻辑结构和物理结构的区别是什么？能不能给一个“逻辑上是线性结构，物理上是链式结构”的例子？
为什么我们通常分析最坏情况复杂度，而不是最好情况？
（答案在评论区公布）
