我们知道矩阵是一个非常强大的数据结构,在动态规划以及各种图论算法上都有广泛的应用,当然矩阵有着不足的地方就是空间和时间
复杂度都维持在N2上,比如1w个数字建立一个矩阵,在内存中会占用1w*1w=1亿的类型空间,这时就会遇到outofmemory。。。那么面
临的一个问题就是如何来压缩矩阵,当然压缩的方式有很多种,这里就介绍一个顺序表的压缩方式:三元组。
一:三元组
有时候我们的矩阵中只有零星的一些非零元素,其余的都是零元素,那么我们称之为稀疏矩阵,当然没有绝对的说有多少个零元素才算稀疏。
针对上面的这个无规律的存放非零元素,三元组提出了一种方法,就是仅仅记录矩阵中的非零元素以及它的行,列以及值N(x,y,v)构成的一个三元
组,标识一个稀疏矩阵的话,还要记录该矩阵的阶数,这样我们就将一个二维的变成了一个一维,极大的压缩的存储空间,这里要注意的就是,三
元组的构建采用“行“是从上到下,“列”也是从左到右的方式构建的顺序表。
其实说到这里也就差不多了,我们只要知道三元组是用来做矩阵压缩的一个顺序存储方式即可,然后知道怎么用三元组表来做一些常规的矩阵
运算,好了,既然说已经做成线性存储了,那就做个“行列置换”玩玩。
二:行列置换
做行列置换很容易,也就是交换"非零元素"的(x,y)坐标,要注意的就是,原先我们的三元组采用的是”行优先“,所以在做转置的时候需要
遵循"列优先“。
最后是总的代码:
View Code