4.数组和特殊矩阵

数组的存储结构

以一维数组 $A[0\dots n-1]$ 为例,其存储结构关系式为

LOC(a_{i})=LOC(a_{0})+i\times L(0\le i\text{<} n)

其中 $L$ 是每个数组元素所占的存储单元。

对于多维数组,有两种映射方法:按行优先和按列优先。

按行优先

设二维数组的行下标与列下标的范围分别为 $[0,h_{1}]$ 与 $[0,h_{2}]$ ,则存储结构关系式为

LOC(a_{i,j})=LOC({a_{0,0}}+i\times(h_{2}+1)+j)\times L

按列优先

LOC(a_{i,j})=LOC({a_{0,0}}+j\times(h_{1}+1)+i)\times L

特殊矩阵的压缩存储

注意

解相关题目时，要注意题目条件中给定的数组下标的信息，一般是从0开始的，部分题目中是从1开始的
一般而言数组的下标默认从0开始，但是矩阵的第一个元素一般写为 $a_{1,1}$ ，即从1开始

对称矩阵

将 $n$ 阶对阵矩阵 $A$ 存放在一维数组 $B\left[ \displaystyle\frac{n(n+1)}{2} \right]$ 中
若只存储下三角部分（含对角线）元素，则 $a_{i,j}$ 在数组 $B$ 中的下标 $k=1+2+\dots+(i-1)+j-1=\displaystyle\frac{i(i-1)}{2}+j-1$ (数组下标从0开始),对应关系如下

k=\begin{cases} \displaystyle\frac{i(i-1)}{2}+j-1 &i\ge j(\text{下三角和主对角线})\\ \displaystyle\frac{j(j-1)}{2}+i-1 &i<j(\text{上三角}a_{i,j}=a_{j,i}) \end{cases}

三角矩阵

其存储思想与对称矩阵类似,不同之处在于存储完下三角区和主对角线上的元素之后,紧接着存储对角线上方的常量一次

注意

以下推导均假设数组的下标从0开始

下三角

将 $n$ 阶对阵矩阵 $A$ 存放在一维数组 $B\left[ \displaystyle\frac{n(n+1)}{2} +1\right]$ 中，对应关系如下

k=\begin{cases} \displaystyle\frac{i(i-1)}{2}+j-1 &i\ge j(\text{下三角和主对角线})\\ \displaystyle \frac{n(n+1)}{2} &i<j(\text{上三角}) \end{cases}

上三角

k=\begin{cases} \displaystyle\frac{(i-1)(2n-i+2)}{2}+j-i &i\ge j(\text{下三角和主对角线})\\ \displaystyle \frac{n(n+1)}{2} &i<j(\text{上三角}) \end{cases}

三对角矩阵

对角矩阵也称带状矩阵
对于 $n$ 阶矩阵 $A$ 中的任意一个元素 $a_{i,j}$ ,当 $|i-j|>1$ 时,有 $a_{i,j}=0(1\le i, j\le n)$ ,则称为三对角矩阵
在三对角矩阵中,所有非零元素都集中在以主对角线为中心的3条对角线的区域,其他区域的元素都为零

\begin{bmatrix} a_{1,1}&a_{1,2} & & & & \\ a_{2,1}&a_{2,2} & a_{2,3} & & 0 & \\ &a_{3,2} & a_{3,3} &a_{3,4} & & \\ & & \ddots & \ddots & \ddots & \\ & 0 & a_{n-1,n-2} & a_{n-1,n-1} &a_{n-1,n} & \\ & & & a_{n,n-1} & a_{n,n} & \end{bmatrix}

将3条对角线上的元素按行优先方式存放在一维数组 $B$ 中,且 $a_{1,1}$ 存放于 $B[0]$ 中,则 $a_{i,j}(1\le i,j\le n,|i-j|\le 1)$ 对应下标 $k=2i+j-3$

提示

解题时一般是根据题目所给条件现场推导
记住各种矩阵的存储方式直接推导
上三角第一行n个元素，第二行n-1个...，第一列1个，第二列2个...；下三角第一行1一个，第二行2个...，第一列n个，第二列n-1个...，三对角矩阵除了第一行和最后一行是2个其他的行都是3个
例如 $n$ 阶下三角矩阵 $A$ 按列优先顺序,元素 $a_{i,j}$ 之前有 $j-1$ 列,共有 $n+(n-1)+\dots+(n-j+2)=(j-1)(2n-j+2)/2$ 个元素,元素 $a_{i,j}$ 是第 $j$ 列上第 $i-j+1$ 个元素,数组 $B$ 下标从1开始, $k=(j-1)(2n-j+2)/2+i-j+1$

稀疏矩阵

矩阵中非零元素的个数 $t$ ,相对矩阵元素的个数 $s$ 来说非常少,即 $s\gg t$ 的矩阵称为稀疏矩阵
将非零元素及其相应的行和列构成一个三元组(行标,列标,值)，然后按照某种规律存储这些三元组
稀疏矩阵压缩存储后便失去了随机存取特性
三元组可采用数组存储,也可以采用十字链表法存储

4.数组和特殊矩阵

# 数组的存储结构

# 按行优先

# 按列优先

# 特殊矩阵的压缩存储

# 对称矩阵

# 三角矩阵

# 下三角

# 上三角

# 三对角矩阵

# 稀疏矩阵