3.4 数组与特殊矩阵

数组的行优先/列优先地址计算，对称矩阵、三角矩阵、三对角矩阵的压缩存储，以及稀疏矩阵的三元组和十字链表。

数组的定义

数组是由 $n$（$n \ge 1$）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在 $n$ 个线性关系中的序号称为该元素的下标。

数组是线性表的推广：一维数组可视为一个线性表；二维数组可视为其数据元素是定长线性表的线性表。数组一旦被定义，其维数和维界就不再改变——除了结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

数组的存储结构

一维数组 $A[0..n-1]$ 的存储地址：$\mathrm{LOC}(a_i) = \mathrm{LOC}(a_0) + i \times L$（$L$ 为每个元素所占的存储单元）。

对于多维数组，有两种映射方法：

对于行下标范围 $[0, h_1]$、列下标范围 $[0, h_2]$ 的二维数组：

特殊矩阵的压缩存储

压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，目的是节省存储空间。

特殊矩阵：具有许多相同矩阵元素或零元素，并且这些元素的分布有一定规律性的矩阵，例如对称矩阵、上（下）三角矩阵、对角矩阵。

压缩存储的关键是找出矩阵元素 $a_{i,j}$ 与它在一维数组 $B$ 中下标 $k$ 的映射关系。点击下方矩阵中的任意元素，观察它被存放到 $B$ 的哪个位置：

对称矩阵

$n$ 阶方阵中任意元素都满足 $a_{i,j} = a_{j,i}$，只需存放主对角线和下三角区（共 $\frac{n(n+1)}{2}$ 个元素）。按行优先存放下三角元素 $a_{i,j}$（$i \ge j$，下标从 1 开始，$B$ 下标从 0 开始）：

• 第 1 行有 1 个元素，第 2 行有 2 个……第 $i-1$ 行有 $i-1$ 个，所以前 $i-1$ 行共有 $\frac{i(i-1)}{2}$ 个元素；
• 在第 $i$ 行中，$a_{i,j}$ 前面还有 $j-1$ 个元素。

三角矩阵

• 下三角矩阵：上三角区所有元素均为同一常量 $c$。存储完下三角区和主对角线后，紧接着存储一次常量 $c$，$B$ 共 $\frac{n(n+1)}{2} + 1$ 个单元。
• 上三角矩阵：下三角区所有元素均为同一常量。按行优先存储上三角元素 $a_{i,j}$（$i \le j$）时，第 1 行有 $n$ 个元素，第 2 行有 $n-1$ 个……第 $i-1$ 行有 $n-i+2$ 个，因此

三对角矩阵

对角矩阵也称带状矩阵。三对角矩阵中所有非零元素都集中在以主对角线为中心的 3 条对角线区域，即 $|i - j| > 1$ 时 $a_{i,j} = 0$。

按行优先存储时，第 1 行有 2 个元素，其余每行 3 个元素（最后一行 2 个），共 $3n-2$ 个。$a_{i,j}$ 前面有 $3(i-1)-1$ 个元素，再加上本行中它前面的 $j-i+1$ 个元素：

反过来，已知 $k$ 求 $i, j$：$i = \left\lfloor \dfrac{k+1}{3} + 1 \right\rfloor$，$j = k - 2i + 3$。

稀疏矩阵

矩阵中非零元素的个数 $t$ 相对矩阵元素的个数 $s$ 来说非常少，即 $s \gg t$ 的矩阵称为稀疏矩阵。例如一个 $100 \times 100$ 的矩阵中只有不到 100 个非零元素。

稀疏矩阵的非零元素分布没有规律，因此除了存放元素值，还要存储它所在的行和列，构成三元组（行标 $i$，列标 $j$，值 $a_{i,j}$）。

• 三元组表（顺序存储）压缩后失去了随机存取特性。
• 稀疏矩阵也可以采用十字链表存储：每个非零元素用一个结点表示，结点包含行号、列号、值，以及指向同行下一个非零元素的右指针和指向同列下一个非零元素的下指针。

即时练习