2.5 殊矩阵的压缩存储

2.5.2 稀疏矩阵

　　一般来讲，零元素多到了一定程度并且没有规律分布的矩阵叫做稀疏矩阵。对稀疏矩阵的压缩存储必须充分考虑以下三个问题：
　　① 尽可能减少或者不存储零元素以节省空间，降低空间复杂度。
　　② 尽可能快地实现数据元素的存储位置与原有位置之间的转换。
　　③ 尽可能不与零元素进行运算，以降低时间复杂度。
　　稀疏矩阵的压缩存储有三种最常见的方法，分别是三元组顺序表、行逻辑链接顺序表和十字链表。
　　1．三元组顺序表
　　三元组顺序表是采用顺序结构存储稀疏矩阵的一种压缩存储方法，它以“行、列、取值”三元来记载一个非零元素。下面是一个定义数据元素类型为Elemtype的三元组的例子：
　　
　　为了方便计算，数组中下标为0的存储位置空闲不用。例如，矩阵及其转置矩阵的三元组顺序表如表2-1所示。

表2-1 三元组顺序表实例

　　令m×n矩阵中非零元素数量为k，存在多种通过三元组顺序表对矩阵进行转置的方法。主要有排序法和辅助向量法。
　　（1）排序法
　　第一步，将原三元组顺序表的i与j取值交换，时间复杂度为O(k)。
　　第二步，在新顺序表中按i的取值从小到大进行排序，为了避免再次对j排序，需要确保i取值相同的行之间的顺序不变，于是只能选择稳定的排序算法，时间复杂度一般在O(klogk)～O(k²)之间。
　　在执行第二步前，新的顺序表按照j的取值从小到大排序。而第二步中并不改变i取值相同的行之间的顺序，于是保证了这些行之间仍然按照j的取值大小排序。整个过程类似一个先j后i，并且已经完成了j排序的基数排序，只要再完成按i排序就可以了。
　　矩阵A按照排序法的转置过程如表2-2所示。

表2-2 三元组顺序表转置实例

（2）辅助向量法
　　增加一行向量记载原矩阵中每列的第一个非零元素在所有以列排序的非零元素中的位置，显然，此位置也将是转置矩阵中每行的第一个非零元素存储在顺序表中的下标，定义此向量为cpot。为了能够顺利增加这个向量，需要辅助一个记载每列非零元素数量的向量，定义此向量为num。从矩阵中获取上述两个辅助向量的步骤如下：
　　第一步，遍历原三元组的j，将对应的向量元素num[j]取值加1，即可获取每列非零元素数量，时间复杂度为O(k)。例如，遍历到三元组A的第p项时：
　　
　　第二步，按照以下公式计算向量cpot，即可获取每列第一个非零元素的位置（n为原矩阵的列数），时间复杂度为O(k)。
　　
　　通过辅助向量进行矩阵转置的步骤如下：
　　第一步，遍历原三元组顺序表，循环执行第二步和第三步。
　　第二步，设当前元素列取值为j，则将此元素存入新三元组cpot[j]位置中。
　　第三步，将新矩阵第j行元素存储位置加1，即cpot[j]++。
　　算法的时间复杂度为O(k)，图2-9是矩阵A转置的示例。