数据结构：（四）空间的艺术——数组压缩与广义表
目录
一、 数组：从逻辑维度到物理地址
1. 行优先 (Row-major) 与 列优先 (Column-major)
二、 特殊矩阵的压缩存储
1. 对称矩阵 ()
2. 三角矩阵
三、 稀疏矩阵 (Sparse Matrix)：变废为宝
1. 三元组顺序表 (Triple Oracle)
2. 十字链表 (Cross List) —— 终极优化
四、 广义表 (Generalized Lists)：递归的线性表
1. 核心操作：GetHead 与 GetTail
五、 今日深度总结表
避坑指南：
一、 数组：从逻辑维度到物理地址
数组是随机存取结构。在内存中，多维数组必须映射为一维线性地址。
1. 行优先 (Row-major) 与 列优先 (Column-major)
行优先（C语言、严版教材默认）：先存第一行，再存第二行。
二维数组地址计算公式（以
的二维数组
为例，下标从 0 开始）：
详细注释：
代表跳过了前
行的所有元素，
代表在当前行偏移的位置，
是每个元素占用的字节数。
二、 特殊矩阵的压缩存储
对于有规律的矩阵，我们只存“有效”部分，其余部分通过数学公式计算得出。
1. 对称矩阵 (![]()
)
只需存储下三角（含对角线）的个元素。
映射公式：将二维下标
映射到一维数组
。
(当
时)
2. 三角矩阵
上（下）三角全是常数。同样只存有效的一半加一个位置存常数
。
三、 稀疏矩阵 (Sparse Matrix)：变废为宝
当矩阵中绝大多数元素为 0 时（非零元素占比通常 < 5%），直接存储会造成内存极大浪费。
1. 三元组顺序表 (Triple Oracle)
原理：每个非零元素存为一个三元组
(行下标, 列下标, 值)。缺点：失去了随机存取特性。
高频考点：快速转置算法。传统的行列互换后，为了保持三元组按行序排列，需要预先统计每列非零个数，计算出转置后每行应放的起始位置。
2. 十字链表 (Cross List) —— 终极优化
结构：每个非零元素是一个节点，包含五个域：
行、列、值、行指针(right)、列指针(down)。优势：在进行矩阵加法、乘法等动态运算时，十字链表无需像三元组那样频繁移动元素，效率极高。
四、 广义表 (Generalized Lists)：递归的线性表
广义表是线性表的推广，它的元素可以是原子（单个数据），也可以是子表。
1. 核心操作：GetHead 与 GetTail
这是考试中最容易丢分的地方：
GetHead(L)：取出的第一个元素。可以是原子，也可以是子表。
GetTail(L)：除去第一个元素外，剩下的元素组成的表。
⚠️ 必考例题：
——注意：尾部一定带括号，是一个表！
五、 今日深度总结表
| 存储对象 | 核心挑战 | 解决方案 | 适用场景 |
| 稠密矩阵 | 快速存取 | 顺序存储（行优先） | 基础科学计算 |
| 对称/对角矩阵 | 冗余数据多 | 下三角/对角压缩 | 物理模拟、结构分析 |
| 稀疏矩阵 | 0 元素极多 | 三元组、十字链表 | 社交网络邻接矩阵、推荐算法 |
| 广义表 | 结构不规则 | 链式存储（头尾链） | Lisp 语言、递归逻辑表示 |
避坑指南：
公式偏移：一定要看清题目下标是从 0 还是 1 开始。如果是从 1 开始，地址公式变为：
。
转置细节：三元组转置时，如果不使用“快速转置”，时间复杂度会升至 $O(n \times t)$（$t$ 为非零元素个数），这在考研大题中是扣分项。
广义表空表：
。空表也是表，不能写“无”。