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;
