第9章数组与广义表

课程目录第9章数组与广义表

第9章数组与广义表：存储结构与压缩技巧

数组和广义表，这两个概念看起来简单，但实际用起来门道不少。我在做嵌入式系统开发时，就曾因为数组存储顺序搞反，导致整个图像数据错位——那画面，简直像毕加索的画。今天咱们就把这块彻底理清楚。

9.1 数组的存储结构

数组在内存里怎么放？说白了就两种方式：行优先和列优先。你想想看，二维数组在物理上是一维的，总得有个规则把逻辑位置映射到物理地址。

9.1.1 行优先存储

C语言用的就是行优先。什么意思？就是先存完第一行所有元素，再存第二行。比如一个3×4的数组：

int arr[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

内存中的顺序是：1,2,3,4,5,6,7,8,9,10,11,12。

地址计算公式：

Loc(a[i][j]) = Loc(a[0][0]) + (i * n + j) * sizeof(element)

其中n是列数。这个公式我建议你背下来，面试经常考。

9.1.2 列优先存储

Fortran和MATLAB用的是列优先。先存第一列，再存第二列。同样的数组，列优先顺序是：1,5,9,2,6,10,3,7,11,4,8,12。

地址公式：

Loc(a[i][j]) = Loc(a[0][0]) + (j * m + i) * sizeof(element)

m是行数。

⚠ 我曾经踩过的坑： 在C语言里用指针遍历二维数组时，如果按列优先方式访问，缓存命中率会极低。因为CPU缓存一次加载一整行，你跳着访问列，性能直接掉一个数量级。

9.2 特殊矩阵的压缩存储

实际项目中，很多矩阵是特殊的。比如对称矩阵、三角矩阵、稀疏矩阵。如果按普通二维数组存，浪费空间不说，还慢。我做过一个有限元分析的项目，矩阵规模10万×10万，不压缩根本存不下。

9.2.1 对称矩阵

对称矩阵满足a[i][j] = a[j][i]。我们只需要存一半，比如下三角部分（包括对角线）。

压缩为一维数组后，下标映射公式：

k = i*(i+1)/2 + j   (i ≥ j)

举个例子，3×3对称矩阵：

原始矩阵：
1 2 3
2 4 5
3 5 6

压缩后一维数组：[1, 2, 4, 3, 5, 6]
对应位置：k0, k1, k2, k3, k4, k5

    核心要点： 压缩存储节省了近一半空间，但访问时需要做一次条件判断——如果i<j，就交换i和j。

9.2.2 三角矩阵

上三角矩阵：对角线以下全为0。下三角矩阵：对角线以上全为0。存储方式类似对称矩阵，但只存非零部分。

下三角矩阵（含对角线）的压缩公式：

k = i*(i+1)/2 + j   (i ≥ j)

上三角矩阵的压缩公式：

k = i*(2n - i - 1)/2 + j   (i ≤ j)

嗯，这里要注意：上三角的公式稍微复杂点，我建议你手推一遍，理解比死记硬背重要。

9.2.3 稀疏矩阵

稀疏矩阵的非零元素很少，比如5%以下。这时候用三元组存储最合适。

三元组结构：

typedef struct {
    int row;      // 行号
    int col;      // 列号
    int value;    // 非零元素值
} Triple;

typedef struct {
    Triple data[MAXSIZE];  // 三元组表
    int rows;              // 总行数
    int cols;              // 总列数
    int nums;              // 非零元素个数
} SparseMatrix;

举个例子：

原始稀疏矩阵：
0 0 3 0
0 5 0 0
0 0 0 7

三元组表示：
(0,2,3)
(1,1,5)
(2,3,7)

💡 个人经验： 稀疏矩阵的转置操作，用三元组做时要注意按列排序。我一般用快速排序，时间复杂度O(nlogn)，比暴力O(n²)快得多。

9.3 广义表

广义表是线性表的推广。普通线性表的元素都是原子，广义表的元素可以是子表。说白了，就是可以嵌套。

9.3.1 广义表的定义

广义表记作：LS = (a1, a2, ..., an)

其中ai可以是原子，也可以是子表。比如：

A = ()           // 空表
B = (a, b)       // 只有原子
C = (a, (b, c))  // 包含子表
D = (A, B, C)    // 嵌套广义表

9.3.2 广义表的存储结构

我习惯用链式存储。每个节点要么是原子节点，要么是子表节点。

typedef enum { ATOM, LIST } NodeType;

typedef struct GLNode {
    NodeType tag;      // 标志域：ATOM或LIST
    union {
        char atom;     // 原子值
        struct {
            struct GLNode *hp;  // 表头指针
            struct GLNode *tp;  // 表尾指针
        } ptr;
    } data;
} GLNode;

这种结构叫头尾链表存储法。每个子表节点有两个指针：hp指向表头，tp指向表尾。

9.3.3 广义表的基本操作

常用的操作有：

取表头：GetHead(L) —— 返回第一个元素
取表尾：GetTail(L) —— 返回除第一个元素外的子表
求深度：递归计算嵌套层数
求长度：最外层元素个数

举个例子：

L = (a, (b, c, d), e)
GetHead(L) = a
GetTail(L) = ((b, c, d), e)
深度 = 2
长度 = 3

    注意： GetTail返回的永远是一个子表，即使只有一个元素。比如L=(a)，GetTail(L)=()，空表。

9.4 知识体系总览

下面这张图把本章的核心知识点串起来了：

9.5 实战建议

学完这些理论，我建议你动手做几件事：

手写一个稀疏矩阵乘法 —— 用三元组实现，别用二维数组。做完你就知道压缩存储的威力了。
实现广义表的深度递归计算 —— 递归是广义表操作的核心，写一遍能加深理解。
对比行优先和列优先的缓存性能 —— 写个测试程序，用大数组跑一下，看看时间差多少。

💡 我的习惯： 遇到矩阵问题，先问自己三个问题：矩阵规模多大？非零元素比例多少？访问模式是行遍历还是列遍历？答案决定了选哪种存储方案。

数组和广义表这块，说白了就是「怎么把数据放好、找得快」。理解了存储的本质，后面学树、图这些复杂结构就轻松多了。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录