搜索
写经验 领红包
 > 自然

数据结构中对称矩阵的压缩存储怎么求(对称矩阵压缩存储的存储地址公式)

导语:C语言:数据结构-对称矩阵的压缩存储

对称矩阵

(1)特点

矩阵中行数等于列数,即它是一个方阵,且第i行第j列的元素与第j行第i列的元素对应相等,即ai,j=aj,i。

例5.5 图5-5是一个4阶对称的对称矩阵,虚线所示部分称为对称矩阵的下三角部分(包括对角线部分),显然对下三角部分数组元素ai,j,一定有i≥j。

对称矩阵

(2)对称矩阵的压缩存储原理

根据对称矩阵的特点(ai,j=aj,i),行数=列数,所以只要存储下三角部分的矩阵元素,其他矩阵元素可根据对称矩阵的特性得到。

(3)存储方法

定义一个一维数组,其数据类型与对称矩阵的相同,长度大于等于对称矩阵的下三角部分的元素个数。确定在一维数组中存储的起始点,以行序为主,依次存储下三角部分的矩阵元素到一维数组中。

例5.6 对称矩阵的压缩存储

用对称矩阵的压缩存储方法,把上图5-5所示的矩阵A存储到一维数组b中。一维数组存储的起始下标为零,如图5-6所示。

对称矩阵的压缩存储

例5.7 在例5.6中,求矩阵元素a4,2对应一维数组b中的数组元素。设矩阵在存放时,从一维数组的第一个元素b[0]开始。

分析:矩阵元素a4,2在第4行第2列,而下三角部分的前3行的元素个数为:1+2+3=6,第4行从第1列到第2列有两个元素。共有6+2=8个元素。

由此,a4,2是下三角部分的第8号元素。存放时从元素b[0]开始,所以矩阵元素a4,2 对应一维数组中的数组元素为b[7]。

(4)对称矩阵压缩存储的关系式

设有对称矩阵A,一维数组b,把矩阵A的下三角部分压缩存储到一维数组b中。矩阵元素ai j,(i≥j),对应于b[k],则有:

k= a[i(i-1)/2+j-1] 从b[0]开始存储

k= a[i(i-1)/2+j] 从b[1]开始存储

注:当i≤j时,因为ai,j=aj,i,只要按照aj,i计算即可。

本文内容由小冰整理编辑!