基于三元组表表示的稀疏矩阵的快速转置算法及其改进
摘 要：介绍基于三元组表表示的稀疏矩阵的快速转置算法，此算法在转置前需要先确定原矩阵中各列第一个非零元在转置矩阵中的位置，在此使用2个数组作为辅助空间，为了减少算法所需的辅助空间，通过引入2个简单变量提出一种改进算法。该改进算法在时间复杂度保持不变的情况下，空间复杂度比原算法节省一半。
关键词：稀疏矩阵；压缩存储；三元组表；快速转置；时间复杂度；空间复杂度
中图分类号：TP311.12文献标识码：B
文章编号：1004-373X(2008)22-078-02
Improvement on Fast Transposition Algorithm to Sparse Matrix Expressed by Triple List
WANG Rong1,2
(1.Xidian University,Xi′an,710071,China;2.Weinan Teachers University,Weinan,714000,China)
Abstract：The fast transposition algorithm to sparse matrix expressed by triple list is introduced.This algorithm needs to determine the position in the transposed matrix position of the first element which is not equal to zero in the original matrix each row,it uses two arrays as auxiliary space.In order to reduce the auxiliary space which the algorithm needed,an improvement is made through introducing two simple variables.The improved algorithm saves a half auxiliary space compared to the original algorithm at the same time complexity.
Keywords：sparse matrix;compression memory；triple list;fast transposition;time complexity;space complexity
矩阵作为许多科学与工程计算的数据对象，必然是计算机处理的数据对象之一。在实际应用中，常会遇到一些阶数很高，同时又有许多值相同的元素或零元素的矩阵，在这类矩阵中，如果值相同的元素或零元素在矩阵中的分配没有规律，则称之为稀疏矩阵。
为了节省存储空间，常对稀疏矩阵进行压缩存储。压缩存储的基本思想就是：对多个值相同的元素只分配1个存储空间，对零元素不分配存储空间。换句话说，就是只存储稀疏矩阵中的非零元素。
稀疏矩阵可以采取不同的压缩存储方法，对于不同的压缩存储方法，矩阵运算的实现也就不同。
1稀疏矩阵的三元组表表示法
根据压缩存储的基本思想，这里只存储稀疏矩阵中的非零元素，因此，除了存储非零元的值以外，还必须同时记下它所在行和列的位置(i,j)，即矩阵中的1个非零元aij由1个三元组(i,j,aij)惟一确定。由此可知，稀疏矩阵可由表示非零元的三元组表及其行列数惟一确定。
对于稀疏矩阵的三元组表采取不同的组织方法即可得到稀疏矩阵的不同压缩存储方法，用三元组数组（三元组顺序表）来表示稀疏矩阵即为稀疏矩阵的三元组表表示法。三元组数组中的元素按照三元组对应的矩阵元素在原矩阵中的位置，以行优先的顺序依次存放。
三元组表的类型说明如下：
＃define MAXSIZE 1000/*非零元素的个数最多为1000*/
typedef struct
{
introw,col; /*该非零元素的行下标和列下标*/
ElementType e；/*该非零元素的值*/
}Triple;
typedef struct
{
Tripledata［MAXSIZE+1］;/* 非零元素的三元组表，data［0］未用*/
int m,n,len;/*矩阵的行数、 列数和非零元素的个数*/
}TSMatrix；
2 稀疏矩阵的快速转置算法
待转置矩阵source和转置后矩阵dest分别用三元组表A和B表示，依次按三元组表A中三元组的次序进行转置，转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。
为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上，需要预先计算以下数据：
(1)待转置矩阵source每一列中非零元素的个数（即转置后矩阵dest每一行中非零元素的个数）。
(2)待转置矩阵source每一列中第一个非零元素在三元组表B中的正确位置（即转置后矩阵dest每一行中第一个非零元素在三元组表B中的正确位置)。
为此，需要设2个数组num［］和position［］，其中num［col］用来存放矩阵source中第col列中非零元素个数（转置后矩阵dest中第col行非零元素的个数）；position［col］用来存放转置矩阵source中第col列（转置后矩阵dest中第col行）中第一个非零元素在三元组表B中的正确位置。
num［col］的计算方法：将三元组表A扫描一遍，对于其中列号为k的元素，给相应的num［k］加1。
position［col］的计算方法：
position［1］=1
position［col］=position［col-1］+num［col-1］ （其中2≤col≤A.n）
将三元组表A中所有的非零元素直接放到三元组表B中正确位置上的方法是：position［col］的初值为三元组表A中列号为col（三元组表B的行号为col）的第1个非零元素的正确位置，当三元组表A中列号为col的1个元素加入到三元组表B时，则position［col］=position［col］+1，即：使position［col］始终指向三元组表A中列号为col的下一个非零元素在三元组表B中的正确位置。
稀疏矩阵的快速转置算法如下：
(1)初始化num［ ］数组；
(2)求num［ ］数组各元素的值；
(3)求position［ ］数组各元素的值；
(4)将三元组表A中所有的非零元素直接放到三元组表B中正确位置上。
快速转置算法的时间主要耗费在4个并列的单循环上，这4个并列的单循环分别执行了A.n，A.len，A.n-1，A.len次，因而总的时间复杂度为O(A.n)+O(A.len)+O(A.n)+O(A.len)，即为O（A.n+A.len）。当待转置矩阵source中非零元素个数接近于A.m×A.n时，其时间复杂度接近于经典算法的时间复杂度O(A.m×A.n)。
快速转置算法在空间耗费上除三元组表所占用的空间外，还需2个辅助向量空间，即num［1..A.n］，position［1..A.n］。可见，算法在时间上的节省，是以更多的存储空间为代价的。
可见，稀疏矩阵的三元组表表示法虽然节约了存储空间， 但比起矩阵的正常存储方式来讲，其实现相同操作要耗费较多的时间，同时也增加了算法的难度,即以耗费更多时间为代价来换取空间的节省。
3 稀疏矩阵的快速转置算法的改进
在稀疏矩阵的快速转置算法中引入2个辅助向量空间num［］和position［］，在下面的改进算法中只保留num［］，另外引入2个变量k1和k2。num［col］起初用来存放矩阵source中第col列中非零元素个数（转置后矩阵dest中第col行非零元素的个数），然后通过修改num［col］中各元素的值，用num［col］ 存放转置矩阵source中第col列（转置后矩阵dest中第col行）中第一个非零元素在三元组表B中的正确位置。修改num［col］中各元素的值的操作实现如下：
(1)令k1=num［1］;num［1］=1;
(2)对于col=2…A.n依次做：
k2= num［col］
num［col］=k1+num［col-1］;
k1=k2;
在转置过程中，当三元组表A中列号为col的1个元素加入到三元组表B时，则num［col］=num［col］+1，即：使num［col］始终指向三元组表A中列号为col的下一个非零元素在三元组表B中的正确位置。
改进的快速转置算法如下：初始化num［ ］数组；求num［ ］数组各元素的值；修改num［ ］数组各元素的值；将三元组表A中所有的非零元素直接放到三元组表B中正确位置上。
显然，上述改进算法的时间复杂度与原算法相同，在空间复杂度上除了三元组表所占用的空间外，只需要1个辅助向量空间num［1..A.n］和2个简单变量，而算法的空间复杂度仅考虑算法所需的辅助空间，因此，改进算法的空间复杂度比原算法节约一半。
参考文献
［1］耿国华.数据结构C语言描述［M］.西安：西安电子科技大学出版社，2002.
［2］严蔚敏,吴伟民.数据结构（C语言版）［M］.北京：清华大学出版社，1997.
［3］殷人昆，陶永雷，谢若阳,等.数据结构(用面向对象方法与C++描述).北京：清华大学出版社，1999.
［4］ 朱战立.数据结构使用C++语言.西安：西安电子科技大学出版社，2001.
［5］谢应科,张涛,韩承德.实时SAR成像中矩阵转置的设计与实现.计算机研究与发展，2003，40(1):6-11.
［6］江帆,刘光平,周志敏.多计算机上分布式矩阵转置.微处理机，2002(2):34-37.
作者简介 王 荣 女，1972年出生，陕西华阴人，渭南师范学院计算机科学系讲师，西安电子科技大学硕士研究生。
