数组和特殊矩阵
掌握多维数组的存储方式，了解特殊矩阵的压缩存储，可能在选择题中出现概念考察以及某个矩阵元素下标的计算。
多维数组的存储
如果数组的第一个元素位于内存地址 $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}$，
所以为了节省存储空间，可以使用一位数组$B$进行存储
如何计算对称矩阵中元素的下标
$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}$$
三角矩阵
- 下三角矩阵也是一个方阵，其主对角线及其以下（右下部分）的所有元素都不为零，而主对角线以上的所有元素都为零。
- 上三角矩阵是是一个方阵，其主对角线及其以上（左上部分）的所有元素都不为零，而主对角线以下的所有元素都为常数。
如何计算三角矩阵中元素的下标
以上三角矩阵$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（上三角区和对角线元素） \\
\frac{n(n+1)}{2},\text{ } i \gt j（下三角区元素）
\end{cases}$$
三对角矩阵
$$\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}$$
三对角矩阵可以使用压缩存储，将3条对角线上的元素按照行优先的方式存放在一位数组B中。
稀疏矩阵
稀疏矩阵中非零元素的个数相比矩阵元素的总个数非常少，通常，稀疏矩阵中的非零元素的分布是没有规律的。因此，非零元素可以用一个三元组来存储（行，列，值），使用三元组组成的线性表来存储稀疏矩阵中南欧给所有的元素。
矩阵
$$M = \begin{vmatrix}
4 & 0 & 0 & 0\\
0 & 0 & 6 & 0\\
0 & 9 & 0 & 0\\
0 & 23 & 0 & 0
\end{vmatrix}$$