全屏显示专题章节

对于一个m×n的矩阵，设s为矩阵元素的总和，有s＝m×n，设t为矩阵中非零元素的总和，满足t≪s的矩阵称作稀疏矩阵。符号≪读作远小于。简单地说，稀疏矩阵就是非零矩阵元素个数远远小于矩阵元素个数的矩阵。相对于稀疏矩阵来说，一个不稀疏的矩阵也称作稠密矩阵。

由于稀疏矩阵的零元素非常多，且分布无一定规律，所以稀疏矩阵的压缩存储方法是只存储矩阵中的非零元素。稀疏矩阵中每个非零元素和它对应的行下标和列下标构成一个三元组，稀疏矩阵中所有这样的三元组构成一个三元组表。稀疏矩阵压缩存储的方法是只存储稀疏矩阵的三元组表。图5－8（a）是一个稀疏矩阵，图5－8（b）是对应的三元组表。

稀疏矩阵的压缩存储结构主要有三元组顺序表和三元组链表两大类型。其中，三元组链表中又有一般链表、行指针数组链表和行列指针的十字链表存储结构等。稀疏矩阵的压缩存储结构可看作是顺序表和链表的直接应用和组合应用。

1.稀疏矩阵的三元组顺序表

用顺序表存储的三元组表称作三元组顺序表。三元组顺序表是把三元组定义成顺序表的数据元素。因此，我们可把三元组定义成顺序表的数据元素。

设稀疏矩阵三元组顺序表按先行序后列序的顺序存放，则三元组顺序表的存储表示如下。

算法5.1 稀疏矩阵的三元组顺序表存储表示

这样，图5－8（b）所示的稀疏矩阵的三元组表的存储结构就对应为图5－9所示的稀疏矩阵的三元组顺序表。

下面我们讨论在这种压缩存储结构下稀疏矩阵转置运算的实现方法。

矩阵的转置运算是把矩阵中每个元素的行值转为列值，同时再把列值转为行值。因此，一个稀疏矩阵的转置矩阵仍是稀疏矩阵。图5－10是图5－9所示的稀疏矩阵三元组顺序表的转置。

下面我们给出其中的一种求稀疏矩阵三元组顺序表的转置矩阵的普通算法。

算法5.2 稀疏矩阵的三元组顺序表转置算法

此稀疏矩阵的转置算法的时间复杂度为O（nu×tu），其中nu为稀疏矩阵的列数，tu为稀疏矩阵的非零元个数。

当非零元的个数tu和mu×nu（mu为矩阵行数，nu为矩阵列数）同数量级时，算法5.2的时间复杂度就为O（mu×nu2）（例如，倘若在100×500的矩阵中有tu＝10 000个非零元），虽然节省了存储空间，但时间复杂度提高了，因此算法5.2仅适于tu≪mu×nu的情况。

那有什么更快的转置算法吗？如果我们能预先确定矩阵M中每一列（即T中每一行）的第一个非零元在b.data中应有的位置，那么在对a.data中的三元组依次作转置时，便可直接放到b.data中恰当的位置上去。为了确定这些位置，在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中应有的位置。

因此，我们需要附设num和cpot两个向量。Num［col］表示矩阵M的第col列中非零元的个数，cpot［col］指示M中第col列的第一个非零元在b.data中的恰当位置。因此有

下面给出稀疏矩阵的三元组顺序表的快速转置算法。

算法5.3 稀疏矩阵的三元组顺序表的快速转置算法

这个算法比前一个算法多用了两个辅助向量。从时间上看，算法中有四个并列的单循环，循环次数分别为nu和tu，因而总的时间复杂度为O（nu＋tu）。在M的非零元个数tu和mu×nu等数量级时，其时间复杂度为O（mu×nu），和经典算法的时间复杂度相同。

当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。例如，在做“将矩阵B加到矩阵A上”这一操作时，由于非零元的插入或删除将会引起A.data中元素的移动，因此对于这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。

在链表中，每个非零元可用一个含五个域的结点表示，其中，i、j和e三个域分别表示该非零元所在行和列以及非零元的值，向右域right用来链接同一行中下一个非零元，向下域down用来链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，同时又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，所以称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示。