数组和特殊矩阵

⭐ 中优先级

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

多维数组

在计算机内存中，数组元素是 连续存放 的。对于一个二维数组来说，它实际上只是对一维数组的一种逻辑抽象。理解其存储方式的关键在于：如何将二维坐标 $(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}$$

三角矩阵

下三角矩阵

上三角矩阵

下三角矩阵 是一个方阵，其主对角线及其以下（右下部分）的所有元素都不为零，而主对角线以上的所有元素都为零。
上三角矩阵 是一个方阵，其主对角线及其以上（左上部分）的所有元素都不为零，而主对角线以下的所有元素都为常数。

三角矩阵下标计算

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

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

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

元素为

$$a_{i, j} = \begin{cases} \frac{(i-1)(2n-i+2)}{2}+(j-i),\text{ } i \le j（\text{\small 上三角区和对角线元素}） \\ \frac{n(n+1)}{2},\text{ } i \gt j（\text{\small 下三角区元素}） \end{cases}$$

稀疏矩阵

稀疏矩阵（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 中一般默认讨论方阵。