落絮飞雁的个人网站

顺流而下,把梦做完

稀疏矩阵转置之快速转置法

数据结构作业题目 = =
前情回顾:矩阵转置-简单代码

要你对一个三元表进行步骤最少的转置,你可能会想,如果知道三元表中每一项在转置后的新的三元表中的位置,然后直接放进去,岂不是极大的缩小了时间复杂度?没错!快速转置法正是基于这种思想而设计的。
那么如何知道三元表中某一项的位置呢?在课本98页的a.data这个三元表可以看到,j为列号,在转置后即为新的三元表的行号,三元表正是按照行序进行排列的,而j=1有2个、j=2有2个、j=3有2个、j=4有1个、j=6有1个。根据这些数据按照从小到大排列,j=1的项在新的三元表中应占据第1、2位,j=2的项在新的三元表中应占据第3、4位,j=3的项在新的三元表中应占据第5、6位,j=4应占据第7位,j=6应占据第8位。

接下来就轻松多了,转置的时候直接从第一项读起,读取其j值,比如课本中a.data这个三元表的第一项的j值为2,因为j=2占据第3、4位,所以应该从第三位开始放,接下来如果读取的某一项的j值也是2,就放在第4位。因为j=2的项只有两个,所以第5位绝对不会被j=2的项占据,第5、6项本来就是留给j=3的。再比如当读到j=6的那项时,第8位是留给它的,就可以直接放进第8位了。这样,读取每一项,都能在三元表中找到相应的位置,这就是稀疏矩阵快速转置的原理。

代码:

参考:
【LB】稀疏矩阵的快速转置原理及其算法


原文转自:稀疏矩阵转置之快速转置法|落絮飞雁的个人网站
授权协议:创作共用 署名-非商业性使用 2.5 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。