Lecture 12：特殊矩阵与压缩存储

This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

12.1 数组

12.1.1 一维数组

定义：#一维数组

描述：一维数组中的各个元素大小相同，并且在物理存储空间中连续存放。

地址计算 设数组首地址为 LOC，元素类型为 ElemType，则数组元素 a[i] 的存放地址为： $$ LOC+i\times sizeof(ElemType) $$

注意

除非题目特别说明，否则数组下标默认从 $0$ 开始。
C 语言数组下标也是从 $0$ 开始。

C 语言定义

ElemType a[10];

含义

数组共有 $10$ 个元素。
合法下标范围为： $$ 0\le i\le 9 $$

12.1.2 二维数组

定义：#二维数组

描述：二维数组在逻辑上是二维表，但计算机内部存储空间是线性的，所以需要把二维逻辑位置映射到一维物理地址。

设二维数组为：

ElemType b[M][N];

其中：

$M$ 表示行数。
$N$ 表示列数。
LOC 表示数组首地址。

行优先存储

规则

先存完第 $0$ 行，再存第 $1$ 行。
同一行内从左到右存储。

b[i][j] 的地址为： $$ LOC+(i\times N+j)\times sizeof(ElemType) $$

解释

第 $i$ 行前面共有 $i$ 行。
每行有 $N$ 个元素。
因此前面已有： $$ i\times N $$ 个元素。
当前元素在第 $i$ 行内偏移 $j$ 个位置。

列优先存储

规则

先存完第 $0$ 列，再存第 $1$ 列。
同一列内从上到下存储。

b[i][j] 的地址为： $$ LOC+(j\times M+i)\times sizeof(ElemType) $$

解释

第 $j$ 列前面共有 $j$ 列。
每列有 $M$ 个元素。
因此前面已有： $$ j\times M $$ 个元素。
当前元素在第 $j$ 列内偏移 $i$ 个位置。

C 语言定义

ElemType b[2][4];

例子：2 行 4 列

行优先：

b[0][0], b[0][1], b[0][2], b[0][3], b[1][0], b[1][1], b[1][2], b[1][3]

列优先：

b[0][0], b[1][0], b[0][1], b[1][1], b[0][2], b[1][2], b[0][3], b[1][3]

图示解读

计算机内存是一维连续地址空间，二维数组必须按约定的次序线性展开。
行优先先连续存完第 $0$ 行，再存第 $1$ 行；列优先则先连续存完第 $0$ 列，再存第 $1$ 列。
C/C++ 数组采用行优先；地址公式必须同时结合行数、列数、下标起点和元素大小判断。

12.1.3 教材补充：任意维数组的地址公式

设 $d$ 维数组为：

$$ A[l_1..u_1][l_2..u_2]\cdots[l_d..u_d] $$

第 $k$ 维长度为：

$$ n_k=u_k-l_k+1 $$

每个元素占 $w$ 个地址单位，$LOC(A[l_1][l_2]\cdots[l_d])$ 为第一个元素的首地址。

行优先：最后一维变化最快

$$ LOC(A[i_1][i_2]\cdots[i_d]) =LOC(A[l_1][l_2]\cdots[l_d]) +w\sum_{k=1}^{d} \left[(i_k-l_k)\prod_{t=k+1}^{d}n_t\right] $$

空乘积按 $1$ 计算。三维数组的元素偏移可写成：

$$ ((i_1-l_1)n_2+(i_2-l_2))n_3+(i_3-l_3) $$

例如 A[3][4][5] 从 $0$ 开始，A[1][2][3] 前面有：

$$ (1\times4+2)\times5+3=33 $$

个元素，所以其地址为 $LOC+33w$。

列优先：第一维变化最快

$$ LOC(A[i_1][i_2]\cdots[i_d]) =LOC(A[l_1][l_2]\cdots[l_d]) +w\sum_{k=1}^{d} \left[(i_k-l_k)\prod_{t=1}^{k-1}n_t\right] $$

地址题统一检查

先写每一维的合法下界、上界与长度，不能默认都从 $0$ 开始。
明确哪一维变化最快；C/C++ 内建数组采用行优先，但题目可能另作规定。
先算“前面有多少个元素”，最后再乘元素宽度 $w$。
区分元素序号与字节地址；若 $w$ 以字节计，最终地址差也以字节计。
题目给出的 LOC 若是整个数组首地址，就对应所有维度均取下界的位置，而不一定是下标全为 $0$ 的位置。

12.2 特殊矩阵

12.2.1 普通矩阵

普通矩阵存储

普通矩阵可以直接使用二维数组存储。
若矩阵为 $m\times n$，普通存储需要： $$ m\times n $$ 个存储单元。

注意

做矩阵压缩存储题时，必须先确认下标从 $0$ 开始还是从 $1$ 开始。
本节后续矩阵公式若无特别说明，默认：
- 矩阵下标 $i,j$ 从 $1$ 开始；
- 压缩后的一维数组下标 $k$ 从 $0$ 开始。

12.3 对称矩阵的压缩存储

定义：#对称矩阵

描述：若 $n$ 阶方阵中任意元素都满足 $a_{i,j}=a_{j,i}$，则该矩阵称为对称矩阵。

数学定义 $$ a_{i,j}=a_{j,i}\quad (1\le i,j\le n) $$

普通存储

使用 $n\times n$ 的二维数组。
需要： $$ n^2 $$ 个存储单元。

压缩存储策略

只存储主对角线加下三角区。
或只存储主对角线加上三角区。
因为另一半可以通过对称关系得到。

图示解读

主对角线把矩阵分为上三角区和下三角区；对称关系使两区的信息互为镜像。
压缩时只保存主对角线加任意一侧三角区，共 $n(n+1)/2$ 个元素。
访问未存储一侧的 $a_{i,j}$ 时，交换行列下标，读取已存储的 $a_{j,i}$。

12.3.1 存储单元数量

主对角线加下三角区的元素个数为： $$ 1+2+3+\cdots+n $$

所以需要： $$ \frac{n(n+1)}{2} $$ 个存储单元。

同理，主对角线加上三角区也需要： $$ \frac{n(n+1)}{2} $$ 个存储单元。

12.3.2 按下三角区压缩

若只存储下三角区和主对角线，按行优先存入一维数组 B[k]。

当 $i\ge j$ 时，$a_{i,j}$ 位于下三角区或主对角线上： $$ k=\frac{i(i-1)}{2}+j-1 $$

当 $i<j$ 时，$a_{i,j}$ 位于上三角区，可利用对称关系： $$ a_{i,j}=a_{j,i} $$

因此先交换下标，再计算： $$ k=\frac{j(j-1)}{2}+i-1 $$

12.3.3 按上三角区压缩

若只存储上三角区和主对角线，按行优先存入一维数组 B[k]。

当 $i\le j$ 时，$a_{i,j}$ 位于上三角区或主对角线上： $$ k=\frac{(i-1)(2n-i+2)}{2}+(j-i) $$

当 $i>j$ 时，$a_{i,j}$ 位于下三角区，可利用对称关系： $$ a_{i,j}=a_{j,i} $$

因此先交换下标，再计算： $$ k=\frac{(j-1)(2n-j+2)}{2}+(i-j) $$

12.4 三角矩阵的压缩存储

定义：#三角矩阵

描述：三角矩阵是指除主对角线和某一侧三角区外，其余元素都相同的矩阵。

12.4.1 下三角矩阵

特点

保留主对角线和下三角区。
上三角区的元素都相同，通常记为常量 $c$。

压缩策略

按行优先原则将下三角区和主对角线元素存入一维数组。
在最后一个位置存储常量 $c$。

一维数组大小 $$ \frac{n(n+1)}{2}+1 $$

其中：

前 $\frac{n(n+1)}{2}$ 个位置存储下三角区和主对角线。
最后 $1$ 个位置存储常量 $c$。

映射公式 $$ k= \begin{cases} \frac{i(i-1)}{2}+j-1, & i\ge j \ \frac{n(n+1)}{2}, & i<j \end{cases} $$

解释

当 $i\ge j$ 时，访问的是下三角区或主对角线元素，按公式映射到 B[k]。
当 $i<j$ 时，访问的是上三角区常量元素，统一映射到最后一个位置。

12.4.2 上三角矩阵

特点

保留主对角线和上三角区。
下三角区的元素都相同，通常记为常量 $c$。

压缩策略

按行优先原则将上三角区和主对角线元素存入一维数组。
在最后一个位置存储常量 $c$。

一维数组大小 $$ \frac{n(n+1)}{2}+1 $$

映射公式 $$ k= \begin{cases} \frac{(i-1)(2n-i+2)}{2}+(j-i), & i\le j \ \frac{n(n+1)}{2}, & i>j \end{cases} $$

解释

当 $i\le j$ 时，访问的是上三角区或主对角线元素。
当 $i>j$ 时，访问的是下三角区常量元素，统一映射到最后一个位置。

图示解读

下三角矩阵保存主对角线和下三角区，上三角区统一为常量 $c$；上三角矩阵反之。
非常量区按行优先存入 B[0] 至 B[n(n+1)/2-1]，常量 $c$ 单独存入最后的 B[n(n+1)/2]。
所有位于常量区的位置都映射到同一个数组单元，不需要重复保存 $c$。

12.5 三对角矩阵的压缩存储

定义：#三对角矩阵

描述：三对角矩阵是带状矩阵的一种，只有主对角线及其上下相邻两条对角线上的元素可能非零；一般带状矩阵还可以有更宽的非零带，二者不能互称。

数学定义 当： $$ |i-j|>1 $$ 时，有： $$ a_{i,j}=0\quad (1\le i,j\le n) $$

所以非零元素只可能出现在： $$ |i-j|\le 1 $$ 的位置。

压缩存储策略

按行优先或列优先原则，只存储带状部分。
PDF 中展示的是按行优先存储带状部分。

图示解读

只有 $|i-j|\le 1$ 的主对角线、上邻对角线和下邻对角线元素进入压缩数组。
当 $n\ge 2$ 时，逐行展开后第 1 行和第 $n$ 行各存 2 个元素，其余各行存 3 个元素，总数为 $3n-2$；当 $n=1$ 时首、末行是同一行，只存 $a_{1,1}$ 这 1 个元素。
带状区外元素按定义为 $0$，不进入压缩数组。

12.5.1 存储单元数量

对 $n\ge 2$ 的 $n$ 阶三对角矩阵：

第 $1$ 行有 $2$ 个带状元素。
第 $n$ 行有 $2$ 个带状元素。
第 $2$ 行到第 $n-1$ 行，每行有 $3$ 个带状元素。

因此总数为： $$ 2+3(n-2)+2=3n-2 $$

当 $n=1$ 时，矩阵只有 $a_{1,1}$，存储单元数量为 $1$，不能把首行和末行重复计数。

12.5.2 按行优先压缩公式

将满足： $$ |i-j|\le 1 $$ 的元素 $a_{i,j}$ 存入一维数组 B[k]。

若矩阵下标 $i,j$ 从 $1$ 开始，一维数组下标 $k$ 从 $0$ 开始，则： $$ k=2i+j-3 $$

适用条件： $$ |i-j|\le 1 $$

解释

第 $i$ 行前面已经存过的带状元素数量，可以推导为该行起始位置。
对于中间行，每行最多存 $3$ 个元素。
PDF 提醒：推导时注意 $a_{i,j}$ 元素前面有 $i-2$ 个空位。

压缩规则 $$ a_{i,j}\ (|i-j|\le 1)\rightarrow B[k] $$

由压缩下标反求矩阵下标

在本节“矩阵下标从 $1$ 开始、压缩数组下标从 $0$ 开始、按行优先”的约定下： $$ i=\left\lfloor\frac{k+1}{3}\right\rfloor+1, \qquad j=k-2i+3 $$

该逆映射对 $0\le k\le 3n-3$ 有效，所得位置自动满足 $|i-j|\le 1$。

12.5.3 例子

若 $i=3,j=2$，则： $$ |i-j|=|3-2|=1 $$

该元素属于带状区域，可以压缩存储。

下标为： $$ k=2i+j-3=2\times3+2-3=5 $$

所以： $$ a_{3,2}\rightarrow B[5] $$

12.6 稀疏矩阵的压缩存储

定义：#稀疏矩阵

描述：稀疏矩阵是指非零元素个数远远小于矩阵元素总数的矩阵。

若矩阵总元素个数为： $$ m\times n $$

非零元素个数为： $$ t $$

当 $t$ 远小于 $m\times n$ 时，可以考虑压缩存储。

12.6.1 顺序存储：三元组

压缩存储策略

只保存非零元素。
每个非零元素保存三个信息：

<行, 列, 值>

三元组形式

行	列	值
$i$	$j$	$a_{i,j}$

例子若： $$ a_{1,3}=4 $$

则可以保存为：

<1, 3, 4>

原 PDF 第 6 页的完整 $5\times6$ 稀疏矩阵有 6 个非零元，按行号、列号递增可写成：

<1,3,4>, <1,6,5>, <2,2,3>, <2,4,9>, <3,5,7>, <4,2,2>

第 $5$ 行没有非零元，其行链表为空；图中的 right 和 down 分别串起同一行和同一列的这些结点。

优点

节省大量零元素空间。
适合非零元素较少的矩阵。

缺点

访问某个指定位置 $a_{i,j}$ 时，不能像二维数组一样直接定位。
通常需要查找对应的三元组。

12.6.2 链式存储：十字链表法

PDF 补充图示

稀疏矩阵还可以使用链式存储。
常见方法是十字链表法。

定义：#十字链表法

描述：十字链表法用链表同时维护每一行和每一列的非零元素关系。

结点信息 每个非零元素结点通常包含：

行号。
列号。
元素值。
向右指针 right：指向同一行的下一个非零元素。
向下指针 down：指向同一列的下一个非零元素。

指针含义

right 指向第 $i$ 行的下一个非零元素。
down 指向第 $j$ 列的下一个非零元素。

图示解读

每个非零结点保存 (行, 列, 值)，并同时属于一条行链和一条列链。
right 把同一行的非零结点按列号连接，down 把同一列的非零结点按行号连接。
行头数组与列头数组分别提供行链、列链入口；这种结构适合需要同时按行和按列遍历或修改的稀疏矩阵。

12.7 题型整理

题型：#矩阵压缩下标计算

第一部分：解题方法

第一步：看清矩阵类型。
- 对称矩阵；
- 三角矩阵；
- 三对角矩阵；
- 稀疏矩阵。
第二步：看清下标从 $0$ 还是 $1$ 开始。
第三步：看清压缩后数组下标从 $0$ 还是 $1$ 开始。
第四步：确认按行优先还是按列优先。
第五步：套用对应映射公式。

第二部分：典型例题

例题 1：下三角矩阵中 $a_{4,2}$ 存到哪个位置？

设矩阵下标从 $1$ 开始，一维数组下标从 $0$ 开始。

因为： $$ i=4,\quad j=2,\quad i\ge j $$

所以： $$ k=\frac{i(i-1)}{2}+j-1 $$

代入： $$ k=\frac{4(4-1)}{2}+2-1=6+1=7 $$

因此： $$ a_{4,2}\rightarrow B[7] $$

例题 2：上三角矩阵中 $a_{4,2}$ 存到哪个位置？

因为： $$ i=4,\quad j=2,\quad i>j $$

它位于下三角常量区，所以映射到最后一个位置： $$ k=\frac{n(n+1)}{2} $$

第三部分：知识点复盘

对称矩阵只需要存一半加主对角线。
三角矩阵除了存三角区和主对角线，还要存常量 $c$。
三对角矩阵只存带状区域。
稀疏矩阵只存非零元素。
下标起点不同，公式会不同，不能混用。

12.8 本节复盘

必须掌握

一维数组地址： $$ LOC+i\times sizeof(ElemType) $$
二维数组行优先地址： $$ LOC+(i\times N+j)\times sizeof(ElemType) $$
二维数组列优先地址： $$ LOC+(j\times M+i)\times sizeof(ElemType) $$
对称矩阵存储单元数： $$ \frac{n(n+1)}{2} $$
三角矩阵压缩后一维数组大小： $$ \frac{n(n+1)}{2}+1 $$
三对角矩阵存储单元数： $$ \begin{cases} 1, & n=1,\ 3n-2, & n\ge 2. \end{cases} $$
三对角矩阵按行优先压缩公式： $$ k=2i+j-3 $$
稀疏矩阵可用三元组：

<行, 列, 值>

易错点

矩阵下标从 $0$ 开始和从 $1$ 开始，公式不同。
压缩数组下标从 $0$ 开始和从 $1$ 开始，公式也不同。
三角矩阵要额外存储常量 $c$。
对称矩阵可以通过 $a_{i,j}=a_{j,i}$ 找到另一半。
三对角矩阵不是只存主对角线，而是存三条对角线。
稀疏矩阵的三元组不是存所有元素，只存非零元素。

一句话总结

压缩存储的核心是只存有必要区分的元素：对称矩阵存一半，三角矩阵存一半加常量，三对角矩阵存带状区域，稀疏矩阵存非零元素。

12.1 数组

12.1.1 一维数组

定义：#一维数组

12.1.2 二维数组

定义：#二维数组

行优先存储

列优先存储

12.1.3 教材补充：任意维数组的地址公式

行优先：最后一维变化最快

列优先：第一维变化最快

地址题统一检查

12.2 特殊矩阵

12.2.1 普通矩阵

12.3 对称矩阵的压缩存储

定义：#对称矩阵

12.3.1 存储单元数量

12.3.2 按下三角区压缩

12.3.3 按上三角区压缩

12.4 三角矩阵的压缩存储

定义：#三角矩阵

12.4.1 下三角矩阵

12.4.2 上三角矩阵

12.5 三对角矩阵的压缩存储

定义：#三对角矩阵

12.5.1 存储单元数量

12.5.2 按行优先压缩公式

12.5.3 例子

12.6 稀疏矩阵的压缩存储

定义：#稀疏矩阵

12.6.1 顺序存储：三元组

12.6.2 链式存储：十字链表法

定义：#十字链表法

12.7 题型整理

题型：#矩阵压缩下标计算

第一部分：解题方法

第二部分：典型例题

第三部分：知识点复盘

相关知识

12.8 本节复盘