3.8 特殊矩阵的压缩存储★3◎2

3.8 特殊矩阵的压缩存储★3◎2

　　矩阵是一种常见的数学对象，一般来讲，可以使用二维数组存储一个矩阵，但是数值分析中常常出现一些特殊的矩阵，比如在某些矩阵中，相同值的元素或零值元素按照一定规律排列，则称此类矩阵为“特殊矩阵”，如果矩阵中存在大量的零值元素，而且零值元素的位置没有规律，则称此类矩阵为“稀疏矩阵”。如果对以上两类矩阵的存储采取相同值元素只存储一次，对零值元素不分配存储空间的策略，对此类矩阵的存储称为“压缩存储”。
　　1．对称矩阵和三角矩阵的压缩存储
　　N阶对称矩阵满足以下条件：

aij=aji 1≤i，j≤n

　　此类矩阵的上三角元素与下三角元素取值相同，因此我们可以使用一个数组存储其下三角元素即可完成对整个矩阵的存储，如图3-10所示。

　　其中，矩阵元素aij的下标i、j与其存储在数组中的位置下标k（从0开始计数）存在如下对应关系：

　　
　　以i≥j为例，推导方法为：
　　在矩阵元素aij之前已经存储了i-1行矩阵元素和第i行的j-1个元素，又已知矩阵的第1行需要存储1个元素，第2行需要存储2个元素，依次类推，第i-1行需要存储i-1个元素，故矩阵元素aij之前一共存储的元素数有：
　　又由于数组下标从0开始，故矩阵元素aij存储在位置上。
　　例如矩阵元素a31存储在一维数组中的位置为：

　　即一维数组中第4个元素，如图3-10所示。
　　这种压缩存储方法也适用于三角矩阵。
　　2．稀疏矩阵的压缩存储
　　稀疏矩阵的压缩存储方法一般有三元组顺序表、行逻辑链接顺序表和十字链表三种最常见的方法。本小节将以如下稀疏矩阵为例讲述这三种存储方法：

　　（1）三元组顺序表
　　只将矩阵的非0元素存储到一维数组中，这个数组的元素由三部分组成，分别代表了矩阵非0元素的行信息、列信息和值信息，如表3-7所示。

表3-7 三元组顺序表实例

　　（2）行逻辑链接顺序表
　　本方法在三元组顺序表的基础上，增加一个数组存储矩阵中每行第一个非0元素出现的位置，在上例中需要增加的数组以及数据中元素的取值如表3-8所示。

表3-8 行逻辑链接顺序表

　　（3）十字链表
　　十字链表表示稀疏矩阵比较复杂，如图3-11是上面矩阵的十字链表，请读者体会：