Question

数据结构之稀疏矩阵

Answer 1

用户产品关系矩阵，比如某个公司的所有用户对自己喜爱的产品有一个评分，但是因为该公司用户和产品种类数量繁多，就有可能存在用户通过产品产生的关联性不是很大的情况（没有共同评价过的产品），就产生了稀疏矩阵。

百科的定义：在 矩阵 中，若数值为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为非零元素个数

测试类及结果