数据结构-二维数组-三角矩阵压缩存储
一、什么是三角矩阵
前情提要
三角矩阵也是属于一类特殊的二维数组矩阵,同样也用压缩的存储方式,能够更好的节约存储空间,二维数组的三角矩阵分为上三角矩阵和下三角矩阵,其实现的原理差不多类似,下面就细细道来。
三角矩阵的特点
此处讨论的三角矩阵的行数和列数是一样的,不妨设都设为 n 。如下所示:
如上所示,为上三角矩阵,矩阵的对角线以下的所有元素均为同一常数 δ ,或者无效的数据。从上往下逐行的元素总数是比上一行少一个,构成等差数列条件,以下会用的等差数列数学知识。若 δ 为常数,则需要在所有元素的最后一个另外加一个元素位置单独存放该数据,毕竟只要是有效数据就需要存储的嘛。对于下三角矩阵有类似的特点,这里放到公式推导里面去介绍。
二、三角矩阵压缩存储
上三角矩阵的存储
如下所示:
对于元素处于上三角区域,即元素 aij ,其中 i≤j ,可得如下规律:
第 1 行有
∑k=1i−1(n−k+1)=(i−1)(2n−i+2)2 个元素,元素 aij ,在第i行中是第 (j−i+1) 个元素,规定:每个元素所占的长度为 e ,所以:
对于元素处于下三角区域,即元素 aij ,其中 i>j ,因为下三角区的元素值都一样(如果元素的值有效),则把它放到存储区的最后一个单元,即: (n+1)n2+1 的位置,可得地址公式: address(aij)=address(a11)+((n+1)n2)e
下三角矩阵的存储
如下所示:
对于元素处于下三角区域,即元素 aij ,其中 i≥j ,可得如下规律:
第 1 行有
∑k=1i−1k=(i−1)(1+i−1)2=(i−1)i2 个元素,元素 aij 在第 i 行为第
矩阵的压缩存储暂时写到这,写得不好,多多指教哈。