1数据结构概述
计算机解决问题时，首先要把现实中的信息抽象为数据，并选择合适的方式组织这些数据。 数据结构就是研究数据之间的相互关系（逻辑结构）、数据在计算机中的存储方式（存储结构）以及在其上可执行的操作。
1.1 基本术语
- 数据（Data）：能输入计算机并被处理的符号的总称，如数、字符、图像、声音。
- 数据元素：数据的基本单位（如一条学生记录），一个元素可由若干数据项组成（学号、姓名——数据项是最小不可分割单位）。
- 数据对象：性质相同的数据元素的集合，如全部整数、全班学生记录。
1.2 逻辑结构
逻辑结构描述数据元素之间的逻辑关系，与存储无关，分为四类：
集合
元素同属一个集合，元素间除"同属"外无其他关系
线性结构
一对一：元素排成序列，有唯一前驱和后继
树形结构
一对多：层次关系，如家族谱、目录
图状结构
多对多：任意两元素都可能相关，如交通网
1.3 存储结构（物理结构）
- 顺序存储：元素存放在地址连续的存储单元里，借助相对位置表示逻辑关系（数组实现）。
- 链式存储：元素存放在任意地址，每个节点附带指针指向相关节点。
- 索引存储：在建数据的同时建立附加的索引表以加快查找。
- 散列存储（哈希）：根据元素关键字直接计算出存储地址。
逻辑结构是面向问题的抽象，存储结构是逻辑结构在计算机中的实现。同一种逻辑结构可以采用不同的存储结构（如线性表既可顺序存储也可链式存储）。
2线性表
2.1 顺序表（顺序存储）
用一组地址连续的存储单元依次存放线性表元素，高级语言中借助数组实现。
下标: [0] [1] [2] [3] [4]
数据: 12 25 38 47 60 ← 逻辑相邻，物理也相邻- 优点：可随机存取（按下标直接定位，O(1)）；存储密度高，无需额外指针。
- 缺点：插入和删除需移动大量元素（平均移动一半，O(n)）；需要连续空间，扩容不便、可能浪费。
2.2 链表（链式存储）
节点由数据域 + 指针域构成，节点在内存中可以不连续。
头指针 head
↓
[12|●]→[25|●]→[38|●]→[47|∧] （∧ 表示空指针 NULL）
数据 指针- 单链表：每个节点只有一个指向后继的指针。
- 双链表：节点同时有指向前驱和后继的两个指针，可双向遍历。
- 循环链表：尾节点指向头节点，形成环，从任意节点都可遍历全表。
- 优点：插入删除只需修改指针、不需移动元素（O(1)，若已定位）；按需动态分配空间。
- 缺点：只能顺序存取，找第 i 个元素要从头遍历（O(n)）；指针占用额外空间。
2.3 顺序表与链表对比
| 对比项 | 顺序表（数组） | 链表 |
|---|---|---|
| 存储空间 | 连续，需预分配 | 不连续，动态申请 |
| 按位置访问 | 随机存取 O(1) | 顺序存取 O(n) |
| 插入/删除 | 平均移动 n/2 个元素 O(n) | 改指针即可 O(1)（不计查找） |
| 额外开销 | 无 | 每个节点有指针开销 |
| 适用场景 | 查找多、增删少、长度稳定 | 增删频繁、长度变化大 |
3栈
push → ┌────┐
│ 30 │ ← top（栈顶，最后入栈，最先出栈）
├────┤
│ 20 │
├────┤
│ 10 │ ← bottom（栈底）
└────┘
pop 顺序：30 → 20 → 103.1 栈的实现
可用顺序栈（数组+栈顶指针）或链栈实现。入栈栈顶指针上移，出栈下移；要防止上溢（栈满还压入）和下溢（栈空还弹出）。
3.2 栈的典型应用
- 函数调用与返回：系统用"函数调用栈"保存返回地址、参数和局部变量；递归本质上就是借助栈实现的。
- 括号匹配检查：左括号入栈，遇右括号弹出匹配；栈最终为空且不发生失配则表达式合法。
- 表达式求值：中缀转后缀（逆波兰式），再借助栈计算；运算符有优先级。
- 撤销操作（Undo）、浏览器后退、深度优先搜索（DFS）等。
入栈序列为 1,2,3 时，合法出栈序列不只有 3,2,1：例如 1 入 1 出、2 入 2 出、3 入 3 出 可得到 1,2,3——这类"出栈序列合法性"判断题的关键是：任意元素出栈时，栈中比它先入栈的元素必须按逆序出现。
4队列
出队 ← [ 10 ][ 20 ][ 30 ] ← 入队
↑front ↑rear4.1 循环队列
用数组实现队列时，队头删除会造成前面空间闲置（"假溢出"）。解决办法是把数组想象成首尾相接的环，
队头、队尾指针用取模运算循环移动，称为循环队列。通常牺牲一个单元来区分队空与队满：
队空：front == rear；队满：(rear+1) % n == front。
4.2 队列的应用与变种
- 操作系统中的任务排队：打印队列、进程就绪队列、消息缓冲。
- 广度优先搜索（BFS）：按层次遍历图或树。
- 双端队列 Deque：两端都可进出；优先队列：按优先级高低出队（通常用堆实现）。
- 实际系统中的消息队列（Kafka 等）、秒杀请求削峰也是队列思想的延伸。
栈与队列的记忆：栈像弹夹/水桶（后进先出 LIFO），队列像排队/管道（先进先出 FIFO），二者都是"操作受限的线性表"。
5串、数组与广义表
5.1 串（字符串）
串是由零个或多个字符组成的有限序列，如 "hello"。串中字符个数为串的长度，长度为 0 的串称空串。
常见操作有求长度、连接、比较、求子串、插入删除，其中最重要的是模式匹配：在主串中查找子串（模式串）出现的位置。
朴素匹配法最坏 O(nm)，KMP 算法利用已匹配信息使时间复杂度降为 O(n+m)。
5.2 数组
数组是类型相同、下标有序的一组元素的集合。一维数组可视为顺序表；二维数组在内存中按行优先（C、Java）或列优先（Fortran）次序展开为一维序列存放。
二维数组 A[2][3] 按行优先存放：
A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2]5.3 特殊矩阵的压缩存储
- 对称矩阵：a[i][j] = a[j][i]，只存下三角（含对角线）。
- 三角矩阵：上（下）三角元素相同，只存一半再加一个常数单元。
- 稀疏矩阵：绝大多数元素为零，只记录非零元的"行、列、值"三元组。
5.4 广义表
广义表是线性表的推广，其元素既可以是单个数据（原子），也可以又是一个广义表（子表），如 L = (a, (b, c), d)，
可表示层次嵌套数据，广泛用于人工智能的符号表达式和函数式语言。
6树与二叉树
6.1 树的基本概念
树是 n（n≥0）个节点的有限集合，有且仅有一个根节点，其余节点分成若干互不相交的子树，每个子树本身又是一棵树。 它适合表达具有层次关系的数据（组织架构、文件目录、菜单）。
- 度：节点拥有的子树数；树的度是各节点度的最大值。
- 层次/深度：根为第 1 层，逐层加一；树的最大层数即树的深度。
- 叶子是度为 0 的节点；父节点、子节点、兄弟节点、森林（若干棵互不相交的树）。
6.2 二叉树
重要性质：
- 第 i 层最多有
2^(i-1)个节点；深度为 k 的二叉树最多有2^k - 1个节点。 - 对任何二叉树，若叶子数为 n₀、度为 2 的节点数为 n₂，则
n₀ = n₂ + 1。
两种特殊形态：满二叉树每层节点数都达到最大（无空缺）；完全二叉树除最后一层外全满，最后一层节点从左到右连续排列——它可用数组高效存储。 一般二叉树常用链式存储（节点含 left、right 两个指针）。
6.3 二叉树的遍历
遍历指按某种次序访问每个节点且仅访问一次。根据根的访问时机分为（以左→右为序）：
| 遍历方式 | 访问顺序 | 用途 |
|---|---|---|
| 前序遍历（先根） | 根 → 左 → 右 | 复制树、显示目录结构、前缀表达式 |
| 中序遍历（中根） | 左 → 根 → 右 | 二叉排序树中得到有序序列、中缀表达式 |
| 后序遍历（后根） | 左 → 右 → 根 | 释放/计算目录大小、后缀表达式 |
| 层序遍历 | 自上而下、自左向右逐层访问 | 借助队列实现 |
6.4 哈夫曼树（最优二叉树）
路径长度是路径上的分支数。给定 n 个带权叶子构造一棵二叉树，使带权路径长度之和 WPL 最小的树称哈夫曼树。 构造方法：每次取权值最小的两棵树合并、新树根权值为两者之和，重复直到只剩一棵树。 其应用哈夫曼编码是一种不定长前缀编码：出现频率高的字符用短编码，广泛用于数据压缩（如 ZIP、JPEG）。
7图
图是比树更复杂的多对多非线性结构。现实中的交通线路、社交关系、课程先修关系、网络拓扑都可以用图建模。
7.1 图的定义与术语
图 G 由顶点集 V 和边集 E 组成，记 G=(V, E)。
- 有向图 / 无向图：边有方向（弧：尾→头）或无方向。
- 度、入度、出度：无向图中与顶点相连的边数为度；有向图分入度（以它为终点）和出度。
- 权与网：边上标注距离、费用等数值（权），带权图也称网。
- 路径与连通：两顶点间的顶点序列；无向图任意两顶点都有路径则为连通图。
7.2 图的存储
邻接矩阵
用二维数组 A[i][j] 表示顶点 i 到 j 是否有边（带权则存权值，无边存 ∞）。判断两顶点是否相邻极快 O(1)，但稀疏图浪费空间，适合稠密图。
邻接表
为每个顶点建立一个链表，链接它的所有邻接点。节省空间、便于遍历邻接点，适合稀疏图，是实际中最常用的存储方式。
7.3 图的遍历
- 深度优先搜索 DFS：从某顶点出发，沿一条路走到尽头再回溯，借助栈/递归实现——"不撞南墙不回头"。
- 广度优先搜索 BFS：先访问起点，再依次访问其所有邻接点，层层外扩，借助队列实现——"水波式扩散"，可求无权图最短路径。
7.4 经典图算法
| 问题 | 算法 | 思想 |
|---|---|---|
| 最小生成树 | Prim、Kruskal | 以最小总权值选出连通所有顶点的 n-1 条边（架光缆、修路） |
| 单源最短路径 | Dijkstra（迪杰斯特拉） | 贪心逐步确定起点到各顶点的最短距离（导航） |
| 各点对最短路径 | Floyd | 动态规划思想，用中间点松弛 |
| 工程活动排序 | 拓扑排序、关键路径 | 对有向无环图排序，判断课程/工序先后与工期 |
8查找
查找（检索）：在数据集合中寻找关键字等于给定值的元素。衡量查找效率的主要指标是平均查找长度 ASL（查找成功时平均比较次数）。
8.1 线性表查找
- 顺序查找：从头到尾逐个比较。对数据无任何要求，简单但慢，平均 ASL ≈ (n+1)/2，O(n)。
- 二分查找（折半查找）：要求数据已排序且顺序存储。每次与中间元素比较，排除一半：
mid = (low+high)/2。 效率 O(log₂n)，如在 100 万个有序数中找一个数最多约 20 次比较。 - 分块查找（索引顺序查找）：把表分块，块间有序、块内可无序，先查索引块再块内顺序找，是二者的折中。
8.2 树表查找
二叉排序树（二叉搜索树 BST）：左子树值 < 根 < 右子树值。中序遍历得到升序序列，查找类似二分，平均 O(log n)； 若插入顺序不当退化成链表则降为 O(n)，为此有平衡二叉树（AVL）、红黑树通过旋转保持平衡（数据库索引、map 底层常用）。
8.3 哈希查找（散列）
思想：不经过比较，由关键字通过哈希函数 H(key) 直接计算存储地址，理想情况下查找 O(1)。如除留余数法 H(key) = key % p。
不同关键字可能算出同一地址，即冲突（碰撞），解决方法：
- 开放定址法：冲突后按线性探测、二次探测等寻找下一个空位。
- 链地址法：同一地址的所有同义词存入一个链表。
- 再哈希法、建立公共溢出区等。装填因子（已存元素/表长）越大冲突越多，需适时扩容。
9排序
排序：把一组无序记录按关键字递增（或递减）排列起来，是最基础、使用最频繁的算法。 若多个记录关键字相等，排序后相对次序保持不变，则称算法稳定。
9.1 三大简单排序
- 冒泡排序：相邻元素两两比较，逆序则交换，每轮把当前最大者"冒泡"到末尾。稳定，O(n²)。
- 简单选择排序：每轮在未排序部分选出最小元素放到已排序序列末尾。比较次数与初始顺序无关，O(n²)，不稳定。
- 直接插入排序：把每个元素插入前面已排好序的序列中的正确位置（类似整理扑克牌）。稳定，O(n²)，对基本有序的数据很快。
9.2 三种高效排序
- 快速排序：选一个基准，把比它小的放左边、大的放右边，再对两边递归。平均 O(n log n)，实践中最快的内排序之一，不稳定。
- 归并排序：把序列不断对半拆成单元素（自然有序），再两两合并成有序序列。稳定、O(n log n)，但需 O(n) 额外空间，适合外部排序。
- 堆排序：利用完全二叉树性质的"堆"反复取堆顶极值。O(n log n)、原地、不稳定。
9.3 排序算法对比
| 算法 | 平均时间 | 最坏时间 | 额外空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
数据量小用简单排序；量大追求速度用快排；要求稳定用归并；语言标准库常采用混合排序（如内省排序 Timsort）。
本章小结：数据结构 = 逻辑结构（集合、线性、树、图）+ 存储结构（顺序、链式、索引、散列）+ 运算。 线性结构中：顺序表随机存取快、链表增删灵活、栈 LIFO 管"回溯"、队列 FIFO 管"排队"；树和图表达层次与网络关系；查找从顺序、二分、BST 到哈希逐级提速；排序分 O(n²) 简单算法与 O(n log n) 高效算法。下一章学习如何在计算机中持久化管理大规模数据——数据库技术。