数据结构之稀疏矩阵
2018-02-27 本文已影响129人
理想是一盏灯
稀疏矩阵
应用背景
用户产品关系矩阵，比如某个公司的所有用户对自己喜爱的产品有一个评分，但是因为该公司用户和产品种类数量繁多，就有可能存在用户通过产品产生的关联性不是很大的情况（没有共同评价过的产品），就产生了稀疏矩阵。
用户产品关系矩阵
定义
百科的定义：在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。
存储
一般矩阵采用二维数组存储，但是由于稀疏矩阵中存在大量的“空”值，占据了大量的存储空间，而真正有用的数据却少之又少，且在计算时浪费资源，所以要进行压缩存储以节省存储空间和计算方便。
稀疏矩阵
一般采用三元组线性表表示，可以采用顺序或链式方式存储，比如上面的稀疏矩阵用三元组表示为(1,3,1),(2,2,2),(3,1,3),(4,4,5),(5,5,6),(6,6,7),(6,7,4)
三元组的类型定义
三元组的类型定义
稀疏矩阵类型定义
成员包括矩阵的函数、列数、非零元素的集合,该定义用到了前面讲的线性表的有序顺序存储结构和有序链式存储结构
稀疏矩阵类型定义
矩阵操作
矩阵转置
插入时间复杂度O(t),所以总时间复杂度为O(t*t) ,t为非零元素个数
矩阵转置实现一
更高效的转置
插入时间复杂度O（1），所以总时间复杂度O（n*t）,其中n为列数，t为非零元素个数
矩阵转置实现二
矩阵加法
矩阵加法
测试类及结果
测试类
测试结果
