5、矩阵的压缩存储
5.1、对称矩阵的压缩存储
若n阶矩阵任意一个元素,都有的\(a_{i,j} = a_{j,i}\)的矩阵称为对称矩阵,
普通存储:二位数组存储需要n*n个位置
压缩存储策略:值存储对角线和下三角(或者对角线和上三角)
\[\begin{pmatrix} a_{1,1} & a_{1,2} & ... & a_{1,n-1} & a_{1,n}\\ a_{2,1} & a_{2,2} & ... & a_{2,n-1} & a_{2,n}\\ ... & ... & ... & ... & ...\\ a_{n-1,1} & a_{n-1,2} & ... & a_{n-1,n-1} & a_{n-1,n}\\ a_{n,1} & a_{n,2} & ... & a_{n,n-1} & a_{n,n} \end{pmatrix}\]策略:储对角线 + 下三角 行优先原则
按行优先原则将个元素存储得到一维数组中
需要数组的大小为\(1+2+3+...+n\) ---> $\frac{(n+1)\times n}{2} $
arr存储数组图片
\(a_{i,j}\)是一维数组的第几个元素了?,\(a_{i,j}\)前面有\((1+2+3+i-1)\)个元素,加上第j列的第j个元素就是\(a_{i,j}\)的位置:\(\frac{(i-1)\times i}{2} + j\)个
由于数组下标从零开始,所以\(a_{i,j}\)的位置:\(\frac{(i-1)\times i}{2} + j - 1\)
即:\(a_{i,j} = arr[\frac{(i-1)\times i}{2} + j - 1] (i>=j)\)
策略:储对角线 + 下三角 列优先原则
需要数组的大小和行优先原则一样
arr存储数组图片
\(a_{i,j}\)是一维数组的第几个元素了?,\(a_{i,j}\)前面有\((n+n-1+n-2+n-j + 2)\)个元素,加上第i行的第i个元素就是\(a_{i,j}\)的位置:\(\frac{2nj + 3j -2n -2 -j^2}{2} + i\)个
即:\(a_{i,j} = arr[\frac{2nj + 3j -2n -2 -j^2}{2} + i - 1] (i>=j)\)
5.2、三角矩阵的压缩存储
上三角或者下三角的全是相同常数的矩阵,叫三角矩阵
\(\begin{pmatrix} a_{1,1} & c & ... & c & c\\ a_{2,1} & a_{2,2} & ... & c & c\\ ... & ... & ... & ... & ...\\ a_{n-1,1} & a_{n-1,2} & ... & a_{n-1,n-1} & c\\ a_{n,1} & a_{n,2} & ... & a_{n,n-1} & a_{n,n} \end{pmatrix}\)或者\(\begin{pmatrix} a_{1,1} & a_{1,2} & ... & a_{1,n-1} & a_{1,n}\\ c & a_{2,2} & ... & a_{2,n-1} & a_{2,n}\\ ... & ... & ... & ... & ...\\ c & c & ... & a_{n-1,n-1} & a_{n-1,n}\\ c & c & ... & c & a_{n,n} \end{pmatrix}\)
三角矩阵和对称矩阵差不多,只需要存储(对角线+下三角)或者(对角线+上三角);不过需要多加一个三角的常数
策略:储对角线 + 下三角 行优先原则
需要数组的大小为\(1+2+3+...+n+1\) ---> \(\frac{(n+1)\times n}{2} + 1\)
\[a_{i,j} = \left\{\begin{matrix} arr[\frac{(i-1)\times i}{2} + j - 1] (i>=j) \\ arr[\frac{(n+1)\times n}{2}] (i<j) \end{matrix}\right. \]5.3、三对角矩阵的压缩存储
\[\begin{pmatrix} a_{1,1} & a_{1,2} & 0 & ... & 0 & 0\\ a_{2,1} & a_{2,2} & a_{2,3} & ... & 0 & 0\\ ... & ... & ... & ... & ... & ...\\ 0 & 0 & 0 & ... & a_{n-1,n-1} & a_{n-1,n}\\ 0 & 0 & 0 & ... & a_{n,n-1} & a_{n,n} \end{pmatrix}\]三对角矩阵又称带状矩阵,当|i-j|>1时候,\(a_{i,j} = 0\) (i,j<=n)
按照行优先(列优先)原则只可以存存储带状部分
出了第一行和最后一行只有两个元素,其他行都有三个元素
需要数组的大小为:\(3n-2\)
\(a_{i,j}\)前面有i-1行,所以前面就有\(3(i-1)-1\)个元素;又是第i行的\(j-i+2\)个元素;所以\(a_{i,j}\)是第\(2i+j-2\)个元素
即:\(a_{i,j} = arr[2i + j - 3]\)
例:如果知道数组的第k的位置,怎么得到它的i,j了?
显然:\(3(i-1)-1 < k <= 3i-1\)
\(i < \frac{(k+1)}{3}+1\)
因为i为整数 \(i = \left \lfloor \frac{(k+1)}{3}+1 \right \rfloor\)
由于 \(k = 2i+j-3\)
所以\(j = k-2i+3\)
5.4、稀疏矩阵的压缩存储
稀疏矩阵:非零元素的个数远远小于全部矩阵元素的个数
顺序压缩策略:
顺城存储:<行,列,值>
\[\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 2 & 0 & 0 & 4\\ 0 & 0 & 0 & 0 & 5 & 0\\ 0 & 0 & 0 & 7 & 0 & 2\\ 0 & 0 & 3 & 0 & 0 & 0 \end{pmatrix}\]i(行) | j(列) | v(值) |
---|---|---|
1 | 2 | 1 |
2 | 3 | 2 |
2 | 6 | 4 |
3 | 5 | 5 |
4 | 4 | 7 |
4 | 6 | 2 |
5 | 3 | 3 |
可以定义一个结构体:
struct Sparse{
int i;//行位置
int j;//列位置
ElemType v;//值的位置
};
十字链表:
可以定义两个结构体:
typedef struct OLNode{
int i;//行位置
int j;//列位置
ElemType v;//值的位置
struct OLNode *right,*down; //非零元素所在行和列的后继
}OLNode,*OLink;
typedef struct CrossList{
int mu,nu,tu;//矩阵的行数,列数,非零的个数
OLink *rhead,*chead;//稀疏矩阵的行和列的头指针
}CrossList;
\[\begin{pmatrix}
0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 2 & 0 & 0 & 4\\
0 & 0 & 0 & 0 & 5 & 0\\
0 & 0 & 0 & 7 & 0 & 2\\
0 & 0 & 3 & 0 & 0 & 0
\end{pmatrix}\]