Appearance
数据结构的基本概念
核心思想
基本概念和术语
| 术语 | 定义 | 示例 |
|---|---|---|
| 数据 | 信息的载体，能被计算机识别和处理的符号集合 | 数字、字符、图像 |
| 数据元素 | 数据的基本单位，通常作为整体处理 | 一条学生记录 |
| 数据项 | 构成数据元素的不可分割的最小单位 | 学号、姓名、性别 |
| 数据对象 | 性质相同的数据元素的集合，是数据的子集 | 整数集合 N = |
层次关系：数据 ⊃ 数据对象 ⊃ 数据元素 ⊃ 数据项
数据类型
数据类型是一个值的集合以及定义在该集合上的一组操作的总称。
| 类型 | 定义 | 示例 |
|---|---|---|
| 原子类型 | 值不可再分 | int、float、char |
| 结构类型 | 值可分解为若干成分 | struct、数组 |
| 抽象数据类型（ADT） | 数学模型 + 定义在其上的一组操作 | 栈 ADT、队列 ADT |
ADT 的核心是封装——使用者只需知道"能做什么操作"，不需要知道"怎么存储、怎么实现"。
数据结构三要素
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。一个完整的数据结构包含三个要素：
1. 逻辑结构
逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。
| 逻辑结构 | 元素间关系 | 示例 |
|---|---|---|
| 集合 | 同属一个集合，无其他关系 | — |
| 线性结构 | 一对一 | 线性表、栈、队列 |
| 树形结构 | 一对多 | 二叉树、堆 |
| 图状结构 | 多对多 | 有向图、无向图 |
2. 存储结构（物理结构）
存储结构是逻辑结构在计算机中的具体实现，依赖于编程语言。
| 存储结构 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 顺序存储 | 逻辑相邻 → 物理相邻 | 随机存取，密度大 | 需要连续空间，可能产生外部碎片 |
| 链式存储 | 用指针表示逻辑关系 | 无碎片，充分利用空间 | 指针占额外空间，只能顺序存取 |
| 索引存储 | 额外建立索引表（关键字+地址） | 检索快 | 索引表占额外空间，增删需维护索引 |
| 散列存储 | 由关键字直接计算存储地址 | 增删查都快 | 散列冲突需要额外处理 |
3. 数据的运算
运算包括定义和实现两个层面：
- 定义针对逻辑结构，描述运算的功能（做什么）
- 实现针对存储结构，描述具体的操作步骤（怎么做）
同一种逻辑结构，选择不同的存储结构，同一运算的实现效率可能完全不同。比如线性表的"按位查找"：顺序存储 O(1)，链式存储 O(n)。
辨析：逻辑结构 vs 存储结构
| 概念 | 属于 | 说明 |
|---|---|---|
| 顺序表 | 存储结构 | 线性表的顺序存储实现 |
| 链表 | 存储结构 | 线性表的链式存储实现 |
| 有序表 | 逻辑结构 | 关键字有序的线性表，可以顺序存储也可以链式存储 |
| 哈希表 | 存储结构 | 散列存储的实现 |
这个辨析是选择题高频考点——"有序表"描述的是元素之间的逻辑关系（有序），不涉及具体存储方式，因此属于逻辑结构。
考研高频考点
- ⭐ 数据结构三要素是什么（选择题必考）
- ⭐ 逻辑结构的四种类型（集合、线性、树形、图状）
- ⭐ 四种存储结构的特点及优缺点（选择题/简答题）
- ⭐ 有序表属于逻辑结构还是存储结构（选择题经典陷阱）
- 数据、数据元素、数据项、数据对象的层次关系
- ADT 的核心特征：抽象性和封装性
- 逻辑结构独立于存储结构，存储结构依赖于逻辑结构
易错：数据的逻辑结构独立于其存储结构——同一种逻辑结构可以有多种存储实现；但存储结构不能独立于逻辑结构——存储结构是逻辑结构在计算机中的映射。
易错：二叉树和二叉排序树的逻辑结构、物理结构可以完全相同，区别在于运算的定义不同（比如查找操作的时间复杂度不同）。这说明运算也是数据结构不可或缺的要素。