稀疏矩阵

什么是稀疏矩阵
矩阵中有很多零，其中非零元素只是占了一小部分，大部分都是零，这种就叫稀疏矩阵。
稀疏矩阵概念没有严格的界定，0 的个数/在矩阵元素总数中占的百分比没有严格的规定，凭感觉的概念。

在严版数据结构中的定义，这里的零 可以是常数c 。

c是不是零 ，就是概念上的分歧。

三元组表示法
第一行（下标0）：一般不存储任何一个元素
第一个代表非0元素个数，第二个代表行数，第三个代表列数

从下标1开始存储矩阵中的元素，一般按照行优先存储。
当然可以按照列优先，或者存储任意位置 也行，把所有元素存进去即可。

邻接表表示法

定义一个一维数组，数组的下标 对应于 要存储矩阵的行标
数组的元素 是一些指针，每个指针都指向一条链表，链表中的结点就保存了矩阵中的非零元素信息。
其中第一个信息 是非0元素的值，
第二个信息 是非0元素所在的列标

每条链表所在的行标保存了 这条链表中所有元素的行标信息。
每条链表中的结点保存了元素的值和列标信息。

每个十字链表都有一个 头节点，它一共有五个域
第一行：第一个域：行数，第二个域：列数，第三个域：非零元素个数
第二行：两个域引出两个指针，指向两个数组
第四个域：列数组，第五个域：行数组。
两个数组内存储了一些指针，指向表内的非零元素。

给表中的非零元素都申请一个结点
表元素结点类型 和表的头节点类型 是一样的，保存的信息不一样。

元素结点
第一个分量存的：行号
第二个分量存的：列号
第三个分量存的：元素值
第四、五个分量存的：指针

十字链表构造 和 二维数组 是类似的。
只不过是只给非零元素分配存储空间。

行方向上 结点之间的指针是从结点第五个域引出来的。

列方向上 结点之间的指针是从结点第四个域引出来的。

在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。 最常用的稀疏矩阵存储格式为列压缩存储(compressedcolumn storage,CCS) 或行压缩存储( ompressedrow storage,CRS)。 阶包含 nnz 个非零元的稀疏矩阵需要用列指针、行指标和非零值三个一维数组表示，其中 nnz 维非零值数组按列记录所有非零元素，同样维数的行指标记录每列非零元所在的行，n+1 维的列打针向量记录每一列(包括 n+1 列) 的开始位置。还有三元组表和链接存储等其他格式等。符号稀疏矩阵(symbolic sparse matrix) 只需列指针和行指标两个数组。此外，稀疏向量是稀疏矩阵的特例，只需用指标和非零值两个数组表示，最近在电路、电子结构等领域得到越来越多的重视。

几乎由零值组成的矩阵叫稀疏矩阵。 在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。 矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时，则称该矩阵为稀疏矩阵（sparse matrix），该比值称为这个矩阵的稠密度。 与之相区别的是，如果非零元素的分布存在规律（如上三角矩阵、下三角矩阵、对角矩阵），则称该矩阵为特殊矩阵。比较基本的定义是矩阵中的大多数元素为零，并且可以利用零元素节约大量存储、运算和程序运行时间。 矩阵： 矩阵指在数学中，按照长方阵列排列的复数或实数集合，最早来自方程组的系数及常数所构成的方阵，由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为非零元素个数

测试类及结果