第八章 数组与广义表：存储结构与压缩技巧
数组和广义表，听起来像是两个独立的概念，但在实际工程中，它们经常被放在一起讨论。为什么？因为广义表本质上就是数组的一种推广——数组要求每个元素类型相同，而广义表允许元素类型不同，甚至允许嵌套。
我个人习惯把这一章的内容分成三块来理解：数组的存储布局、特殊矩阵的压缩、广义表的链表实现。这三块知识，说白了就是解决同一个问题：如何用最小的内存代价，高效地访问数据。
核心思想： 数据在内存中是一维的，但我们的逻辑结构可能是二维甚至多维的。存储结构就是在这两者之间搭桥。
8.1 数组的存储结构：行优先与列优先
数组在内存中怎么放？这个问题看似简单，但坑不少。我记得刚入行时，在一个图像处理项目里，因为搞错了行优先和列优先，导致整张图片显示成了条纹状。排查了一下午才发现是存储顺序的问题。
行优先存储，就是先存第一行的所有元素，再存第二行，以此类推。C语言默认就是行优先。比如一个 int a[3][4]，在内存中的排列是：
a[0][0], a[0][1], a[0][2], a[0][3],
a[1][0], a[1][1], a[1][2], a[1][3],
a[2][0], a[2][1], a[2][2], a[2][3]列优先存储则相反，先存第一列，再存第二列。Fortran语言就是列优先。你想想看，如果两种语言混编，数据传递时不做转换，结果会怎样？
我的经验： 在嵌入式系统中，如果频繁按行访问数据，就用行优先；如果按列访问多，就考虑列优先。这样可以充分利用CPU的缓存预取机制，性能差距可能达到数倍。
计算地址的公式也很简单。对于行优先的二维数组 A[m][n]，元素 A[i][j] 的地址为：
Loc(A[i][j]) = Base + (i * n + j) * sizeof(element)列优先则是：
Loc(A[i][j]) = Base + (j * m + i) * sizeof(element)嗯，这里要注意：公式中的 m 和 n 不要搞反。我曾经在代码里把行数和列数写反了，结果数组越界访问，程序跑飞了。这种bug很难查，因为逻辑上看起来完全正确。
8.2 特殊矩阵的压缩存储
实际工程中，很多矩阵是特殊的——比如对称矩阵、三角矩阵、稀疏矩阵。如果按普通二维数组存储，浪费大量空间。压缩存储的核心思想就是：只存有用的数据。
8.2.1 对称矩阵
对称矩阵满足 A[i][j] = A[j][i]。说白了，只需要存上三角或下三角的一半数据就够了。我一般习惯存下三角（包括对角线），因为这样索引计算更直观。
对于一个 n×n 的对称矩阵，压缩到一维数组 B[k] 中，下三角元素 A[i][j]（i ≥ j）的映射关系是：
k = i * (i + 1) / 2 + j如果 i < j，就交换 i 和 j 再计算。这个公式怎么来的？其实就是等差数列求和：前 i 行共有 i * (i + 1) / 2 个元素，再加上第 i 行的第 j 列偏移。
避坑指南： 我曾经在实现对称矩阵压缩时，忘记处理 i < j 的情况，直接用了上面的公式。结果访问上三角元素时，索引变成了负数。调试了半天才发现——对称矩阵的压缩，一定要保证 i ≥ j 再计算。
8.2.2 三角矩阵
三角矩阵分上三角和下三角。下三角矩阵只有对角线及以下有数据，以上全是常数（通常是0）。压缩方法和对称矩阵类似，但多了一个常数存储。
对于下三角矩阵，压缩到一维数组 B[k]：
k = i * (i + 1) / 2 + j (i ≥ j)
k = n * (n + 1) / 2 (i < j，存储常数)上三角矩阵同理，只是公式略有变化：
k = j * (j + 1) / 2 + i (i ≤ j)
k = n * (n + 1) / 2 (i > j，存储常数)你可能会问：为什么上三角的公式是 j * (j + 1) / 2 + i？因为上三角中，第 j 列有 j+1 个元素（从第0行到第j行），前 j 列共有 j * (j + 1) / 2 个元素，再加上行偏移 i。
8.2.3 稀疏矩阵
稀疏矩阵是指非零元素很少的矩阵。比如一个 1000×1000 的矩阵，只有几百个非零元素。如果按普通方式存储，4MB 内存就浪费了。
常用的压缩方式有三种：
- 三元组表示法：用 (row, col, value) 三个字段存储每个非零元素。简单直观，但访问时可能需要遍历。
- 行逻辑链接的顺序表：在三元组基础上，增加每行第一个非零元素的位置索引。查找效率更高。
- 十字链表：用链表结构存储，每个节点有行、列、值，以及指向下一行和下一列的指针。适合矩阵运算中频繁插入删除的场景。
三元组的结构体定义如下：
typedef struct {
int row; // 行号
int col; // 列号
int value; // 非零元素值
} Triple;
typedef struct {
Triple data[MAXSIZE]; // 三元组表
int rows; // 总行数
int cols; // 总列数
int num; // 非零元素个数
} SparseMatrix;我的建议： 在嵌入式系统中，如果稀疏矩阵的规模不大（比如几十行），三元组就够用了。如果矩阵规模大且需要频繁查找，用行逻辑链接。十字链表虽然灵活，但实现复杂，内存开销也大——除非你要做矩阵乘法或转置，否则慎用。
8.3 广义表的头尾链表存储
广义表是数组的推广。数组要求所有元素类型相同，但广义表允许元素是原子（单个数据）或子表。比如 A = (a, (b, c), d)，其中 (b, c) 就是一个子表。
广义表的存储，我推荐用头尾链表。每个节点有两个指针：表头指针和表尾指针。表头指向第一个元素，表尾指向剩余部分。
节点类型定义：
typedef enum { ATOM, LIST } NodeType;
typedef struct GLNode {
NodeType tag; // 标志域：ATOM 或 LIST
union {
char atom; // 原子值（当 tag == ATOM 时）
struct {
struct GLNode *head; // 表头指针
struct GLNode *tail; // 表尾指针
} ptr; // 表结构（当 tag == LIST 时）
} data;
} GLNode;举个例子，广义表 A = (a, (b, c), d) 的存储结构如下：
- 第一个节点：tag=LIST，head 指向原子 a，tail 指向剩余部分
- 剩余部分：tag=LIST，head 指向子表 (b, c)，tail 指向原子 d
- 子表 (b, c)：tag=LIST，head 指向原子 b，tail 指向原子 c
这种结构的好处是：递归定义，递归操作。求深度、复制、遍历都可以用递归实现，代码非常简洁。
避坑指南： 我曾经在实现广义表复制时，忘记处理递归终止条件——当表尾为 NULL 时，应该直接返回 NULL。结果递归无限循环，栈溢出了。记住：广义表的递归操作，一定要有明确的终止条件。
广义表的深度计算，递归思路很简单：
int Depth(GLNode *L) {
if (L == NULL) return 0; // 空表深度为0
if (L->tag == ATOM) return 0; // 原子深度为0
int maxDepth = 0;
GLNode *p = L;
while (p != NULL) {
int d = Depth(p->data.ptr.head); // 递归求子表深度
if (d > maxDepth) maxDepth = d;
p = p->data.ptr.tail; // 继续处理剩余部分
}
return maxDepth + 1;
}嗯，这里要注意：广义表的深度是子表嵌套的最大层数，不是元素个数。比如 (a, (b, (c))) 的深度是3，因为 c 嵌套了三层。
总结一下： 数组和广义表的存储，本质上都是在「逻辑结构」和「物理结构」之间做映射。数组的映射是线性的，广义表的映射是递归的。理解了这个本质，你就能灵活应对各种存储需求。
在实际项目中，我见过很多开发者一上来就用二维数组存矩阵，结果内存不够用。其实只要稍微思考一下数据的特性——是不是对称的？是不是稀疏的？——就能找到更优的存储方案。这就是我们学这一章的意义所在。
公众号:蓝海资料掘金营，微信deep3321