数据结构导论（02142） · 基本概念与复杂度至树与二叉树

返回分篇目录

学习顺序是：先分清逻辑结构与存储方式，再学习线性表、栈队列、树和图，最后比较查找与排序。每一类结构都按“表示 → 操作 → 复杂度 → 选择条件”理解，算法实现可继续读对应手册。

数据结构导论（02142）

基本概念与复杂度

数据、结构与操作

数据元素是处理的基本单位，数据项是元素中有意义的组成部分。逻辑结构描述元素之间的关系：集合、线性、树形、图；存储结构描述这些关系如何落在内存中：顺序、链式、索引、散列。

同一逻辑结构可以有不同存储实现，例如线性表可用数组或链表。读取、查找属于不改变结构的引用操作；插入、删除会改变结构，修改元素值也不是纯读取。不能因为它们都属于“基本运算”就归成同一类。

算法用明确、可执行且有限的步骤求解问题，允许零个或多个输入，产生输出。正确性、可读性、健壮性和效率是不同检查维度。

分析时间与辅助空间

常见增长量级为 O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2^n)。复杂度取决于实际执行次数，不是简单数循环层数：折半循环是对数级，嵌套循环也可能具有相互受限的范围。

辅助空间关注为算法额外申请的变量、容器和递归栈，与输入本身占用空间区分。分析时说明平均、最好还是最坏情况，不能把平均界写成所有输入的保证。

线性表：顺序存储与链式存储

顺序表的读取、插入与删除

线性表是有限序列，除两端外每个元素有唯一直接前驱和后继。顺序表用连续存储单元表示，支持按下标访问；元素大小 L、首地址 d，按一基位置编号时：LOC(aᵢ) = d + (i−1)L。

长度为 n 的表，在第 i 个位置插入需要后移 n−i+1 个元素；删除第 i 个元素后需要前移 n−i 个元素。末尾追加/删除无需移动其他元素，但追加仍可能触发扩容。

text

初始：[10, 20, 30]
第2个位置插入15：先后移30、20，再写入15 → [10, 15, 20, 30]
删除第2个元素：前移20、30，再减少长度 → [10, 20, 30]

移动元素前先校验位置和容量，不能在移动过程中覆盖尚未保存的元素。

单链表与双向链表

图中q被插入p与r之间。必须先让q保留原后继r，再改p的连接；如果是双向链表，还要同步更新反向指针。

查看图表代码

链表节点用数据域与指针表达逻辑相邻关系，物理位置可以不连续。单链表保存后继，双向链表另存前驱；循环链表的尾部连接回头节点或首节点，具体形式必须与实现约定一致。

已知前驱 p，插入节点 q 的关键顺序是先保存后继，再改 p 的连接：

text

q.next = p.next
p.next = q

删除 p 的后继时，先保存被删节点，再连接并释放；同时处理头、尾、空表及单节点边界。双向链表还需同步修改另一方向的连接，不能只改 next。

如何选择与比较复杂度

操作或条件	顺序表	单链表
按位置读取	`O(1)`	`O(n)`
未建立额外索引的按值查找	`O(n)`	`O(n)`
已知位置插入/删除	通常移动 `O(n)` 个元素	已知前驱时连接修改 `O(1)`；找前驱仍可能 `O(n)`
空间	数据连续，可能预留容量	节点分散，需要指针与分配开销

顺序表不只限于静态分配，也可动态扩容；链表也并非“有空闲内存就一定分配成功”。存储密度是数据域占用与整个节点占用之比，比较时还要考虑容量浪费、对齐和缓存局部性。

栈、队列与数组

栈：后进先出

栈只在栈顶插入和删除，push 入栈、pop 出栈，规则为 后进先出（LIFO）。递归调用、括号匹配、撤销等场景会使用栈式顺序。顺序栈要检查容量，链栈要检查空栈与分配失败。

原笔记把 LIFO 写成“先进先出”是混淆；按 A、B、C 入栈，未穿插其他操作时弹出次序应为 C、B、A。

队列与循环队列

容量4、保留一个空槽的队列最多装3项。下图只画数组槽位的回绕关系，当前是否为空或满还要结合front、rear判断。

查看图表代码

队列从队尾插入、队头删除，为 先进先出（FIFO）。A、B、C 依次入队，出队仍为 A、B、C。顺序队列若只递增下标，会出现前端空间不能复用的“假溢出”。

循环队列用取模回绕。若数组容量为 m、约定空出一个位置、front 指向队头、rear 指向下次写入处：

空：front == rear。
满：(rear + 1) % m == front。
入队后：rear = (rear + 1) % m。
出队后：front = (front + 1) % m。

这种实现最多存 m−1 个元素；如果采用计数器或满标记，满空公式会不同。链队列要同步维护头尾指针，尤其最后一个元素出队时。

多维数组与矩阵压缩

数组按索引访问；二维数组采用行优先、零基下标、每元素 k 字节时，LOC(a[i][j]) = base + (i × 列数 + j) × k。更换下界或存储顺序后需调整公式。

对称、三角矩阵可利用结构少存重复元素；稀疏矩阵按行列位置保存非零项。压缩不是“所有非零只分配一个空间”，而是用索引或规则重建未显式保存的项，访问成本也会变化。

树与二叉树

术语、性质与存储

树是递归结构，根以外的节点有唯一父节点；叶子没有孩子，节点的度是孩子数，树的度是最大节点度。约定根为第 1 层时，高度是最大层数。

二叉树区分左右子树，每个节点至多两个孩子；不要求每个节点都有两个孩子。常用性质：

第 i 层最多 2^(i−1) 个节点。
高度 k 最多 2^k−1 个节点。
非空二叉树的叶子数 n₀ = n₂ + 1，n₂ 为有两个孩子的节点数。
满二叉树每层填满；完全二叉树除最后一层外填满，最后一层从左连续排列。

数组存储适合完全二叉树等布局，一基编号时节点 i 的孩子为 2i、2i+1；倾斜树可能浪费大量数组位置。链式结构保存左右孩子指针，操作时仍需维护正确关系。

先序、中序、后序与层序遍历

查看图表代码

遍历	规则	此图结果
先序	根、左、右	`A B D E C F G`
中序	左、根、右	`D B E A F C G`
后序	左、右、根	`D E B F G C A`
层序	按层从左到右	`A B C D E F G`

深度遍历可用递归或显式栈，层序常用队列。每个节点访问一次通常为 O(n)；递归辅助空间取决于高度，不能一律写 O(log n)。

实现对照见树的四种遍历。

一般树、森林与哈夫曼树

权值1、2、4先合并最小的1与2得到3，再合并3与4得到7。叶子权值乘深度的总和为1×2+2×2+4×1=10；每次选择的是当前森林最小两棵，合并节点也要重新参与选择。

查看图表代码

一般树可用双亲数组、孩子链表或孩子—兄弟结构表示。孩子—兄弟表示中，左指针对应第一个孩子，右指针对应下一个兄弟；森林可把各树根视作兄弟连接。理解指针含义比记“旋转 45 度”更可靠。

一般树有先根、后根和层序遍历；不能未经定义就把二叉树中序直接移植为一般树中序。

哈夫曼树用于使带权路径长度最小：从权值森林中反复选最小两棵，合并为权值之和的新树，直到只剩一棵。按边赋予 0/1 得到前缀编码；相同权值可能产生不同树与编码，但总带权路径长度相同。

数据结构导论（02142） · 基本概念与复杂度至树与二叉树 ​