# 数据结构的基本概念

> 本文出自 CodeBrick 408 数据结构讲义，原文：https://www.codebrick.tech/ds-blog/posts/intro/concepts
> 这是供 AI 阅读的纯文本版：公式为 LaTeX，流程图为 mermaid 源码，原文中的折叠内容已全部展开。
> 讲解或引用本文内容时，请一并给出上面的原文链接。

> 2026 大纲 **一、基本概念（一）数据结构的基本概念**。

## 数据结构到底在说什么

一堆数据摆在那里，光有值是不够用的。学生记录之间是"互不相干的一群"，还是"排成一队"，还是"分成上下级"，决定了你能对它们做什么、做得多快。**数据结构研究的就是这件事：元素之间有什么关系，这些关系怎么落到内存里，以及在这个前提下能做哪些操作。**

这三句话就是**三要素**：**逻辑结构**（元素之间是什么关系）、**存储结构**（这些关系怎么在内存里表示出来）、**数据的运算**（能做什么、怎么做）。三者缺一不可——少了任何一个，"数据结构"这个词都还没说完整。

```mermaid
flowchart TD
    A["数据结构 = 三要素"] --> B["逻辑结构：元素之间是什么关系"]
    A --> C["存储结构：这些关系怎么落到内存里"]
    A --> D["数据的运算：能做什么、怎么做"]
    B --> B1["集合：仅同属一个集合"]
    B --> B2["线性：一对一"]
    B --> B3["树形：一对多"]
    B --> B4["图状：多对多"]
    C --> C1["顺序存储：物理相邻表示逻辑相邻"]
    C --> C2["链式存储：指针指示逻辑关系"]
    C --> C3["索引存储：附加索引表 关键字+地址"]
    C --> C4["散列存储：由关键字直接算地址"]
    D --> D1["运算的定义：面向逻辑结构，说做什么"]
    D --> D2["运算的实现：面向存储结构，说怎么做"]
```

三者之间的关系是有方向的：逻辑结构决定"有哪些关系要表达"，存储结构决定"用什么手段表达"，运算的效率则是两者搭配出来的结果。

> 🔴 **依赖是单向的**：逻辑结构独立于存储结构——同一种逻辑关系，顺序存、链式存都行；但存储结构不能独立于逻辑结构——你得先知道要表达什么关系，才谈得上怎么表达。

后面每一章讲一种具体结构时，都是在把这三个格子一个个填满。

## 从数据到数据项

先把四个层层嵌套的术语理清楚，它们的区别全在"是集合还是成员、是整体还是部分"上：

| 术语 | 定义 | 与上一级的关系 | 示例 |
|---|---|---|---|
| 数据 | 能被计算机识别、存储、加工的符号总称 | —— | 数字、字符、图像、声音 |
| 数据对象 | **性质相同**的数据元素的集合 | ⊆ 数据（真正的集合包含）| 整数集、全体学生记录 |
| 数据元素 | 数据的**基本单位**，整体考虑与处理 | ∈ 数据对象（成员，不是子集）| 一条学生记录 |
| 数据项 | 构成数据元素的**最小单位**，不可分割 | 数据元素的组成成分（整体—部分）| 学号、姓名、性别 |

两个容易被改一个字就变错的说法：**"数据元素是数据的最小单位"是错的**，它是**基本**单位，最小单位是数据项；**"同一数据对象中所有元素具有相同特性"是对的**，但"相同特性"指的是所含数据项个数相同、对应类型一致，**不是值相同**。

## 三要素之一：逻辑结构

逻辑结构描述元素之间的逻辑关系，与怎么存无关。分类的依据只有一条：**数一数每个元素的直接前驱和直接后继各有几个。**

| 逻辑结构 | 直接前驱 | 直接后继 | 关系 | 例子 |
|---|---|---|---|---|
| 集合 | 无前驱后继的概念 | — | 仅"同属一个集合" | 判断某学生是否在本班 |
| 线性结构 | 至多 1 个 | 至多 1 个 | 一对一 | 线性表、栈、队列、串、数组 |
| 树形结构 | 至多 1 个（双亲）| 可有多个（孩子）| 一对多 | 二叉树、文件目录 |
| 图状（网状）结构 | 可有多个 | 可有多个 | 多对多 | 交通网、社交网 |

**为什么恰好是四类**：前驱与后继的个数各取"至多 1 个 / 可有多个"两档，组合出三种有意义的情形，再加上根本没有前后驱关系的集合，正好四类。

![一对多的树形结构：结点 1 有 3 个孩子、结点 7 有 2 个孩子，而每个结点向上只有唯一的双亲，这正是"至多 1 个直接前驱、可有多个直接后继"](/textbook-figs/yrk-text-ds-p4-0.jpg)

> 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版），p4

![多对多的图状结构：结点 6 同时与 1、2、4、5 相连，任何一条边都不区分"前"和"后"，所以前驱与后继的个数都不受限制](/textbook-figs/yrk-text-ds-p4-1.jpg)

> 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版），p4

还有一种更粗的二分法：**线性结构 / 非线性结构**，集合、树形、图状都归入非线性。两种分法不矛盾，只是粗细不同。要留神的是几个归类容易反过来的：

- **栈和队列是线性结构**。它们是"操作受限的线性表"——受限的是**运算**，不是元素之间的关系。
- **串是线性结构**，特殊之处只在于数据元素只能是一个字符。
- **数组是线性结构**，它是线性表的推广，元素本身又是一个线性表。二维数组不是"非线性"，"维"说的是下标个数，不是元素间关系的复杂度。
- **广义表**同样是线性表的推广，与数组的区别在于它的元素**不同构**：可以是单个元素，也可以是一张子表。

## 三要素之二：存储结构

存储结构（物理结构）是数据对象在计算机里的存储表示。存的时候有两样东西要落地：**每个元素的值**，以及**元素之间的逻辑关系**。后半句才是四种存储方法真正的分界线——它们的区别就是"用什么手段表达关系"。

| 存储方法 | 关系靠什么表达 | 存取方式 | 优点 | 代价 |
|---|---|---|---|---|
| 顺序存储 | 存储单元的**邻接位置** | 随机存取 | 存储密度为 1；按位序访问 $O(1)$ | 需连续空间；插删要移动大量元素 |
| 链式存储 | 附加的**指针** | 只能顺序存取 | 不要求连续空间；插删只改指针 | 指针占空间，密度小于 1；按位序访问 $O(n)$ |
| 索引存储 | 附加的**索引表** | 先查索引表再定位 | 检索快；索引表可常驻内存 | 索引表占空间；插删还要维护索引 |
| 散列存储 | 关键字与地址间的**函数** | 直接定址，随机存取 | 理想情况增删查都接近 $O(1)$ | 必然出现冲突，须设计冲突处理 |

**顺序存储**的地址是算出来的：$\text{Loc}(a_i)=\text{Loc}(a_1)+(i-1)\times L$（$L$ 为每个元素占用的存储单元数），所以支持随机存取。**链式存储**每个结点要额外存指针，于是引出一个量：

$$
\text{存储密度} = \frac{\text{结点中数据本身占用的存储量}}{\text{结点占用的存储总量}}
$$

顺序存储的存储密度为 1，链式恒小于 1。所以"链式更省空间"这句话要说清楚省的是什么——省的是**预先分配却没用上的空闲空间**，不是每个结点的空间；论单个结点，链式反而更费。

**索引存储**是在存元素的同时另建一张**索引表**，表里每一项叫索引项，一般形式是 $(\text{关键字},\ \text{地址})$，关键字是能唯一标识一个结点的那些数据项。按索引项的密度分两种：**稠密索引**给每个结点都建一个索引项，地址直接指出该结点的物理位置；**稀疏索引**让一组相邻结点共用一个索引项，地址指出的是**这一组的起始位置**，找到组之后还得在组内顺序找。稀疏索引的表小得多，代价是多一步组内查找——[分块查找](https://www.codebrick.tech/ds-blog/posts/search/block-search)就是稀疏索引的直接应用，[B 树](https://www.codebrick.tech/ds-blog/posts/search/b-tree)、B+ 树则是把索引做成多级、并让它随数据一起动态调整的结果。

**散列存储**根据关键字直接算出地址。它和索引存储的根本差别是：索引存储要**查一张表**，散列存储**算一个式子**，不需要表。代价是这个函数不可能是单射（关键字空间通常远大于地址空间），必然出现两个不同关键字算到同一个地址的情况——这就是冲突，所以散列存储天然要附带一套冲突处理方案。

最后一点常被忽略：**四种存储方法既可以单独使用，也可以组合使用。** 组合的例子后面会反复见到：

- **邻接表** = 顶点表用顺序存储 + 每个顶点的边表用链式存储；
- **索引顺序表**（分块查找的结构）= 索引表 + 各块内部顺序存储；
- **拉链法散列表** = 散列存储定位到桶 + 桶内链式存储。

所以"某某结构用的是哪种存储"这类问题，答案可以不止一个。

## 三要素之三：数据的运算

运算有两面：**定义**面向逻辑结构，说**做什么**（功能、参数、初始条件、结果）；**实现**面向存储结构，说**怎么做**。同一个逻辑结构换一种存储结构，同一个运算的效率会成对地此消彼长：

| 运算 | 顺序存储 | 链式存储 | 差别的来源 |
|---|---|---|---|
| 按位序取第 $i$ 个元素 | $O(1)$ | $O(n)$ | 顺序存储地址能直接算；链式只能从头指针一个个走 |
| 按值查找 | $O(n)$ | $O(n)$ | 两者都要逐个比较 |
| 在第 $i$ 个位置插入 | $O(n)$ | 已知前驱结点时 $O(1)$ | 顺序存储要整体后移；链式只改两个指针 |
| 删除第 $i$ 个元素 | $O(n)$ | 已知前驱结点时 $O(1)$ | 同上，方向相反 |

> 🔴 链式那两个 $O(1)$ 带着限定语"**已知前驱结点时**"。如果题目只给位序 $i$，你还得先花 $O(n)$ 走到第 $i-1$ 个结点，总代价仍是 $O(n)$。这张表用错，多半就是因为这个限定语被吃掉了。

运算是三要素里最容易被忘掉的一个，但它有时是唯一的区分依据：**普通二叉树和二叉排序树可以有完全相同的逻辑结构和存储结构**，把它们分开的只有运算的定义。

## 数据类型与抽象数据类型

**数据类型是一个值的集合，与定义在这个值集上的一组操作的总称**——注意值集和操作集是绑定成对的，不是两件事。它分成**原子类型**（值不可再分，如 `int`、指针）和**结构类型**（值可分解，如 `struct`、数组）。

**抽象数据类型（ADT）是用户定义的、表示应用问题的数学模型，以及定义在其上的一组操作的总称**，包含数据对象 $D$、关系的集合 $S$（即逻辑结构）、基本操作的集合 $P$（即运算的定义）三部分。它的核心是**信息隐藏**：使用者只需要知道能做什么操作、初始条件和结果，不需要知道怎么存、怎么实现。

把三者摆在一起，边界就清楚了：

| | 值集 | 关系（逻辑结构）| 运算的定义 | 存储结构 | 运算的实现 |
|---|---|---|---|---|---|
| 数据类型 | 语言预定义 | 隐含 | 语言预定义 | 语言/编译器决定 | 语言/编译器决定 |
| 抽象数据类型 | 用户定义 | 用户定义 | 用户定义 | ❌ 不含 | ❌ 不含 |
| 数据结构 | ✅ | ✅ | ✅ | ✅ | ✅ |

一句话：**ADT = 逻辑结构 + 运算的定义**，不含存储结构和实现；而数据类型与 ADT 的差别在于**谁来定义**。

**〔原文中此段为可折叠内容〕ADT 的书写格式与一份完整示例（要自己动手写 ADT 时再展开）**


书写格式是固定的：

```text
ADT 抽象数据类型名 {
    数据对象：<数据对象的定义>
    数据关系：<数据关系的定义>
    基本操作：<基本操作的定义>
} ADT 抽象数据类型名
```

其中数据对象与数据关系用数学符号加自然语言描述；每个基本操作的格式是：

```text
基本操作名(参数表)
    初始条件：<初始条件描述>
    操作结果：<操作结果描述>
```

两个约定必须记住：

- **参数分两种**：**赋值参数**只为操作提供输入值；**引用参数**以 `&` 打头，除了提供输入值，
  还要**带回操作结果**。看到 `&L` 就意味着这个操作会改变 `L` 本身。
- **"初始条件"描述操作执行之前数据结构和参数必须满足的条件**，为空时可以省略；
  **"操作结果"说明操作正常完成后数据结构的变化和返回值**。

照着格式写一个「有序表」的 ADT：

```text
ADT OrderedList {
    数据对象：D = { aᵢ | aᵢ ∈ ElemType, i = 1, 2, …, n, n ≥ 0 }
    数据关系：R = { <aᵢ₋₁, aᵢ> | aᵢ₋₁, aᵢ ∈ D, i = 2, …, n }
              且对任意 i (2 ≤ i ≤ n) 有 aᵢ₋₁ ≤ aᵢ        // 非递减有序
    基本操作：
        InitList(&L)
            操作结果：构造一个空的有序表 L。
        ListLength(L)
            初始条件：有序表 L 已存在。
            操作结果：返回 L 中数据元素的个数。
        Insert(&L, e)
            初始条件：有序表 L 已存在。
            操作结果：把 e 插入到 L 中恰当的位置，使 L 仍保持非递减有序，表长加 1。
        Search(L, k)
            初始条件：有序表 L 已存在。
            操作结果：若 L 中存在关键字等于 k 的元素，返回它的位序；否则返回 0。
        Delete(&L, i, &e)
            初始条件：有序表 L 已存在，且 1 ≤ i ≤ ListLength(L)。
            操作结果：删除 L 的第 i 个元素，用 e 返回其值，表长减 1。
        DestroyList(&L)
            初始条件：有序表 L 已存在。
            操作结果：销毁有序表 L。
} ADT OrderedList
```

**这份定义里没有一个字提到数组、指针、下标或结点**——这就是"抽象"的准确含义。正因为如此，
它既可以用顺序表实现（`Search` 用折半查找，$O(\log n)$；`Insert` 要移动元素，$O(n)$），
也可以用有序单链表实现（`Search` 只能顺序找，$O(n)$；`Insert` 找到位置后只改指针）。
**换实现不用改 ADT 定义，这就是封装带来的好处。**

自己写时最容易漏的两处：一是**数据关系里忘了写约束**（上面的 $a_{i-1} \le a_i$ 是"有序"这个
词的全部内容，漏了它就成了普通线性表）；二是**忘了标 `&`**（`Insert(&L, e)` 要改 $L$，
而 `Search(L, k)` 不改，两者的参数写法必须不同）。

## 判断一个名词属于哪一层

这一节最实用的东西是一条判据，可以直接套：**换一种存储方式，这句话还成立吗？成立就是逻辑层，不成立就是存储层。**

| 名词 | 套判据 | 结论 |
|---|---|---|
| 有序表 | "按关键字非递减排列"顺序存、链式存都成立 | **逻辑结构**（带约束的线性结构）|
| 顺序表 | "顺序"就是指顺序存储方法 | **存储结构** |
| 链表 | "用指针表示逻辑关系"本身就是存储方法 | **存储结构** |
| 哈希表 | "由关键字算地址"就是散列存储方法 | **存储结构** |
| 栈、队列 | "只能在一端进出"限制的是**运算**，顺序栈和链栈都满足 | **逻辑结构**（受限的线性结构）|
| 循环队列 | 指"用数组首尾相接实现队列"，是一种顺序实现 | **存储结构** |
| 二叉排序树 | "左小右大"与怎么存无关，两种存法都成立 | **逻辑结构** |

## 考点速记

**这一节不单独成题。** 它给出的是判断依据，兑现的地方在后面每一章——判断某个名词属于逻辑层还是存储层、某个复杂度差别的来源是存储方法还是运算定义、某种结构能不能换一种存法。所以这一节不用背，要能用。

三条会被反复调用的结论：

1. **三要素缺一不可**——普通二叉树与二叉排序树可以有完全相同的逻辑结构和存储结构，区分它们的只有**运算的定义**。
2. **逻辑结构独立于存储结构，存储结构不能独立于逻辑结构**——同一逻辑结构换存储方法得到不同的存储结构，同一存储方法也能实现不同的逻辑结构。
3. **ADT 只有逻辑结构和运算的定义**，不含存储结构与实现——这是它与数据结构最实质的差别。

> **易错**：**有序表 vs 顺序表。**"有序"修饰的是**关系**，"顺序"修饰的是**存储方法**。所以有序表可以用链表实现，顺序表也可以是无序的——两个词不在同一层。

> **易错**：**顺序存储 vs 顺序存取。** 一个说"怎么放"，一个说"怎么取"，而且结论正好反直觉：顺序**存储**支持的是**随机存取**（严蔚敏 p23："线性表的顺序存储结构是一种随机存取的存储结构"）；顺序**存取**指的是必须从头逐个走，那是链式的性质。

> **易错**：**数据元素是数据的"基本单位"，不是"最小单位"。** 最小单位是数据项。这两个词换一个字，结论就反了。

**〔原文中此段为可折叠内容〕教材出处**


- 严蔚敏《数据结构（C 语言版）》（第 2 版），p4：数据结构的定义
  （"相互之间存在一种或多种特定关系的数据元素的集合"）、逻辑结构与存储结构两个层次、
  四类基本逻辑结构（集合、线性、树、图）及其对应的一对一/一对多/多对多关系。
- 同书 p5：线性结构的推广（栈、串、数组、广义表）与非线性结构的层次划分；存储结构（物理结构）
  的定义与顺序存储、链式存储两种基本方法。
- 同书 p6：数据类型的定义（"一个值的集合和定义在这个值集上的一组操作的总称"）。
- 同书 p7、p9~p10：抽象数据类型的三部分（数据对象、数据对象上关系的集合、基本操作的集合）、
  ADT 的书写格式、赋值参数与引用参数的约定、以及一个完整的 ADT 定义—表示—实现示例。
- 同书 p16：本章小结中"逻辑结构与数据的存储无关""同一逻辑结构采用不同的存储方法可以得到不同
  的存储结构"两条结论。
- 殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版），p6：**四种基本存储方法**
  （顺序、链接、索引、散列）的完整定义，包括索引项的一般形式 $(\text{关键码},\ \text{地址})$、
  稠密索引与稀疏索引的区别，以及"四种存储方法既可单独使用也可组合使用"；原子类型与结构类型
  的划分（与前者同页）。
- 同书 p4：本篇引用的树形结构图（图 1.6）与图状结构图（图 1.7）。

## 相关知识

[算法和算法评价](https://www.codebrick.tech/ds-blog/posts/intro/complexity)｜[线性表基本概念](https://www.codebrick.tech/ds-blog/posts/linear/concepts)｜
[栈和队列的基本概念](https://www.codebrick.tech/ds-blog/posts/stack-queue/concepts)｜[串的基本概念](https://www.codebrick.tech/ds-blog/posts/string/concepts)｜
[树的基本概念](https://www.codebrick.tech/ds-blog/posts/tree/concepts)｜[图的基本概念](https://www.codebrick.tech/ds-blog/posts/graph/concepts)｜
[线性表的顺序存储](https://www.codebrick.tech/ds-blog/posts/linear/sequential-list)｜[单链表](https://www.codebrick.tech/ds-blog/posts/linear/singly-linked-list)｜
[分块查找](https://www.codebrick.tech/ds-blog/posts/search/block-search)｜[B 树](https://www.codebrick.tech/ds-blog/posts/search/b-tree)｜
[散列表（拉链法）](https://www.codebrick.tech/ds-blog/posts/search/hash-chaining)｜[查找的基本概念](https://www.codebrick.tech/ds-blog/posts/search/concepts)｜
[排序的基本概念](https://www.codebrick.tech/ds-blog/posts/sorting/concepts)


## 真题练习