第10章基本数据结构

导读

数据结构是算法的基础。选择合适的数据结构可以显著提高算法的效率。本章将介绍几种基本的数据结构：栈、队列、链表和有根树。这些数据结构虽然简单，但它们是构建更复杂数据结构（如堆、平衡树、图等）的基石。

我们将详细讨论每种数据结构的定义、操作、实现方式以及典型应用。理解这些基本数据结构的特性和操作，是学习高级数据结构和算法的前提。

核心概念详解

10.1 栈

定义：

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。只允许在一端（栈顶）进行插入和删除操作。

基本操作：

PUSH(S, x)：将元素x压入栈S，O(1)
POP(S)：弹出并返回栈顶元素，O(1)
PEEK(S)：返回栈顶元素但不弹出，O(1)
IS-EMPTY(S)：判断栈是否为空，O(1)

数组实现：

STACK-INIT(n)
    创建数组S[1..n]
    S.top = 0

PUSH(S, x)
    S.top = S.top + 1
    S[S.top] = x

POP(S)
    if STACK-EMPTY(S)
        error "underflow"
    S.top = S.top - 1
    return S[S.top + 1]

应用：

函数调用栈
表达式求值（后缀表达式）
括号匹配
深度优先搜索
浏览器历史记录

10.2 队列

定义：

队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构。在一端（队尾）插入，在另一端（队头）删除。

基本操作：

ENQUEUE(Q, x)：将元素x加入队尾，O(1)
DEQUEUE(Q)：移除并返回队头元素，O(1)
PEEK(Q)：返回队头元素但不移除，O(1)
IS-EMPTY(Q)：判断队列是否为空，O(1)

数组实现（循环队列）：

ENQUEUE(Q, x)
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
    else
        Q.tail = Q.tail + 1

DEQUEUE(Q)
    x = Q[Q.head]
    if Q.head == Q.length
        Q.head = 1
    else
        Q.head = Q.head + 1
    return x

应用：

广度优先搜索
任务调度
缓冲区
消息队列
打印队列

10.3 链表

定义：

链表（Linked List）是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

类型：

单链表：每个节点有next指针
双链表：每个节点有prev和next指针
循环链表：最后一个节点指向第一个节点

基本操作（单链表）：

LIST-SEARCH(L, k)：查找关键字为k的元素，O(n)
LIST-INSERT(L, x)：在链表头部插入x，O(1)
LIST-DELETE(L, x)：删除x，O(n)（需要先找到x）

哨兵节点：

哨兵（Sentinel）是一个虚拟节点，简化边界条件处理。

头哨兵：简化头部插入/删除
尾哨兵：简化尾部操作

双链表的插入：

LIST-INSERT'(L, x)
    x.next = L.head
    if L.head ≠ NIL
        L.head.prev = x
    L.head = x
    x.prev = NIL

双链表的删除：

LIST-DELETE'(L, x)
    if x.prev ≠ NIL
        x.prev.next = x.next
    else
        L.head = x.next
    if x.next ≠ NIL
        x.next.prev = x.prev

应用：

实现栈和队列
LRU缓存
多项式表示
稀疏矩阵
内存管理（空闲链表）

10.4 有根树

定义：

有根树（Rooted Tree）是一种层次数据结构，由节点和边组成，有一个特殊的根节点。

术语：

根（Root）：树的顶层节点
父节点（Parent）：直接上级节点
子节点（Child）：直接下级节点
叶子节点（Leaf）：没有子节点的节点
深度（Depth）：从根到节点的路径长度
高度（Height）：从节点到最深叶子的路径长度
度（Degree）：子节点的个数

树的表示：

二叉树：

每个节点最多有两个子节点（左子节点和右子节点）。

struct Node {
    key: value
    left: Node
    right: Node
    parent: Node
}

左孩子-右兄弟表示法：

适用于任意度的树。每个节点有：

第一个子节点（left-child）
下一个兄弟节点（right-sibling）

struct Node {
    key: value
    left-child: Node
    right-sibling: Node
    parent: Node
}

10.5 树的遍历

深度优先遍历（DFS）：

前序遍历（Preorder）：根-左-右
中序遍历（Inorder）：左-根-右
后序遍历（Postorder）：左-右-根

广度优先遍历（BFS）：

层序遍历：按层从上到下，每层从左到右

遍历的应用：

前序：复制树、表达式前缀表示
中序：二叉搜索树的有序遍历
后序：删除树、表达式后缀表示
层序：最短路径、层级处理

10.6 指针和对象的实现

在高级语言中，指针和对象的使用方式不同：

显式指针：

C/C++：直接使用内存地址
需要手动管理内存

对象引用：

Java/Python：使用对象引用
自动垃圾回收

数组模拟指针：

用数组下标代替指针
适用于某些特殊场景（如持久化数据结构）

10.7 数据结构的选择

选择数据结构需要考虑：

操作频率：哪些操作最频繁？
数据规模：数据量多大？
访问模式：随机访问还是顺序访问？
空间限制：内存是否充足？

决策指南：

需要后进先出：栈
需要先进先出：队列
需要频繁插入/删除：链表
需要快速查找：哈希表或搜索树
需要层次关系：树

10.8 栈和队列的变体

双端队列（Deque）：

两端都可以插入和删除
可以用栈或链表实现

优先队列：

按优先级出队
通常用堆实现

最小栈：

支持O(1)获取最小值
使用辅助栈记录历史最小值

10.9 链表的变体

跳表（Skip List）：

多层链表，实现O(log n)查找
随机化数据结构

自组织链表：

移动到头（Move-to-Front）
转置（Transpose）

展开树（Splay Tree）：

自调整的搜索树
基于链表思想的树结构

重要知识点

知识点1：栈和队列的对偶性

栈和队列是对偶的数据结构：

栈：LIFO
队列：FIFO
可以用两个栈实现队列
可以用两个队列实现栈

知识点2：链表的优缺点

链表的优势：

动态大小
高效插入/删除（已知位置时）
不需要连续内存

链表的劣势：

不支持随机访问
额外的指针开销
缓存不友好

知识点3：树的递归性质

树天然适合递归处理：

子树是独立的子问题
递归遍历简洁优雅
分治策略的自然载体

知识点4：哨兵节点的简化作用

哨兵节点可以消除边界条件检查，简化代码：

空链表不需要特殊处理
头部/尾部操作统一
减少条件分支

知识点5：数据结构的组合

复杂数据结构通常是基本数据结构的组合：

堆 = 数组 + 完全二叉树
哈希表 = 数组 + 链表
图 = 邻接表（数组 + 链表）

常见误区

误区1：链表总是比数组好

链表的优势在于动态大小和高效插入/删除，但数组在随机访问和缓存友好性方面更优。选择取决于具体需求。

误区2：栈只能用于函数调用

栈的应用远不止函数调用。表达式求值、括号匹配、DFS等都是栈的重要应用。

误区3：树只能是二叉树

树可以有任意数量的子节点。左孩子-右兄弟表示法可以处理任意度的树。

误区4：队列不能用数组实现

循环队列使用数组高效实现了队列。关键是正确处理头尾指针的回绕。

误区5：所有树操作都需要递归

虽然递归是处理树的自然方式，但迭代方式（使用显式栈）也是可行的，且在某些场景下更高效。

实践应用

应用1：编译器中的栈

编译器使用栈进行：

语法分析（递归下降）
表达式求值
作用域管理
寄存器分配

应用2：操作系统中的队列

操作系统使用队列进行：

进程调度（就绪队列）
I/O请求队列
网络数据包缓冲

应用3：数据库中的B树

B树是数据库索引的核心数据结构：

多叉平衡搜索树
支持高效的范围查询
适合磁盘存储

应用4：文件系统

文件系统使用树结构组织：

目录树
文件路径
权限继承

应用5：网络路由

路由表使用树结构：

前缀树（Trie）
最长前缀匹配
高效路由查找

10.10 栈的深度应用：表达式求值

栈在编译器中用于表达式求值，这是一个经典应用。

中缀表达式转后缀表达式（调度场算法）：

中缀表达式如 3 + 4 * 2 对人类直观，但对计算机不友好。后缀表达式（逆波兰表示法）3 4 2 * + 更容易用栈求值。

转换算法使用一个运算符栈：

遇到操作数，直接输出

遇到左括号，压入栈

遇到右括号，弹出并输出直到左括号

遇到运算符，弹出优先级≥当前运算符的所有运算符，然后压入当前运算符

表达式结束时，弹出栈中所有运算符

后缀表达式求值：

使用操作数栈，遇到操作数压入，遇到运算符弹出两个操作数计算后压入结果。

递归与栈的关系：

每次函数调用时，系统会将返回地址、局部变量等压入调用栈。递归深度过大可能导致栈溢出。理解栈的工作原理有助于编写安全的递归代码。

10.11 队列的深度分析：循环队列的实现细节

循环队列使用固定大小数组实现，通过取模运算实现"环形"效果。

关键细节：

队满判断：(tail + 1) % size == head（牺牲一个位置区分队满和队空）
队空判断：head == tail
入队：data[tail] = x; tail = (tail + 1) % size
出队：x = data[head]; head = (head + 1) % size

为什么牺牲一个位置：

如果不牺牲，队满和队空的条件都是 head == tail，无法区分。另一种方案是增加一个计数器记录元素个数。

双端队列的实现：

双端队列（Deque）支持两端插入和删除。可以用双向链表或循环数组实现。在循环数组实现中，需要维护head和tail两个指针，每个指针都可以独立前进或后退。

10.12 链表的高级操作

链表的合并：

将两个有序链表合并为一个有序链表，时间O(n+m)。这是归并排序中合并步骤的链表版本。

链表的反转：

LIST-REVERSE(head)
    prev = NIL
    curr = head
    while curr ≠ NIL
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return prev

时间O(n)，空间O(1)。

检测链表环：

使用快慢指针（Floyd判圈算法）：

慢指针每次走一步，快指针每次走两步
如果有环，快慢指针必然相遇
相遇后，将一个指针移回头部，两个指针每次各走一步，再次相遇点就是环的入口

链表的排序：

归并排序是链表排序的最佳选择：

不需要随机访问
合并操作只需修改指针
时间O(n log n)，空间O(1)（自底向上实现）

10.13 树的深度分析

树的数学性质：

n个节点的树有n-1条边
树的任意两个节点之间有且仅有一条简单路径
树是无环连通图

二叉树的性质：

第i层最多有2^i个节点
深度为k的二叉树最多有2^(k+1)-1个节点
对于任何二叉树，叶子节点数 = 度为2的节点数 + 1

完全二叉树：

除最后一层外，每层都是满的，且最后一层节点靠左排列。完全二叉树可以用数组高效存储，这正是堆的基础。

满二叉树：

每个节点要么是叶子，要么有两个子节点。

10.14 数据结构在内存管理中的应用

空闲链表：

操作系统使用空闲链表管理可用内存块。每个空闲块包含大小信息和指向下一个空闲块的指针。分配时从链表中取出合适的块，释放时归还到链表中。

内存池：

预先分配一大块内存，使用链表管理空闲块。避免频繁的系统调用，提高分配效率。

垃圾回收：

Java等语言的垃圾回收器使用图遍历（标记-清除算法）：从根对象出发遍历对象图，标记所有可达对象，回收不可达对象的内存。

10.15 数据结构选择的决策框架

在实际工程中，选择数据结构需要综合考虑多个因素：

操作频率分析：

统计各种操作的调用频率，选择最频繁操作最高效的数据结构。例如，如果查找操作远多于插入，哈希表优于有序数组。

数据规模评估：

小数据量（<100）：简单数组或链表即可

中等数据量（100-100000）：哈希表、二叉搜索树

大数据量（>100000）：平衡树、B树、跳表

访问模式：

顺序访问为主：数组、链表

随机访问为主：数组、哈希表

范围查询为主：平衡树、B树

内存约束：

内存紧张：数组（紧凑存储）

内存充足：链表、树（指针开销可接受）

并发需求：

单线程：任何数据结构

多线程：选择线程安全的数据结构或使用锁

本章小结

本章详细介绍了基本数据结构。我们学习了：

栈：后进先出（LIFO），支持PUSH和POP操作，O(1)时间。栈在表达式求值、函数调用、括号匹配等场景中不可或缺。

队列：先进先出（FIFO），支持ENQUEUE和DEQUEUE操作，O(1)时间。循环队列是队列的经典数组实现，双端队列扩展了两端操作的能力。

链表：动态数据结构，支持高效插入/删除，但不支持随机访问。链表的高级操作包括合并、反转、环检测和排序。

有根树：层次数据结构，适合表示具有父子关系的数据。二叉树、左孩子-右兄弟表示法各有适用场景。

树的遍历：深度优先（前序、中序、后序）和广度优先（层序）。不同遍历方式适用于不同场景。

数据结构选择：根据操作需求、数据规模、访问模式和内存约束选择合适的数据结构。

基本数据结构是算法的基石。熟练掌握这些数据结构，理解它们的优缺点和适用场景，是学习更复杂数据结构和算法的前提，也是编写高质量软件的基础。

关键术语

术语	英文	含义
栈	Stack	后进先出的数据结构
队列	Queue	先进先出的数据结构
链表	Linked List	节点通过指针连接的数据结构
有根树	Rooted Tree	有根节点的树形数据结构
深度优先遍历	DFS	优先深入子树的遍历方式
广度优先遍历	BFS	按层遍历的方式
哨兵节点	Sentinel	简化边界条件的虚拟节点

思考题

使用两个栈实现一个队列，分析各操作的时间复杂度。

设计一个支持O(1)时间PUSH、POP和获取最小值的栈。

实现一个双链表，支持在O(1)时间内删除给定节点（假设节点指针已知）。

设计一个算法，判断一个二叉树是否为平衡二叉树（任意节点的左右子树高度差不超过1）。

第10章 基本数据结构

导读