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

对称矩阵

（1）特点

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

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

对称矩阵

（2）对称矩阵的压缩存储原理

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

（3）存储方法

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

例5.6 对称矩阵的压缩存储

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

对称矩阵的压缩存储

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

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

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

（4）对称矩阵压缩存储的关系式

设有对称矩阵A，一维数组b，把矩阵A的下三角部分压缩存储到一维数组b中。矩阵元素a_{i 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时，因为a_i,_j=a_j,_i，只要按照a_j,_i计算即可。