第七章：数组与广义表——从连续内存到递归结构

数组这东西，大家从学C语言第一天就接触了。但说实话，很多人用了好几年，对数组的理解还停留在「连续内存的一块区域」这个层面。我个人习惯把数组看作一种随机存取的线性结构——你给我下标，我直接算出地址，时间复杂度O(1)。

广义表就更有意思了。它允许元素本身又是一个表，这就打破了线性结构的限制。我在做编译器的符号表管理时，就遇到过需要嵌套结构的情况，当时用广义表来处理，比用树结构要灵活得多。

好，我们一步步来看。

7.1 数组的定义与存储

数组的定义其实很简单：一组类型相同、物理连续的元素集合。但要注意，C语言里的数组名本质上是一个常量指针，指向首元素地址。

多维数组的存储，有两种方式：

  • 行优先（Row-major）：C语言采用这种方式。先存完第一行所有列，再存第二行。
  • 列优先（Column-major）：Fortran语言采用。先存完第一列所有行，再存第二列。

举个例子，一个二维数组 int a[3][4]，在内存中的布局是这样的：

地址:  [0][0] [0][1] [0][2] [0][3] [1][0] [1][1] [1][2] [1][3] [2][0] ...
偏移:   0      1      2      3      4      5      6      7      8

计算某个元素 a[i][j] 的地址公式：

地址 = 基地址 + (i * 列数 + j) * sizeof(元素类型)

嗯，这个公式我建议你背下来。面试经常考，而且实际做底层驱动时也经常用到。

小技巧： 如果你在嵌入式系统里操作寄存器映射，经常需要把结构体指针强制转换成数组来访问。这时候搞清楚内存布局就特别重要。我曾经因为搞混了行优先和列优先，导致一个图像处理算法输出全是雪花屏……排查了整整两天。

7.2 特殊矩阵的压缩存储

什么叫特殊矩阵？说白了就是那些有很多重复元素或者零元素的矩阵。如果我们还按普通二维数组存，太浪费空间了。所以我们要做压缩存储。

7.2.1 对称矩阵

对称矩阵满足 a[i][j] = a[j][i]。我们只需要存上三角或下三角部分，包括对角线。

以下三角为例，存储到一维数组 sa[] 中：

// 下三角矩阵，按行存储
// 元素 a[i][j] (i >= j) 在 sa 中的下标为：
// k = i*(i+1)/2 + j

// 示例：4x4 对称矩阵
// 原始矩阵：
// 1  2  3  4
// 2  5  6  7
// 3  6  8  9
// 4  7  9  10

// 压缩后 sa[] = {1, 2, 5, 3, 6, 8, 4, 7, 9, 10}
// 共 10 个元素，节省了 6 个

7.2.2 三角矩阵

上三角矩阵：下三角部分（不含对角线）全为常数c。下三角矩阵则相反。

存储时，除了存三角部分的元素，还要多一个位置存那个常数c。

7.2.3 对角矩阵

只有主对角线及其附近几条对角线有非零元素。比如三对角矩阵：

// 三对角矩阵，只有三条对角线有值
// 存储方式：按行存储对角线元素
// 或者用带状存储：sa[i][j-i+1]
注意： 压缩存储虽然省空间，但访问元素时需要做下标转换。这个转换公式如果写错了，程序不会报错，但数据全乱套。我曾经在写稀疏矩阵乘法时，因为下标映射公式少加了一个偏移量，结果算出来的结果完全不对，调试了三个小时才发现。

7.3 稀疏矩阵

稀疏矩阵的定义：非零元素个数远小于总元素个数，且分布没有规律。比如一个1000x1000的矩阵，只有100个非零元素，那就是稀疏矩阵。

稀疏矩阵的存储，核心思想是：只存非零元素的位置和值。

7.3.1 三元组表示法

每个非零元素用一个三元组表示：(行号, 列号, 值)。

// 三元组结构定义
typedef struct {
    int row;    // 行号
    int col;    // 列号
    int value;  // 非零元素值
} Triple;

// 稀疏矩阵结构
typedef struct {
    Triple data[MAXSIZE];  // 三元组表
    int rows;              // 总行数
    int cols;              // 总列数
    int num;               // 非零元素个数
} SparseMatrix;

7.3.2 十字链表法

三元组适合静态矩阵。如果矩阵需要频繁插入、删除非零元素，三元组的效率就很低了。这时候用十字链表更合适。

十字链表的结构：每个非零元素是一个节点，它同时属于一行链表和一列链表。

// 十字链表节点
typedef struct OLNode {
    int row, col;           // 行列号
    int value;              // 值
    struct OLNode *right;   // 指向同一行的下一个非零元素
    struct OLNode *down;    // 指向同一列的下一个非零元素
} OLNode;

typedef struct {
    OLNode *row_head[MAXSIZE];  // 行链表头指针数组
    OLNode *col_head[MAXSIZE];  // 列链表头指针数组
    int rows, cols;             // 矩阵维度
    int num;                    // 非零元素个数
} CrossList;
我的经验： 在实际项目中，如果稀疏矩阵的规模在1000x1000以内，非零元素占比小于5%，用三元组就够了。但如果矩阵需要动态变化，比如在有限元分析中，网格会不断细化，这时候十字链表才是正确的选择。我做过一个电磁场仿真项目，一开始用三元组，结果每次插入新节点都要移动大量数据，改成十字链表后性能提升了近10倍。

7.4 广义表的定义与操作

广义表，也叫列表（List），是线性表的推广。线性表的元素必须是原子（不可分割的数据），而广义表的元素可以是原子，也可以是另一个广义表。

定义形式：GL = (a1, a2, ..., an)，其中 ai 可以是原子，也可以是子表。

举个例子：

  • A = () —— 空表
  • B = (a, b) —— 两个原子
  • C = (a, (b, c), d) —— 第二个元素是子表
  • D = (A, B, C) —— 三个子表

7.4.1 广义表的存储结构

广义表不能用顺序存储，因为元素大小不固定。通常用链式存储：

// 广义表节点类型
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;

这种结构很有意思。每个节点要么存一个原子，要么存一对指针（表头、表尾）。这种设计让广义表的操作变得非常统一。

7.4.2 广义表的基本操作

两个核心操作：

  • 取表头（Head）：第一个元素
  • 取表尾（Tail）：除第一个元素外的剩余部分（一定是一个子表）

举个例子，对于 L = (a, (b, c), d)：

  • Head(L) = a
  • Tail(L) = ((b, c), d)
  • Head(Tail(L)) = (b, c)
  • Head(Head(Tail(L))) = b

你看，通过反复取表头和表尾，我们可以访问到任意深度的元素。

7.4.3 广义表的递归算法

广义表的很多操作天然适合递归。比如求深度：

int Depth(GLNode *L) {
    if (L == NULL) return 1;  // 空表深度为1
    if (L->tag == ATOM) return 0;  // 原子深度为0
    
    int max_depth = 0;
    GLNode *p = L;
    while (p != NULL) {
        int d = Depth(p->data.ptr.hp);  // 递归求子表深度
        if (d > max_depth) max_depth = d;
        p = p->data.ptr.tp;  // 遍历下一个元素
    }
    return max_depth + 1;
}
避坑指南： 写广义表的递归算法时，一定要注意终止条件。我曾经写过一个复制广义表的函数，忘记处理空表的情况，结果递归无法终止，栈溢出了。嗯，从那以后我写递归函数第一件事就是先写终止条件。

知识体系总览

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

数组与广义表知识体系 数组 定义与存储 特殊矩阵压缩 行优先/列优先 对称/三角/对角 稀疏矩阵 三元组表示 十字链表 广义表 定义与存储 基本操作 递归算法 链式存储 Head/Tail 求深度/复制 核心：空间换时间 压缩存储节省空间 随机存取提高效率

数组和广义表，一个强调连续存储和随机访问，一个强调递归结构和灵活嵌套。两者看似不同，但都是构建复杂数据结构的基石。你在实际项目中，根据数据的特点选择合适的结构，往往能事半功倍。

好，这一章就到这里。记住：数组是基础，广义表是进阶。把这两个吃透了，后面学树和图会轻松很多。

← 上一章 📖 返回目录 下一章 →