基于三元组表表示的稀疏矩阵的快速转置算法及其改进.doc

基于三元组表表示的稀疏矩阵的快速转置算法及其改进摘要:介绍基于三元组表表不的稀疏矩阵的快速转置算法，此算法在转置前需要先确定原矩 阵中各列第一个非零元在转置矩阵中的位置，在此使用2个数组作为辅助空间，为了减少算法 所需的辅助空间，通过引入2个简单变量提出一种改进算法该改进算法在时间复杂度保持 不变的情况下，空间复杂度比原算法节省一半需求分析：矩阵作为许多科学与工程计算的数据对象，必然是计算机处理的数据对象之 一在实际应用中，常会遇到一些阶数很高，同时又有许多值相同的元素或零元素的矩阵，在这 类矩阵中，如果值相同的元素或零元素在矩阵中的分配没有规律，则称之为稀疏矩阵为了节 省存储空间，常对稀疏矩阵进行压缩存储压缩存储的基本思想就是:对多个值相同的元素只 分配1个存储空间，对零元素不分配存储空间换句话说，就是只存储稀疏矩阵中的非零元素 稀疏矩阵可以采取不同的压缩存储方法，对于不同的压缩存储方法，矩阵运算的实现也就不 同1. 稀疏矩阵的三元组表表示法根据压缩存储的基本思想,这里只存储稀疏矩阵中的非零元素，因此，除了存储非零元的值以 外，还必须同时记下它所在行和列的位置（i.j）.即矩阵中的1个非零元aij山1个二元组（i,j,aij） 惟一确定。

由此可知，稀疏矩阵可由表示非零元的三元组表及其行列数惟一确定对于稀疏 矩阵的三元组表采取不同的组织方法即可得到稀疏矩阵的不同压缩存储方法，用三元组数组 （三元组顺序表）来表示稀疏矩阵即为稀疏矩阵的三元组表表示法三元组数组中的元素按照 三元组对应的矩阵元素在原矩阵中的位置，以行优先的顺序依次存放三元组表的类型说明如下：# define MAXSIZE 1000 /*非零元素的个数最多为1000*/typedef struct{int row,col; /*该非零元素的行下标和列下标*/ElementType e; /*该非零元素的值*/} Triple;typedef struct{Triple data[MAXSIZE+l]; /*非零元素的二元组表，data⑹未用*/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]加 loposition[col]的计算方法：position] 1]=1position[col]=position[col-l]+num[col-l](其中 2[col[A.n)将三元组表A中所有的非零元素直接放到三元组表B中正确位置上的方法是:position[col] 的初值为三元组表A中列号为col(三元组表B的行号为col)的第1个非零元素的正确位置, 当三元组表A中列号为col的1个元素加入到三元组表B时，贝！J position[col]=position[col]+l, 即:使position[col]始终指向三元组表A中列号为col的下一个非零元素在三元组表B 中的正确位置。

稀疏矩阵的快速转置算法如下：⑴初始化num[]数组；⑵求num[]数组各元素的值；⑶求position[]数组各元素的值；(4)将三元组表A中所有的非零元素直接放到三元组表B中正确位置上快速转置算法的时间主要耗费在4个并列的单循环上，这4个并列的单循环分别执行了 A.n,A.len,A.n-l,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[l.An],position] 1.An]可见,算法在时间上的节省，是以更多的存储空间为代价的 可见,稀疏矩阵的三元组表表示法虽然节约了存储空间，但比起矩阵的正常存储方式来讲，其 实现相同操作要耗费较多的时间，同时也增加了算法的难度，即以耗费更多时间为代价来换取空间的节省3. 稀疏矩阵的快速转置算法的改进在稀疏矩阵的快速转置算法中引入2个辅助向量空间num[]和position]],在下面的改进算法 中只保留num[],另外引入2个变量kl和k2。

num[col]起初用来存放矩阵source中第col列 中非零元素个数(转置后矩阵dest中第col行非零元素的个数)，然后通过修改num[col]中各元 素的值，用num[col]存放转置矩阵source中第col列(转置后矩阵dest中第col行)中第一个非 零元素在三元组表B中的正确位置修改num [col]中各元素的值的操作实现如下：⑴令 kl=num[l];num[l]=l;(2)对于col=2,A.n依次做：k2= num[col]num[col]=kl +num[col-l];kl=k2;在转置过程中，当三元组表A中列号为col的1个元素加入到三元组表B时，则 num[col]=num[col]+l,即:使num[col]始终指向三元组表A中列号为col的下一个非零元素在 三元组表B中的正确位置改进的快速转置算法如下:初始化num［］数组;求num［］数组各元素的值;修改num［］数组各 元素的值;将三元组表A中所有的非零元素直接放到三元组表B中正确位置上显然，上述改进算法的时间复杂度与原算法相同,在空间复杂度上除了三元组表所占用的空 间外,只需要1个辅助向量空间numLL.A.n］和2个简单变量，而算法的空间复杂度仅考虑算法 所需的辅助空间，因此，改进算法的空间复杂度比原算法节约一半。