谭 阳

(1.湖南师范大学数学与计算机科学学院,中国 长沙 410081；2.湖南广播电视大学信息技术系,中国 长沙 410004)

1 稀疏矩阵的转置

00130070090000900-400000000 Arraysubscript12345LinevalueColumnvalueElementvalue131321724934942-4

(a) 示例稀疏矩阵A(b) 矩阵A的三元组表示

图1稀疏矩阵A及其三元组表示

目前适用于三元组存储方式的转置算法主要有2种.

1.1 Transpose算法

对已压缩好的三元组的列值进行扫描,首先找出第1列的所有元素,若有,则交换该元素的行值和列值,并依次储存到新的三元组中；再找出第2列的所有元素,第3列的所有元素……重复上述过程,直至所有元素都已存入新的三元组中,新的三元组即为转置后的矩阵．该算法需要对三元组进行多次扫描,若稀疏矩阵A=(ai,j)n×m中含有t个非零元素,则需要进行m×t次比较运算,其时间复杂度为O(n2)；所需空间为2×3t,其空间复杂度为O(n)．

1.2 快速转置算法

目前计算机上转置稀疏矩阵,通常是采用快速转置算法．此算法同样针对于三元组结构进行转置,但是在转置过程中需要建立两个辅助数组:

i) 用row size[ ]存放先期统计出来的稀疏矩阵A=(ai,j)n×m各列的非零元素个数,即AT各行的非零元素个数．具体方法为:先将该数组清零,然后扫描存储矩阵的三元组,逐个取出非零元素的列值,并将以此列值为下标的辅助数组元素的值累加1．

ii) 用row start[ ]存放先期计算出来的稀疏矩阵A=(ai,j)n×m各行非零元素在转置后的三元组中应存放的位置．具体方法为:转置矩阵的第 0 行从对应三元组的第1个位置开始存放,并循环计算第 2行,第 3行,…,第n行在对应三元组中的开始存放位置．

该算法的