数组和特殊矩阵

掌握多维数组的存储方式，了解特殊矩阵的压缩存储，可能在选择题中出现概念考察以及某个矩阵元素下标的计算。

多维数组的存储

如果数组的第一个元素位于内存地址 $A$，且每个元素占用 $B$ 个字节，行列总数分别为 $R$ 和 $C$，那么数组的 $(i, j)$ 元素（其中 $i$ 是行号，$j$ 是列号）的内存地址可以计算为 $A + (i \times C + j) * B$。

例子：

在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

特殊矩阵的压缩存储

对称矩阵

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

Produced by GNUPLOT 4.4 patchlevel 0

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

symmtry_matrix_storage

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

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

$$k = 1 + 2 + \cdots + (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}$$

三角矩阵

{\displaystyle \mathbf {L} ={\begin{bmatrix}l_{1,1}&&\cdots &&0\\l_{2,1}&l_{2,2}&&(0)&\\l_{3,1}&l_{3,2}&\ddots &&\vdots \\\vdots &\vdots &\ddots &\ddots &\\l_{n,1}&l_{n,2}&\ldots &l_{n,n-1}&l_{n,n}\end{bmatrix}}}

下三角矩阵

{\displaystyle \mathbf {U} ={\begin{bmatrix}u_{1,1}&u_{1,2}&u_{1,3}&\ldots &u_{1,n}\\&u_{2,2}&u_{2,3}&\ldots &u_{2,n}\\\vdots &&\ddots &\ddots &\vdots \\&(0)&&\ddots &u_{n-1,n}\\0&&\cdots &&u_{n,n}\end{bmatrix}}}

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

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

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

$$k = n + (n+1) _ \cdots + (n-i+2) + (j-i+1) - 1 = (i-1)(2n-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} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 6 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 7 & 4 \end{bmatrix} $$

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

三元组表

三元组表用三个一维数组分别存储非零元素的行号、列号和数值。当然了，这里也可以使用一个结构体数组，两者都是一样的。

比如对于上文提到的 $A_{6 \times 7}$ 稀疏矩阵，可以采用以下的三元组进行存储：

十字链表

十字链表的核心思想是通过两个方向的链表（行方向和列方向）来组织非零元素，使得按行或按列访问矩阵元素都较为高效。

下图给出了一个十字链表的存储示例：

3
1
1
3
2
2
-1
^
^
3
1
2
^
^
^
1
1
3
^
^
rhead
chead
0
0
5
3
0
0
5
2
0
0
0

每一个十字链表中的元素结点都需要存储以下信息：行号（i）、列号（j）、元素值（value）、指向同一行下一个非零元素的指针（right）、指向同一列下一个非零元素的指针（down）。

此外，还需要为每一行（rhead）和每一列（chead）设置一个头节点，用于快速定位该行或该列的第一个非零元素。

三对角矩阵

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

$$\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^2$ 降为 $3n-2$ 个数字）。

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

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