303 数组和特殊矩阵

数组和特殊矩阵

数组的存储结构

按行优先

数组元素在内存中按行的顺序依次存储。

二维数组示例：

设 $A[3][2]=\left[\begin{array}{cc}{a}_{00}& a_{01}\\ a_{10}& a_{11}\\ a_{20}& a_{21}\end{array}\right]$，存储顺序：$a_{00}\to a_{01}\to a_{10}\to a_{11}\to a_{20}\to a_{21}$

地址计算推导： 元素 $A[i][j]$ 前有 $i$ 行（每行 $n$ 个元素）和当前行的 $j$ 个元素，故偏移量 $=i\times n+j$。 公式：

$$LOC(A[i][j])=LOC(A[0][0])+(i\times n+j)\times L$$

按列优先

数组元素在内存中按列的顺序依次存储。

二维数组示例：

$A[3][2]$ 的存储顺序：$a_{00}\to a_{10}\to a_{20}\to a_{01}\to a_{11}\to a_{21}$

地址计算推导： 元素 $A[i][j]$ 前有 $j$ 列（每列 $m$ 个元素）和当前列的 $i$ 个元素，故偏移量 $=j\times m+i$。 公式：

$$LOC(A[i][j])=LOC(A[0][0])+(j\times m+i)\times L$$

特殊矩阵的压缩存储

对称矩阵

满足 $a_{ij}=a_{ji}$，仅需存储下三角（含主对角线）。

示例：

$A=\left[\begin{array}{ccc}1& 2& 3\\ 2& 4& 5\\ 3& 5& 6\end{array}\right]$ 压缩存储序列：$[1,2,4,3,5,6]$

地址映射推导：

• $i\ge j$（下三角）：元素 $a_{ij}$ 前有 $i$ 行（第 $0$ 到 $i-1$ 行），元素总数 $=\frac{i(i+1)}{2}$，加上当前行 $j$ 个元素。 公式：

$$k=\frac{i(i+1)}{2}+j$$

三角矩阵

下三角矩阵

示例： $A=\left[\begin{array}{ccc}1& c& c\\ 2& 3& c\\ 4& 5& 6\end{array}\right]$ 压缩存储序列：$[1,2,3,4,5,6,c]$

地址映射：

• $i\ge j$ 时：$k=\frac{i(i+1)}{2}+j$
• $i<j$ 时：$k=\frac{n(n+1)}{2}$（指向常数 $c$）

上三角矩阵

地址映射推导： 元素 $a_{ij}$ 前有 $i-1$ 行（第 $0$ 到 $i-1$ 行），每行元素数递减： 第 $0$ 行：$n$ 个，第 $1$ 行：$n-1$ 个，…，第 $i-1$ 行：$n-i$ 个。 前 $i$ 行总元素数：$\frac{i(2n-i+1)}{2}$，加上当前行偏移 $j-i$。 公式：

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

三对角矩阵（带状矩阵）

非零元素位于主对角线及其相邻两条对角线上，满足 $|i-j|\le 1$。

示例：

$A=\left[\begin{array}{cccc}1& 2& 0& 0\\ 3& 4& 5& 0\\ 0& 6& 7& 8\\ 0& 0& 9& 10\end{array}\right]$ 压缩存储序列：$[1,2,3,4,5,6,7,8,9,10]$

地址映射推导：

• 每行最多 $3$ 个非零元素（首末行 $2$ 个）。
• 元素 $a_{ij}$ 在序列中的位置：前 $i$ 行有 $3i-1$ 个元素（$i\ge 1$），加上当前行偏移 $j-i+1$。 公式：

$$k=2i+j$$

稀疏矩阵

非零元素远少于零元素，通常采用压缩存储。

三元组表示法

用三元组 $(i,j,v)$ 表示非零元素的位置和值。

示例：

$A=\left[\begin{array}{ccc}0& 0& 3\\ 5& 0& 0\\ 0& 0& 0\end{array}\right]$ 的三元组：$(0,2,3)$ 和 $(1,0,5)$。

存储结构：

typedef struct {
    int i, j;     // 行标和列标
    ElemType v;   // 元素值
} Triple;

记忆技巧：

• 行优先排序：先按行号排序，同行内按列号排序（类似字典序）。
• 压缩原理：用 $O(3k)$ 空间存储 $k$ 个非零元素（传统矩阵需 $O(n^2)$）。

十字链表表示法

适用于需要频繁插入和删除操作的稀疏矩阵，每个非零元素用一个节点表示，同时链接在对应的行链表和列链表中。

除了三元组（行标、列标、值）还要保存行数、列数和非零元素的个数。