目录
11.特殊矩阵的压缩存储
(1).一维数组的储存结构
(2).二维数组的存储结构
(3).普通矩阵的存储
(4).特殊矩阵的压缩存储
i.对称矩阵
ii.三角矩阵
iii.三对角矩阵
iiii.稀疏矩阵
11.特殊矩阵的压缩存储
(1).一维数组的储存结构
int a[10];
一维数组的地址是连续的,只要知道了起始地址(LOC,默认是a[0]的地址),就可以知道所有元素的地址。
a[i] 地址的计算 :LOC + i * sizeof(int) .
注意:有时候给出的LOC可能不是a[0] 的,此时,就要在上式子的i 中减去,如给出的是a[1]的,则计算公式变为 LOC + (i - 1) * sizeof(int).
(2).二维数组的存储结构
int b[2][4]
二维数组在内存中有两种存储方法,行优先和列优先。
当然,从逻辑视角上看,将数据配列成矩阵的样式,更方便进行操作。
有int b[M][N],b[0][0] 的地址为LOC,则b[i][j]
行优先:LOC + (i*N + j)*sizeof(int)
列优先:LOC + (j*M + i)*sizeof(int)
(3).普通矩阵的存储
一般是用二维数组,
需要注意的是,矩阵的下标是从(1, 1) 开始的,数组是从(0, 0) 开始的。
(4).特殊矩阵的压缩存储
i.对称矩阵
· 是方阵(n阶),
· 恒有 aij == aji,
因为对称,所以可以只存储下三角区和对称轴(或上三角区和对称轴)(这样就是所谓的压缩存储)
按行优先将各元素存入一维数组(也可以列优先),
如此便要思考,
数组的大小,显然,第一行一个元素,第二行两个元素...第N行N个元素,总数就是n*(n+1)/2.
数据的调用,因为矩阵的下标与数组的下标规则不同,可以写一个简单的映射函数进行转换
aij => b[k]
总结上图,可知
k = (i+1)*i/2 + j - 1 ,
即当前元素行数往上为等差数列求和,再加上列数,就是在数组中的第几个元素,再减一,就成了数组下标。(如果,题干给出的数组起始下标为1,k就不需要减去那个1)
ii.三角矩阵
压缩存储策略:储存aij的三角区,将常数储存在数组最后一位。(以下三角为例)
数组大小,n*(n+1)/2 + 1.
aij的ij 与数组下标之间的相互转换与上文相同。
获取常数项,数组下标就是 n*(n+1)/2。
值得一提的,在上三角中,求aij是数组中的第几个元素,观察图可知,每行的元素数由N个依次递减。所以,aij 前面有 [n + ... + (n - i + 2)] + (j - i)个元素,中括号里的是此行往上的,那个j-i是当前行内aij 之前的元素。
iii.三对角矩阵
以行优先为例,
数组大小,3n - 2。
数组下标(对于aij),前(i - 1)行,有3(i - 1) - 1个元素(每行有三个元素,但第一行只有两个);第i 行中,aij是第j - i + 2个元素,所以aij 就是第2i + j - 2(前后相加)。
k = 2i + j - 3
由数组下标逆推矩阵下标ij
已知b[k]
是第k + 1个元素,在前i-1行,与前i行之间,3(i - 1) - 1 < k + 1 <= 3i - 1
i >= (k + 2)/3,左式算出结果后向上取整就是i 值
(向上取整:如1.2,向上取整就是2,向下就是1)
iiii.稀疏矩阵
压缩策略:
① 顺序存储------设置一个类,其中包含三个数组,分别存储i、j、非零数据。
② 十字链表法----此为链式存储,
结点中,包含行、列、值以及两个指针。
两个指针分别指向同一列的下一个结点和同一行的下一个结点。