数组和特殊矩阵

真题练习：可在站内题库按“特殊矩阵”知识点筛选。

复习时需要掌握多维数组的存储方式和矩阵的几种压缩存储方式。

多维数组的存储

在计算机内存中，数组元素是 连续存放 的。对于一个二维数组来说，它实际上只是对一维数组的一种逻辑抽象。理解其存储方式的关键在于：如何将二维坐标 $(i, j)$ 映射到一维的线性内存地址。

假设：

数组的第一个元素起始地址为 $A$ ；
每个元素占用 $B$ 个字节；
数组一共有 $R$ 行、 $C$ 列；

若下标从 0 开始，那么数组中元素 $a[i][j]$ 的存储地址为：

\operatorname{Addr}(a[i][j])=A+(iC+j)B

其中：

$i \times C$ 表示从第 0 行到第 $i-1$ 行总共有多少个元素；
再加上 $j$ ，就得到了在一维展开后对应的下标；
乘以 $B$ 后，加上基址 $A$ ，就得到了该元素在内存中的实际地址。

举个 C 语言的示例进行说明，如果我们定义一个二维数组：

int a[2][3] = {{1, 2, 3}, {4, 5, 6}};

这个数组的内存布局可以视为一个一维数组，如下所示：

  +---------+---------+---------+---------+---------+---------+
  | a[0][0] | a[0][1] | a[0][2] | a[1][0] | a[1][1] | a[1][2] |
  +---------+---------+---------+---------+---------+---------+
0x100      0x104    0x108     0x10C     0x110     0x114

行主序和列主序

需要注意的是，不同语言对多维数组的存储顺序可能不同：

C / C++ 等主流编程语言：采用 行主序（Row-major order），即先存满一行，再存下一行。
Fortran / MATLAB：采用 列主序（Column-major order），即先存满一列，再存下一列。

如果按列主序存储，上面例子 a[2][3] 的内存布局会变为：

  +---------+---------+---------+---------+---------+---------+
  | a[0][0] | a[1][0] | a[0][1] | a[1][1] | a[0][2] | a[1][2] |
  +---------+---------+---------+---------+---------+---------+

特殊矩阵的压缩存储

对称矩阵

对称矩阵是指：对于矩阵 $A$ 中任意元素 $a_{i,j}$ ，都有

a_{i,j}=a_{j,i}.

所以为了 节省存储空间，可以只保存上三角或下三角元素，并使用一维数组 $B$ 进行存储。

概念对照

对称矩阵的两种压缩方向

点击比较维度，核对保留下三角或上三角时的存储区域、镜像规则和一维下标公式。

比较维度保存下三角保存上三角

当前比较：直接保存的元素。

下标公式的两个核心分支分别包含 $\frac{i(i-1)}{2}+j-1$ 与 $\frac{j(j-1)}{2}+i-1$ 。

对称矩阵的压缩下标

设矩阵下标 $i,j$ 从 1 开始，而一维数组 $B$ 的下标从 0 开始。按行优先存储下三角部分时， $A$ 中元素 $a_{i,j}$ 在数组 $B$ 中的下标为

k=1+2+\cdots +(i-1)+j-1=\frac{i(i-1)}{2}+j-1.

利用对称性，任意元素对应的压缩下标为

k(i,j)= \begin{cases} \dfrac{i(i-1)}{2}+j-1, & i\ge j,\\ \dfrac{j(j-1)}{2}+i-1, & i<j. \end{cases}

三角矩阵

下三角矩阵

上三角矩阵

下三角矩阵

是一个方阵，其主对角线及其以下的元素可以取任意值，而主对角线以上的所有元素都为零。
上三角矩阵

是一个方阵，其主对角线及其以上的元素可以取任意值，而主对角线以下的所有元素都为同一个常数；常见的特殊情形是该常数为 0。

上三角矩阵的压缩下标

以上三角矩阵 $A$ 为例，上半部分元素首先按行优先顺序存储在一维数组 $B$ 中，在最后一个位置添加一个元素，用于存储下三角位置对应的常数。

设矩阵下标 $i,j$ 从 1 开始，数组 $B$ 的下标从 0 开始，则 $A$ 中元素 $a_{i,j}$ 在数组 $B$ 中的下标为

k=n+(n-1)+\cdots +(n-i+2)+(j-i+1)-1 =\frac{(i-1)(2n-i+2)}{2}+(j-i).

因此压缩下标为

k(i,j)= \begin{cases} \dfrac{(i-1)(2n-i+2)}{2}+(j-i), & i\le j,\[4pt] \dfrac{n(n+1)}{2}, & i>j. \end{cases}

其中第一种情况对应上三角区和主对角线元素；第二种情况对应下三角区中的公共常数。

稀疏矩阵

稀疏矩阵（Sparse Matrix）是指在矩阵中大部分元素为零的矩阵。与之相对的是 稠密矩阵（Dense Matrix），即大部分元素非零。

例如，下面是一个 $6\times 7$ 的稀疏矩阵：

A_{6\times 7}= \begin{bmatrix} 0&0&3&0&0&0&0\\ 0&2&0&0&0&0&0\\ 1&0&0&0&0&0&0\\ 0&0&0&5&0&0&0\\ 0&0&0&0&6&0&0\\ 7&0&0&0&0&0&4 \end{bmatrix}.

概念对照

稀疏矩阵存储方式怎么选

点击比较维度，对照完整二维数组、三元组表与十字链表在空间、访问和修改方面的差异。

比较维度二维数组三元组表十字链表

当前比较：主要存储内容。

后续比较统一把矩阵维度记为 $m \times n$ 。

由于 稀疏矩阵 的非零元素远少于零元素，存储整个矩阵（包括所有零元素）会浪费大量空间。因此，稀疏矩阵通常使用特定的数据结构（三元组表 和 十字链表）来高效存储和操作，只保存非零元素及其位置信息。

三元组表

三元组表（Triple Table）是一种稀疏矩阵的顺序存储方法。它利用三个一维数组（或一个结构体数组）分别存放非零元素的行号、列号和数值，从而节省内存空间。

对于一个 $m \times n$ 的稀疏矩阵 $A$ ，若其中只有 $t$ 个非零元素，则三元组表的长度就是 $t$ 。存储时，一般约定按照 行序优先（先按行号从小到大排序，行号相同时再按列号从小到大）存放，便于后续矩阵运算和查找。当 $t\ll mn$ 时，只保存非零元素能显著减少空间占用。

在程序实现时，常见的两种方式是：

分开存储法 用三个等长的一维数组 row[]、col[] 和 val[] 分别保存行号、列号和数值。
结构体存储法 定义一个结构体 Triple，包含 (row, col, value) 三个字段，再用一个一维数组 Triple data[t] 来存储。

分开存储法

#define MAXSIZE 100  // 最大非零元素个数

// 稀疏矩阵三元组表（分开存储）
typedef struct {
    int m, n, t;          // 矩阵的行数、列数、非零元素个数
    int row[MAXSIZE];     // 行号数组
    int col[MAXSIZE];     // 列号数组
    int val[MAXSIZE];     // 数值数组
} TSMatrix;

结构体存储法

#define MAXSIZE 100  // 最大非零元素个数

// 三元组
typedef struct {
    int row, col;  // 行号、列号
    int val;       // 数值
} Triple;

// 稀疏矩阵三元组表（结构体存储）
typedef struct {
    int m, n, t;        // 矩阵的行数、列数、非零元素个数
    Triple data[MAXSIZE]; // 非零元素数组
} TSMatrix;

三元组表的优点是 存储结构简单、节省空间，但缺点是 随机访问代价较高 —— 若要访问某个元素，需要顺序扫描查找对应行列下标，适合用于矩阵转置、稀疏矩阵相加、输出等操作。

在实际应用中，如果需要频繁地进行按行、按列的运算，就会引入 十字链表 等更复杂的存储方式。

十字链表

十字链表（Cross List）是一种用于稀疏矩阵的存储结构，它的核心思想是利用行方向和列方向两个链表同时组织非零元素，从而使得既能按行遍历，也能按列遍历，访问效率都较高。相比于普通的顺序存储或单一链表结构，十字链表在需要频繁进行矩阵运算、转置或按行按列混合访问的场景下具有明显优势。

十字链表通过行链与列链共同组织同一批非零结点：从 rhead[i] 沿 right 指针可遍历第 $i$ 行，从 chead[j] 沿 down 指针可遍历第 $j$ 列。

在十字链表中，每一个非零元素都会建立一个结点。该结点需要记录行号（i）、列号（j）、元素值（value），同时还要保存两个方向的指针：right 指针指向同一行中的下一个非零元素，down 指针指向同一列中的下一个非零元素。借助这两个指针，矩阵可以在行链和列链之间灵活切换，实现双向高效的访问。

为了快速定位某一行或某一列的首个非零元素，还需要额外设置行头指针数组（rhead）和列头指针数组（chead）。每一行和每一列都对应一个头指针，这些头指针并不存储具体数值，而是起到索引的作用，使得从某一行或某一列开始的遍历可以在常数时间内定位到第一个非零元素。

结点定义

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

十字链表结构

// 十字链表结构
typedef struct {
    CrossListNode** rhead;      // 行头指针数组
    CrossListNode** chead;      // 列头指针数组
    int rows;                   // 矩阵行数
    int cols;                   // 矩阵列数
    int nums;                   // 非零元素个数
} CrossList;

十字链表的优势主要体现在三个方面：其一，空间效率高，仅存储非零元素及必要的指针；其二，支持按行或按列的双向遍历，在算法实现中非常灵活；其三，插入与删除操作方便，只需在相应行和列的链表中调整指针即可，而不必像顺序存储那样整体移动元素。因此，十字链表常被用于稀疏矩阵运算和图的邻接矩阵存储，是数据结构与图论中重要的一种存储方式。

三对角矩阵

三对角矩阵是一种特殊的稀疏矩阵，它除了主对角线外，只在其上下相邻的两条对角线上有非零元素，其余元素均为零。

\begin{bmatrix} a_{1,1} & a_{1,2} & & & & \\ a_{2,1} & a_{2,2} & a_{2,3} & & & \\ & a_{3,2} & a_{3,3} & a_{3,4} & & \\ & & \ddots & \ddots & \ddots & \\ & & & a_{n-1,n-2} & a_{n-1,n-1} & a_{n-1,n}\\ & & & & a_{n,n-1} & a_{n,n} \end{bmatrix}

由于仅有三条对角线可能出现非零元素，我们可以只存储这三条线来 节省空间，将存储量从 $n^2$ 个元素降为 $3n-2$ 个元素。

一种常用存储方式是使用三个长度为 n 的数组：

a[2...n]：下对角线（从第 2 行开始有值）
b[1...n]：主对角线
c[1...n-1]：上对角线（到第 n-1 行）

下标换算与压缩存储的核验

做地址题时，先把“逻辑下标从几开始”和“线性数组下标从几开始”写在草稿上，再代入公式。二者只要有一个从 0 改为从 1，常数项就会改变。例如，按行主序存放、每个元素占 4 字节的 $3\times4$ 数组，若 $a[0][0]$ 的地址是 $A$ ，则

\operatorname{Addr}(a[1][2])=A+(1\times4+2)\times4=A+24.

这里的 $1\times4+2$ 是元素个数而不是字节数；最后乘元素大小才是字节偏移。列主序则应先跨过完整的列，0 下标下为 $jR+i$ ，不能把行数 $R$ 和列数 $C$ 混用。

压缩表的容量与边界

对于 $n$ 阶对称矩阵、上三角或下三角矩阵，真正需要保存的独立元素数均为

\frac{n(n+1)}{2}.

若三角矩阵的另一半全部是同一个常数，还要再留一个位置保存该常数，所以容量是 $\frac{n(n+1)}{2}+1$ ，而不是完整的 $n^2$ 。例如按行优先保存下三角、并让矩阵和线性表都从 0 开始时， $i\ge j$ 的元素下标为

k=\frac{i(i+1)}{2}+j.

这个式子的含义是：前面完整的 $i$ 行共有 $1+2+\cdots+i$ 个已存元素，再加本行内偏移 $j$ 。遇到不在被保存区域的坐标，应先利用对称性交换 $i,j$ ，或返回公共常数的位置；不能直接把它当成越界。

稀疏矩阵结构如何选择

设矩阵有 $m$ 行、 $n$ 列和 $t$ 个非零元。三元组表只需要 $O(t)$ 个记录，适合顺序扫描、输出和转置；但若要随机询问 $a_{ij}$ ，最坏仍须扫描 $O(t)$ 个三元组。按列快速转置时，可先统计每一列的非零元个数，再计算每列在转置表中的起始位置，使每个三元组只搬运一次，时间为 $O(n+t)$ 。

十字链表也只为非零元建结点，却同时维护行链与列链：插入或删除一个非零元时，必须在对应行链和对应列链各更新一次链接。它适合频繁按行、按列混合访问；若题目只要求一次性遍历或转置，结构更简单的三元组表往往更合适。