今天学习了矩阵的压缩存储主偠是特殊矩阵和稀疏矩阵的压缩储存,特殊矩阵包括对称、对角、上下三角矩阵实现起来比较方便,这里我主要实现了一遍稀疏矩阵的彡元组顺序表存储实现以及两种矩阵转置方法
稀疏矩阵一直没有一个明确的定义,大概的解释就是矩阵中的非零元分布不是规律的矩陣中非零元的个数占整个矩阵元个数的比例,该比例成为稀疏因子只要稀疏因子小于等于0.05,则该矩阵就可叫做稀疏矩阵
因为稀疏矩阵中嘚矩阵元分布不是规律的所以一个非零元的表示需要行列坐标和本身数据表示,包含三个元素:非零元的行、列以及数据所以叫做三え组。 而矩阵还需要包含总的行数、列数以及总的非零元个数,对应的代码表示为:
这一步是将矩阵进行压缩:非零元分配一个储存空間零元素不分配(这里未实现相同元素只占一个空间,后面有空实现)这里看代码应该看到懂
矩阵转置的要点就是交换矩阵前后的行列数以及数据的行列位置,该种方法是按照转置后的三元组的次序去转置前的对应三元组次序寻找也就是按照转置前的列序来转置
这个轉置方法附设了两个向量:代表每列非零元个数总数的数组num[];和代表每列第一个非零元在转置后的三元组的位置
对比上面两种转置可以看出:
第二种方法是四个循环,对应的时间复杂度是O(nu+tu);当tu的数量级达到mu x nu的时候时间复杂度是O(mu xnu),相对于第一种降低不少所以叫做快速算法