5.2.1　特殊矩阵

特殊矩阵是有许多值相同的元素或有许多零元素，且这些值相同的元素或零元素的分布有一定规律的矩阵。当矩阵的维数比较大时，矩阵占据的内存单元相当多。这时，利用特殊矩阵数据元素的分布规律来压缩矩阵的存储空间，对许多应用问题来说有重要的意义。

特殊矩阵压缩存储的方法是只存储特殊矩阵中数值不相同的数据元素。读取压缩存储矩阵元素的方法是利用特殊矩阵压缩存储的数学映射公式找到相应的矩阵元素。下面介绍几种特殊矩阵。

1.对称矩阵

（1）定义

在一个n阶方阵中A中，若元素满足下列性质：aij＝aji（1≤i，j≤n），则称矩阵A是对称矩阵。图5－1所示是对称矩阵。

（2）存储结构

由于对称矩阵中的数据元素以主对角线为中线对称，因此在存储时，可以把对称的两个相同数值的数据元素存储在一个存储单元中，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。

存储的方法是按“行优先顺序”存储主对角线（包括对角线）以下的元素，存储顺序如图5－2所示。

图5－1 对称矩阵

图5－2 行优先存储对称矩阵

由等差数列求和公式可以推导出5阶对称矩阵存储使用的空间是15，由此推导出n阶对称矩阵数据元素可压缩存储在n（n＋1）／2个存储单元中。假设我们以一维数组Va作为n阶对称矩阵A的压缩存储单元，则一维数组Va要求的元素个数为n（n＋1）／2。存储如图5－3所示。

图5－3 对称矩阵存储

设aij为n阶对称矩阵A中第i行j列的数据元素，k为一维数组Va的下标序号，其数学映射关系为：

通过如上压缩映射后，n阶对称矩阵A中的数据元素aij压缩存储到了一维数组Va中，因此，一维数组Va实现了对n阶对称矩阵A的压缩存储，其压缩存储空间效率提高近一倍。

2.三角矩阵

（1）定义

三角矩阵分为上三角矩阵和下三角矩阵两种。

所谓n阶下三角矩阵就是行列数均为n的矩阵的上三角（不包括对角线）中的数据元素均为常数c（典型情况c＝0）。如图5－4（b）所示上三角矩阵就是行列数均为n的矩阵，下三角（不包括对角线）中的数据元素均为常数c（典型情况c＝0）。图5－4（a）所示为上三角矩阵。

图5－4 三角矩阵

（2）存储结构

三角矩阵在存储时可以只存储下三角矩阵或上三角中的元素，然后多加一个空间存储常数c（c常为0）。三角矩阵的存储和对称矩阵相似，可参考图5－2。存储空间是n（n＋1）／2＋1，比对称矩阵多一个空间，用来存储常数c。

假设我们以一维数组Va作为三角矩阵A的压缩存储单元，则一维数组Va要求的元素个数为n（n＋1）／2＋1。下三角矩阵存储如图5－5所示。同理上三角存储与下三角类似，只是在找相应的数据元素时位置不同。

图5－5 下三角矩阵存储

设aij为n阶下三角矩阵中第i行j列的数据元素，k为一维数组Va的下标序号，我们有如下数学映射公式：

若aij为n阶上三角矩阵中第i行j列的数据元素，k为一维数组Va的下标序号，数学映射公式如下：

3.对角矩阵

（1）定义

对角矩阵中，所有的非零元素都集中在以对角线为中心的带状区域中，即除了主对角线上和主对角线邻近的上、下方，所有其他的元素均为零。最常见的是三对角矩阵，如图5－6所示。

图5－6 三对角矩阵

（2）存储结构

从图5－6可知，在三对角矩阵中，除了第一行和最后一行只有2个非零元素外，其余各行都有3个非零元素，由此得出，存储三对角矩阵所需的空间是2＋2＋3×（n－2）＝3n－2。假设我们以一维数组Va作为三对角矩阵A的压缩存储单元，则一维数组Va要求的元素个数为3n－2。三对角矩阵存储如图5－7所示。

图5－7 三对角矩阵存储

4.特殊矩阵经典例题

以上是特殊矩阵的压缩存储和数据元素地址的确定，在这个过程中需要注意以下几点：

第一，确定矩阵类型属于哪一种；

第二，确定首元素下标、首元素地址和每个元素占的字节数（本节中首元素都是a11）；

第三，确定对应的公式进行求解。

下面举例说明。

例5.1 设有一个n×n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A［0］［0］存放于B［0］中，那么第i行的对角元素A［i］［i］存放于B中何处？

解：第一，矩阵是对称矩阵，采用上三角存储；

第二，第一个元素为A［0］［0］；

第三，由于对称矩阵采用上三角形式存储，所以使用上三角的对应公式。但当i＞j时，此公式使用时i和j调换，与此公式不完全相同。

此公式对应的是第一个元素A［1］［1］，所以套用的时候，i和j在原公式上分别加1，代入后k＝（i＋1－1）（2n－（i＋1）＋2）／2＋j－i，化简后k＝i（2n－i＋1）／2。

例5.2 设数组a［1..10，5..15］的元素以行为主序存放，每个元素占用4个存储单元，则数组元素a［i，j］的地址计算公式是什么？

解：第一，这是一个普通矩阵，以行为主存放数据；

第二，数组第一个元素是a［1］［5］，每个元素占用4个存储单元；

第三，使用公式LOC（aij）＝LOC（a00）＋（i×n＋j）×h （0≤i＜m，0≤j＜n）；

但本题首地址有所变化，公式中的值也灵活变化，代入后是a［i，j］＝a［1，5］＋（（i－1）×（15－5＋1）＋（j－5））×4，化简后a－64＋44i＋4j。

从本题我们可以总结出，元素个数、i和j的值都是有变化的，只要我们掌握基本原则，任何变化都可以化简。