特殊矩阵的压缩存储

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

对于特殊矩阵的压缩存储一般会考察类似某元素位于数组中的哪个地址之类的。对于这类题目一般需要通过找规律推导数学公式来计算出结果且要特别注意数组的下标以及矩阵的下标是从0还是1开始才可计算出正确结果。本节涉及很多公式但不难不用背但需要去理解透彻以便在考场上能直接现场推导出公式来。

一、数组的存储结构

一、数组的存储结构

1、一维数组

各数组元素大小相同且在物理上连续存放。

LOC代表起始地址如果数组下标从1开始那么式子中的 i 要变成 i - 1。

2、二维数组

其内存表示分为两种不同的存储策略一种是行优先存储一种是列优先存储

行优先存储即一行一行的存

计算行优先存储的二维数组的某一个元素的地址

其中(i*N+j) 用于计算目标元素前面所有元素的个数。

列优先存储即一列一列的存

计算列优先存储的二维数组的某一个元素的地址

其中(j*M+i) 用于计算目标元素前面所有元素的个数。

二、特殊矩阵

1、对称矩阵

注意n阶的意思是行数和列数相同都是n列。

关于对称矩阵的压缩存储就是只存储主对角线+下三角区按行优先或列优先原则存储元素至一维数组中。

1、按行优先原则将各个元素存入一维数组中

存储在数组中的情况

一维数组的大小应该定义为 (1+n)*n/2, 此公式通过求和公式将每行元素相加即可得到。上图问号处下标就是 (1+n)*n/2-1(数组第一个下标为0的情况下)。

Q按行优先原则 $a_{ij}$ 是第几个元素

A因为是行优先所以 $a_{ij}$ 是第 $1+2+...+(i-1)+j$ 个元素即第 $\frac{i(i-1)}{2}+j-1$ 个元素(数组下标从0开始的情况下)

2、按列优先原则将各个元素存入一维数组中

存储在数组中的情况

Q按列优先原则 $a_{ij}$ 是第几个元素

A因为是列优先所以先算出前 j-1 行有多少个元素由每列元素个数与列数 j 有关可知每列的元素个数为 n-(j-1) 个前 j-1 行即 n-(1-1) + n-(2-1) + n-(3-1) + ··· + n-(j-1-1)个元素化简得前j-1行有 $n+(n-1)+...+(n-j+2)$ 个元素。接下来再加上第 j 行的元素也就是 $a_{ij}$ 所处的那一行中 $a_{ij}$ 前面的元素个数个数为 i - j 个综上 $a_{ij}$ 是第 $n+(n-1)+...+(n-j+2)+(i-j)+1$ 个元素。

另外如果元素存储在上三角区道理都一样按照求下三角区那样推导公式即可。

易错点需要注意审题仔细看下题目中数组或矩阵下标是从0还是从1开始考虑不全面可能导致计算结果出错。

2、三角矩阵

三角矩阵分为下三角矩阵和上三角矩阵

对于这类数据的压缩存储思想是按照行优先或者列优先原则把不是常量的区域的数据放到一维数组中并仅在数组最后一个位置(下图c处)存储常量(上图中白色区域的元素)

Q下三角矩阵按行优先原则 $a_{ij}$ 是第几个元素

第二个式子表示如果取上三角区的元素那么位置一定是位于数组的最后一个位置的。

Q上三角矩阵按行优先原则 $a_{ij}$ 是第几个元素

第一个式子的推导第一行n个元素第二行n-1个元素······ 推出第i行的元素个数是(n-(i-1))个 $a_{ij}$ 的元素位置就是前i-1行的元素个数加上第i行 $a_{ij}$ 前面的元素个数即第 n + (n-1) + ··· + (n-i+2) + (j-i) 个