Appearance
数据结构的基本概念
2026 大纲 一、基本概念（一）数据结构的基本概念。
数据结构到底在说什么
一堆数据摆在那里，光有值是不够用的。学生记录之间是"互不相干的一群"，还是"排成一队"，还是"分成上下级"，决定了你能对它们做什么、做得多快。数据结构研究的就是这件事：元素之间有什么关系，这些关系怎么落到内存里，以及在这个前提下能做哪些操作。
这三句话就是三要素：逻辑结构（元素之间是什么关系）、存储结构（这些关系怎么在内存里表示出来）、数据的运算（能做什么、怎么做）。三者缺一不可——少了任何一个，"数据结构"这个词都还没说完整。
三者之间的关系是有方向的：逻辑结构决定"有哪些关系要表达"，存储结构决定"用什么手段表达"，运算的效率则是两者搭配出来的结果。
🔴 依赖是单向的：逻辑结构独立于存储结构——同一种逻辑关系，顺序存、链式存都行；但存储结构不能独立于逻辑结构——你得先知道要表达什么关系，才谈得上怎么表达。
后面每一章讲一种具体结构时，都是在把这三个格子一个个填满。
从数据到数据项
先把四个层层嵌套的术语理清楚，它们的区别全在"是集合还是成员、是整体还是部分"上：
| 术语 | 定义 | 与上一级的关系 | 示例 |
|---|---|---|---|
| 数据 | 能被计算机识别、存储、加工的符号总称 | —— | 数字、字符、图像、声音 |
| 数据对象 | 性质相同的数据元素的集合 | ⊆ 数据（真正的集合包含） | 整数集、全体学生记录 |
| 数据元素 | 数据的基本单位，整体考虑与处理 | ∈ 数据对象（成员，不是子集） | 一条学生记录 |
| 数据项 | 构成数据元素的最小单位，不可分割 | 数据元素的组成成分（整体—部分） | 学号、姓名、性别 |
两个容易被改一个字就变错的说法："数据元素是数据的最小单位"是错的，它是基本单位，最小单位是数据项；"同一数据对象中所有元素具有相同特性"是对的，但"相同特性"指的是所含数据项个数相同、对应类型一致，不是值相同。
三要素之一：逻辑结构
逻辑结构描述元素之间的逻辑关系，与怎么存无关。分类的依据只有一条：数一数每个元素的直接前驱和直接后继各有几个。
| 逻辑结构 | 直接前驱 | 直接后继 | 关系 | 例子 |
|---|---|---|---|---|
| 集合 | 无前驱后继的概念 | — | 仅"同属一个集合" | 判断某学生是否在本班 |
| 线性结构 | 至多 1 个 | 至多 1 个 | 一对一 | 线性表、栈、队列、串、数组 |
| 树形结构 | 至多 1 个（双亲） | 可有多个（孩子） | 一对多 | 二叉树、文件目录 |
| 图状（网状）结构 | 可有多个 | 可有多个 | 多对多 | 交通网、社交网 |
为什么恰好是四类：前驱与后继的个数各取"至多 1 个 / 可有多个"两档，组合出三种有意义的情形，再加上根本没有前后驱关系的集合，正好四类。
图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版），p4
图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版），p4
还有一种更粗的二分法：线性结构 / 非线性结构，集合、树形、图状都归入非线性。两种分法不矛盾，只是粗细不同。要留神的是几个归类容易反过来的：
- 栈和队列是线性结构。它们是"操作受限的线性表"——受限的是运算，不是元素之间的关系。
- 串是线性结构，特殊之处只在于数据元素只能是一个字符。
- 数组是线性结构，它是线性表的推广，元素本身又是一个线性表。二维数组不是"非线性"，"维"说的是下标个数，不是元素间关系的复杂度。
- 广义表同样是线性表的推广，与数组的区别在于它的元素不同构：可以是单个元素，也可以是一张子表。
三要素之二：存储结构
存储结构（物理结构）是数据对象在计算机里的存储表示。存的时候有两样东西要落地：每个元素的值，以及元素之间的逻辑关系。后半句才是四种存储方法真正的分界线——它们的区别就是"用什么手段表达关系"。
| 存储方法 | 关系靠什么表达 | 存取方式 | 优点 | 代价 |
|---|---|---|---|---|
| 顺序存储 | 存储单元的邻接位置 | 随机存取 | 存储密度为 1；按位序访问 | 需连续空间；插删要移动大量元素 |
| 链式存储 | 附加的指针 | 只能顺序存取 | 不要求连续空间；插删只改指针 | 指针占空间，密度小于 1；按位序访问 |
| 索引存储 | 附加的索引表 | 先查索引表再定位 | 检索快；索引表可常驻内存 | 索引表占空间；插删还要维护索引 |
| 散列存储 | 关键字与地址间的函数 | 直接定址，随机存取 | 理想情况增删查都接近 | 必然出现冲突，须设计冲突处理 |
顺序存储的地址是算出来的：
顺序存储的存储密度为 1，链式恒小于 1。所以"链式更省空间"这句话要说清楚省的是什么——省的是预先分配却没用上的空闲空间，不是每个结点的空间；论单个结点，链式反而更费。
索引存储是在存元素的同时另建一张索引表，表里每一项叫索引项，一般形式是
散列存储根据关键字直接算出地址。它和索引存储的根本差别是：索引存储要查一张表，散列存储算一个式子，不需要表。代价是这个函数不可能是单射（关键字空间通常远大于地址空间），必然出现两个不同关键字算到同一个地址的情况——这就是冲突，所以散列存储天然要附带一套冲突处理方案。
最后一点常被忽略：四种存储方法既可以单独使用，也可以组合使用。 组合的例子后面会反复见到：
- 邻接表 = 顶点表用顺序存储 + 每个顶点的边表用链式存储；
- 索引顺序表（分块查找的结构）= 索引表 + 各块内部顺序存储；
- 拉链法散列表 = 散列存储定位到桶 + 桶内链式存储。
所以"某某结构用的是哪种存储"这类问题，答案可以不止一个。
三要素之三：数据的运算
运算有两面：定义面向逻辑结构，说做什么（功能、参数、初始条件、结果）；实现面向存储结构，说怎么做。同一个逻辑结构换一种存储结构，同一个运算的效率会成对地此消彼长：
| 运算 | 顺序存储 | 链式存储 | 差别的来源 |
|---|---|---|---|
| 按位序取第 | 顺序存储地址能直接算；链式只能从头指针一个个走 | ||
| 按值查找 | 两者都要逐个比较 | ||
| 在第 | 已知前驱结点时 | 顺序存储要整体后移；链式只改两个指针 | |
| 删除第 | 已知前驱结点时 | 同上，方向相反 |
🔴 链式那两个
带着限定语"已知前驱结点时"。如果题目只给位序 ，你还得先花 走到第 个结点，总代价仍是 。这张表用错，多半就是因为这个限定语被吃掉了。
运算是三要素里最容易被忘掉的一个，但它有时是唯一的区分依据：普通二叉树和二叉排序树可以有完全相同的逻辑结构和存储结构，把它们分开的只有运算的定义。
数据类型与抽象数据类型
数据类型是一个值的集合，与定义在这个值集上的一组操作的总称——注意值集和操作集是绑定成对的，不是两件事。它分成原子类型（值不可再分，如 int、指针）和结构类型（值可分解，如 struct、数组）。
抽象数据类型（ADT）是用户定义的、表示应用问题的数学模型，以及定义在其上的一组操作的总称，包含数据对象
把三者摆在一起，边界就清楚了：
| 值集 | 关系（逻辑结构） | 运算的定义 | 存储结构 | 运算的实现 | |
|---|---|---|---|---|---|
| 数据类型 | 语言预定义 | 隐含 | 语言预定义 | 语言/编译器决定 | 语言/编译器决定 |
| 抽象数据类型 | 用户定义 | 用户定义 | 用户定义 | ❌ 不含 | ❌ 不含 |
| 数据结构 | ✅ | ✅ | ✅ | ✅ | ✅ |
一句话：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 用折半查找，Insert 要移动元素，Search 只能顺序找，Insert 找到位置后只改指针）。 换实现不用改 ADT 定义，这就是封装带来的好处。
自己写时最容易漏的两处：一是数据关系里忘了写约束（上面的 &（Insert(&L, e) 要改 Search(L, k) 不改，两者的参数写法必须不同）。
判断一个名词属于哪一层
这一节最实用的东西是一条判据，可以直接套：换一种存储方式，这句话还成立吗？成立就是逻辑层，不成立就是存储层。
| 名词 | 套判据 | 结论 |
|---|---|---|
| 有序表 | "按关键字非递减排列"顺序存、链式存都成立 | 逻辑结构（带约束的线性结构） |
| 顺序表 | "顺序"就是指顺序存储方法 | 存储结构 |
| 链表 | "用指针表示逻辑关系"本身就是存储方法 | 存储结构 |
| 哈希表 | "由关键字算地址"就是散列存储方法 | 存储结构 |
| 栈、队列 | "只能在一端进出"限制的是运算，顺序栈和链栈都满足 | 逻辑结构（受限的线性结构） |
| 循环队列 | 指"用数组首尾相接实现队列"，是一种顺序实现 | 存储结构 |
| 二叉排序树 | "左小右大"与怎么存无关，两种存法都成立 | 逻辑结构 |
考点速记
这一节不单独成题。 它给出的是判断依据，兑现的地方在后面每一章——判断某个名词属于逻辑层还是存储层、某个复杂度差别的来源是存储方法还是运算定义、某种结构能不能换一种存法。所以这一节不用背，要能用。
三条会被反复调用的结论：
- 三要素缺一不可——普通二叉树与二叉排序树可以有完全相同的逻辑结构和存储结构，区分它们的只有运算的定义。
- 逻辑结构独立于存储结构，存储结构不能独立于逻辑结构——同一逻辑结构换存储方法得到不同的存储结构，同一存储方法也能实现不同的逻辑结构。
- ADT 只有逻辑结构和运算的定义，不含存储结构与实现——这是它与数据结构最实质的差别。
易错：有序表 vs 顺序表。"有序"修饰的是关系，"顺序"修饰的是存储方法。所以有序表可以用链表实现，顺序表也可以是无序的——两个词不在同一层。
易错：顺序存储 vs 顺序存取。 一个说"怎么放"，一个说"怎么取"，而且结论正好反直觉：顺序存储支持的是随机存取（严蔚敏 p23："线性表的顺序存储结构是一种随机存取的存储结构"）；顺序存取指的是必须从头逐个走，那是链式的性质。
易错：数据元素是数据的"基本单位"，不是"最小单位"。 最小单位是数据项。这两个词换一个字，结论就反了。
教材出处
- 严蔚敏《数据结构（C 语言版）》（第 2 版），p4：数据结构的定义 （"相互之间存在一种或多种特定关系的数据元素的集合"）、逻辑结构与存储结构两个层次、 四类基本逻辑结构（集合、线性、树、图）及其对应的一对一/一对多/多对多关系。
- 同书 p5：线性结构的推广（栈、串、数组、广义表）与非线性结构的层次划分；存储结构（物理结构） 的定义与顺序存储、链式存储两种基本方法。
- 同书 p6：数据类型的定义（"一个值的集合和定义在这个值集上的一组操作的总称"）。
- 同书 p7、p9~p10：抽象数据类型的三部分（数据对象、数据对象上关系的集合、基本操作的集合）、 ADT 的书写格式、赋值参数与引用参数的约定、以及一个完整的 ADT 定义—表示—实现示例。
- 同书 p16：本章小结中"逻辑结构与数据的存储无关""同一逻辑结构采用不同的存储方法可以得到不同 的存储结构"两条结论。
- 殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版），p6：四种基本存储方法 （顺序、链接、索引、散列）的完整定义，包括索引项的一般形式
、 稠密索引与稀疏索引的区别，以及"四种存储方法既可单独使用也可组合使用"；原子类型与结构类型 的划分（与前者同页）。 - 同书 p4：本篇引用的树形结构图（图 1.6）与图状结构图（图 1.7）。
相关知识
算法和算法评价｜线性表基本概念｜ 栈和队列的基本概念｜串的基本概念｜ 树的基本概念｜图的基本概念｜ 线性表的顺序存储｜单链表｜ 分块查找｜B 树｜ 散列表（拉链法）｜查找的基本概念｜ 排序的基本概念