数据结构基本概念
🎯 一句话秒杀：数据结构 = 数据 + 结构——研究数据怎么存（逻辑结构+物理结构）和数据怎么操作（算法）。
一、基本概念与术语
数据结构的层次
数据（Data）— 客观事物的符号表示
└── 数据对象（Data Object）— 性质相同的数据元素的集合
└── 数据元素（Data Element）— 数据的基本单位
└── 数据项（Data Item）— 不可分割的最小单位c
// 例如：学生信息表
// 数据对象：全体学生的信息
// 数据元素：单个学生的记录
// 数据项：学号、姓名、成绩——每个都是不可再分的数据项
struct Student { // 数据元素
int id; // 数据项
char name[20]; // 数据项
float score; // 数据项
};核心术语对比
| 术语 | 定义 | 例子 |
|---|---|---|
| 数据 | 客观事物的符号表示 | 数字、文字、图像 |
| 数据元素 | 数据的基本单位 | 一个学生记录 |
| 数据项 | 不可分割的最小单位 | 学号、姓名 |
| 数据对象 | 同性质数据元素的集合 | 全体学生 |
二、逻辑结构（数据间的关系）
四种基本逻辑结构
逻辑结构
├── 集合结构 — 同属一个集合，除此之外没有其他关系
├── 线性结构 — 一对一（如线性表、栈、队列）
├── 树形结构 — 一对多（如树、二叉树）
└── 图状结构/网状结构 — 多对多（如图）
🔑 秒杀秘籍
结构 关系 实例 线性 1:1 排队买票 树形 1:N 家族族谱 图形 N:N 地铁线路图
三、存储结构（物理结构）
四种存储方式
| 存储方式 | 特点 | 优点 | 缺点 |
|---|---|---|---|
| 顺序存储 | 用一组连续的内存单元 | 随机访问快 O(1) | 插入删除需要移动元素 |
| 链式存储 | 用一组任意的内存单元+指针 | 插入删除快 | 只能顺序访问，有额外指针开销 |
| 索引存储 | 建立索引表 | 查找快 | 需要额外索引空间 |
| 散列存储 | 用哈希函数计算位置 | 查找极快 O(1) | 有冲突问题 |
顺序存储 vs 链式存储
| 比较 | 顺序存储 | 链式存储 |
|---|---|---|
| 逻辑相邻→物理位置 | 也相邻 | 不一定相邻 |
| 访问方式 | 随机存取（直接算位置） | 顺序存取（要遍历） |
| 存储密度 | =1（只有数据） | <1（有指针开销） |
| 插入删除 | O(n)—要移动元素 | O(1)—改指针就行 |
| 空间 | 需预分配 | 随用随分配 |
四、数据类型与抽象数据类型
数据类型（Data Type）
一组性质相同的值的集合 + 定义在此集合上的操作
- 原子类型：不可再分（int, char, float）
- 结构类型：由多个成分组成（struct, union, 数组）
抽象数据类型 ADT（Abstract Data Type）
用数学方式定义数据类型——不关心具体实现，只关心"能做什么"
ADT 抽象数据类型名 {
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<操作的定义>
} ADT 抽象数据类型名🚨 红牌警告
数据类型 ≠ 抽象数据类型 数据类型是具体实现（C语言中的int怎么存、怎么算） 抽象数据类型是逻辑描述（不关心底层实现）
五、算法的基本概念
算法的特性（五个）
| 特性 | 含义 | 反例 |
|---|---|---|
| 有穷性 | 有限步后结束 | 死循环 |
| 确定性 | 每一步含义确定 | "把数变大"——歧义 |
| 可行性 | 能通过有限操作实现 | 计算精确π到1亿位（不现实） |
| 输入 | 0个或多个输入 | |
| 输出 | 至少1个输出 | 无输出的程序没用 |
算法 vs 程序
| 对比 | 算法 | 程序 |
|---|---|---|
| 有穷性 | 必须满足 | 可以无限（如操作系统） |
| 语言描述 | 自然语言/流程图/伪代码 | 编程语言 |
| 执行者 | 人 | 计算机 |
六、算法分析——时间复杂度
大O表示法
T(n) = O(f(n)) — 当n→∞时，T(n) ≤ c·f(n)
常见时间复杂度
| 阶 | 名称 | 例子 | 效率 |
|---|---|---|---|
| O(1) | 常数阶 | 取数组元素 a[i] | ⭐⭐⭐⭐⭐ |
| O(log n) | 对数阶 | 二分查找 | ⭐⭐⭐⭐ |
| O(n) | 线性阶 | 遍历数组找最大值 | ⭐⭐⭐ |
| O(n log n) | 线性对数阶 | 快速排序（平均） | ⭐⭐⭐ |
| O(n²) | 平方阶 | 冒泡排序 | ⭐⭐ |
| O(2ⁿ) | 指数阶 | 递归斐波那契 | ❌ |
复杂度计算技巧
c
// O(1) — 不管n多大都执行固定次数
int a = arr[0];
// O(n) — 循环执行n次
for (int i = 0; i < n; i++)
sum += arr[i];
// O(n²) — 两层嵌套循环
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
printf("%d", arr[i][j]);
// O(log n) — 每次规模减半
while (n > 0) {
printf("%d", n);
n /= 2;
}🔑 秒杀秘籍
时间复杂度只看最高阶，忽略常数和低阶 O(2n+1) → O(n) ✅ O(n²+n) → O(n²) ✅ O(100) → O(1) ✅
时间复杂度推导口诀： 一重循环O(n)，两重嵌套O(n²)，每次减半O(log n)
📝 闭卷真题挑战
（点击下方空白查看答案）
1. 数据的逻辑结构分为哪四种？
2. 顺序存储和链式存储的主要区别？
3. 算法必须满足的五个特性是？
4. 以下算法的时间复杂度是？
for(i=0; i<n; i++)
for(j=0; j<n; j++)
a[i][j] = 0;
5. 算法和程序的区别？👆 点击展开答案
- 集合、线性（1:1）、树形（1:N）、图形（N:N）
- 顺序存储逻辑相邻→物理相邻，随机存取；链式存储逻辑相邻→物理不一定相邻，顺序存取
- 有穷性、确定性、可行性、输入、输出
- O(n²)（双层嵌套循环）
- 算法不要求有穷性（？不对——算法必须有穷，程序可以无限运行）；算法是逻辑描述，程序是具体实现
📖 教材习题对照
| 教材习题 | 知识点 | 难度 |
|---|---|---|
| 习题1.1 | 数据结构的定义 | ⭐ |
| 习题1.2 | 逻辑结构与物理结构 | ⭐⭐ |
| 习题1.3~1.4 | 算法特性、时间复杂度 | ⭐⭐ |
| 习题1.5 | 算法分析 | ⭐⭐⭐ |
对应教材：严蔚敏《数据结构》C语言版 第2版 → 第1章 绪论 对应考试大纲：考点12 — 数据结构基本概念、考点20 — 算法基本概念、考点21 — 算法分析初步
📺 配套视频
复习到本考点 → 先看视频补讲，再刷上面「闭卷挑战」。
- 严蔚敏华科大 P2~P3 第一章 绪论 · 基本概念/算法分析
- 严蔚敏本人 P46~P60 本人串讲