数组和特殊矩阵

⭐ 中优先级

在选择题偶尔会考察，多维数组的存储是 和 矩阵的几种压缩存储方式 要了解一下。

多维数组

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

假设：

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

那么数组中元素 $a[i][j]$ 的存储地址为：

Addr (a [i] [j]) = A + (i \times C + j) \times 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] |
  +---------+---------+---------+---------+---------+---------+

特殊矩阵

特殊矩阵是指矩阵中的元素分布具有某种规律或约束的矩阵，例如关于主对角线对称、某些区域中的元素全部相同，或者只有少量位置可能出现非零元素。

常见的特殊矩阵包括：

对称矩阵：关于主对角线对称；
三角矩阵：主对角线一侧的元素全部为零或同一个常数；
三对角矩阵：非零元素只分布在主对角线及其相邻的两条对角线上；
稀疏矩阵：矩阵中的绝大多数元素为零。

由于特殊矩阵中的元素具有明确的分布规律，因此通常不需要按照普通二维数组的方式存储全部元素，而是只存储其中必要的元素，从而达到 压缩存储、节省空间 的目的。

压缩存储时，需要根据矩阵中元素的位置，建立二维下标 ((i,j)) 与一维存储数组下标 (k) 之间的映射关系。

对称矩阵

什么是 对称矩阵：对于矩阵 $A$ 中的任意一个元素 $a_{i, j}$ 都有 $a_{i, j} = a_{j, i}$ ，

所以为了 节省存储空间，可以使用一位数组 $B$ 进行存储

symmtry_matrix_storage

如何计算对称矩阵中元素的下标

$A$ 中的元素 $a_{i, j}$ 在数组 $B$ 的下标

k = 1 + 2 + \dots + (i - 1) + j - 1 = i (i - 1) /2 + j - 1

元素为

$$a_{i, j} = \begin{cases} \frac{i(i-1)}{2}+j-1,\text{ } i \ge j \\ \frac{j(j-1)}{2}+i-1,\text{ } i \lt j \end{cases}$$

三角矩阵

下三角矩阵

上三角矩阵

下三角矩阵 是一个方阵，其 主对角线以上的所有元素均为同一个常数 $c$ （ $c$ 可以是 0，也可以是别的值），主对角线及其以下的元素可以为任意值。
上三角矩阵 是一个方阵，其 主对角线以下的所有元素均为同一个常数 $c$ ，主对角线及其以上的元素可以为任意值。

下标计算

三角矩阵中有近一半的元素都等于同一个常数 $c$ ，它们完全不需要逐个存储，因此可以只存储非常数区域的元素，以节省存储空间。

以上三角矩阵 $A$ 为例，采用 行优先 的方式，将主对角线及其以上的元素依次存储到一维数组 $B$ 中，并在数组的最后增加一个位置，用于存储下三角区域那个统一的常数 $c$ 。

例如，对于 $n$ 阶上三角矩阵：

A = a_{11} c c ⋮ c a_{12} a_{22} c ⋮ c a_{13} a_{23} a_{33} ⋮ c \dots \dots \dots ⋱ \dots a_{1 n} a_{2 n} a_{3 n} ⋮ a_{nn}

按照行优先方式存储：

B = [a_{11}, a_{12}, \dots, a_{1 n}, a_{22}, a_{23}, \dots, a_{2 n}, \dots, a_{nn}, c]

其中最后的 $c$ 是额外增加的位置，用于表示所有下三角区域的元素。

上三角区域元素

对于 $a_{i, j}$ ，当 $i \leq j$ 时， $a_{i, j}$ 位于上三角区域。

在存储 $a_{i, j}$ 之前，前面已经存储了前 $i - 1$ 行的上三角元素。

第 $1$ 行有 $n$ 个元素，第 $2$ 行有 $n - 1$ 个元素，……，第 $i - 1$ 行有 $n - i + 2$ 个元素。

因此，前 $i - 1$ 行共有：

n + (n - 1) + \dots + (n - i + 2)

个元素。

在第 $i$ 行中， $a_{i, j}$ 是从第 $i$ 行第一个元素 $a_{i, i}$ 开始的第 $j - i$ 个位置。

由于数组 $B$ 采用 0 开始下标，因此：

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

所以：

k = \frac{( i - 1 ) ( 2 n - i + 2 )}{2} + (j - i), i \leq j

下三角区域元素

当 $i > j$ 时， $a_{i, j}$ 位于下三角区域。

由于这些元素都没有单独存储，而是统一映射到一维数组 $B$ 的最后一个位置，因此：

k = \frac{n ( n + 1 )}{2}, i > j

这里之所以是

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

是因为上三角区域（包括主对角线）一共有：

n + (n - 1) + \dots + 1 = \frac{n ( n + 1 )}{2}

个元素，而 $B$ 最后增加的那个位置正好使用这个下标。

因此，完整的下标映射公式为：

k = ⎩ ⎨ ⎧ \frac{( i - 1 ) ( 2 n - i + 2 )}{2} + (j - i), \frac{n ( n + 1 )}{2}, i \leq j i > j

注意

严格来说，三角矩阵的定义是"另一半元素为 同一个常量 $c$ ， $c = 0$ 只是最常见的特例。数学上的上/下三角矩阵才要求另一半必须为 0。做题时按题目给的说法走：

题目说"其余元素均为 $c$ "→ 需要用一个额外的存储单元来存 $c$ ，压缩后长度为 $\frac{n ( n + 1 )}{2} + 1$ ；
题目说"其余元素均为 0"→ 0 是已知的、不需要记住的信息，不必单独存储，访问时直接返回 0 即可，压缩后长度就是 $\frac{n ( n + 1 )}{2}$ 。

这一个单元的差别会直接影响 数组总长度 和 下标公式，是选择题最容易设坑的地方：算出的地址差一位，往往就是因为没注意有没有那个存 $c$ 的位置。

稀疏矩阵

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

A_{6 \times 7} = 003000020000100000000500000060000007000004

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

三元组表

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

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

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

分开存储法
用三个等长的一维数组 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） 是一种用于存储稀疏矩阵的链式存储结构。它同时建立行链表和列链表，使矩阵既可以按行遍历，也可以按列遍历，因此特别适合需要频繁进行矩阵运算、转置以及插入、删除非零元素等操作。

下图给出了一个十字链表的示意图：

在十字链表中，每一个非零元素对应一个结点。结点中不仅保存元素的行号、列号和元素值，还包含两个指针：

right：指向本行中的下一个非零元素；
down：指向本列中的下一个非零元素。

因此，每个非零元素同时属于一条行链表和一条列链表，形成了纵横交叉的链式结构，这也是"十字链表"名称的由来。

为了能够快速找到某一行或某一列的第一个非零元素，十字链表还维护两个头指针数组：

rhead：行头指针数组，rhead[i] 指向第 i 行的第一个非零元素；
chead：列头指针数组，chead[j] 指向第 j 列的第一个非零元素。

借助头指针数组，可以在 $O (1)$ 时间内定位任意一行或一列，并沿着对应的链表进行遍历。

// 十字链表结点
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;

注意

十字链表的特点

空间利用率高：仅为非零元素分配结点，适合存储稀疏矩阵。
按行、按列遍历都很方便：每个结点同时链接行链表和列链表，无需转置矩阵即可按列访问。
插入、删除效率高：只需修改对应行链表和列链表中的少量指针，无需移动大量元素。
适用于动态矩阵运算：广泛应用于稀疏矩阵的加法、乘法、转置等运算。

三对角矩阵

三对角矩阵（Tridiagonal Matrix） 是一种特殊的 稀疏矩阵。它只有 主对角线、上对角线 和 下对角线 上的元素可能非零，其余元素均为零。

$$\begin{vmatrix} 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{vmatrix}$$

由于矩阵中仅有三条对角线上的元素可能非零，因此无需为大量的零元素分配存储空间。对于一个 $n \times n$ 的三对角矩阵，只需存储：

主对角线： $n$ 个元素；
上对角线： $n - 1$ 个元素；
下对角线： $n - 1$ 个元素。

因此，仅需

n + (n - 1) + (n - 1) = 3 n - 2

个存储单元，相比普通矩阵的 $n^{2}$ 个元素，大大节省了存储空间。

一种常见的压缩存储方式是分别使用三个一维数组保存三条对角线：

lower[2...n]：存储下对角线元素 $a_{i, i - 1}$
diag[1...n]：存储主对角线元素 $a_{i, i}$
upper[1...n-1]：存储上对角线元素 $a_{i, i + 1}$

对应关系如下：

矩阵元素 a_{i, i - 1} a_{i, i} a_{i, i + 1} 一维数组 lower [i] diag [i] upper [i]

三对角矩阵的特点在于：

仅当 $∣ i - j ∣ \leq 1$ 时，元素 $a_{i, j}$ 才可能非零，否则其值一定为 0。
采用压缩存储后，存储空间由 $n^{2}$ 降低为 $3 n - 2$ ，但仍可以在 $O (1)$ 时间内访问任意一个非零元素。

补充

矩阵类型	必须是方阵吗？	原因
对称矩阵	✅ 必须	需要满足 $A = A^{T}$ ，只有方阵才能与自己的转置维数相同。
三角矩阵	✅ 必须（408 中）	上三角、下三角都是以主对角线为界定义的，通常默认定义在方阵上。
三对角矩阵	❌ 不一定	数学上可以定义在任意 $m \times n$ 矩阵，只要求除主对角线及相邻两条对角线外元素全为 0。408 中一般默认讨论方阵。