稀疏矩阵

什么样的矩阵叫稀疏矩阵

几乎由零值组成的矩阵叫稀疏矩阵。在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时，则称该矩阵为稀疏矩阵（sparse matrix），该比值称为这个矩阵的稠密度。与之相区别的是，如果非零元素的分布存在规律（如上三角矩阵、下三角矩阵、对角矩阵），则称该矩阵为特殊矩阵。比较基本的定义是矩阵中的大多数元素为零，并且可以利用零元素节约大量存储、运算和程序运行时间。矩阵：矩阵指在数学中，按照长方阵列排列的复数或实数集合，最早来自方程组的系数及常数所构成的方阵，由1英国数学家凯利首先提出。它是高等代数学中的常见工具，其运算是数值分析领域的重要问题。将矩阵分解为简单矩阵的组合，可以在理论和实际应用上简化矩阵的运算。成书最迟在（东汉）前期的《九章算术》中，用分离系数法表示线性方程组，得到了其增广矩阵。在消元过程中，使用的把某行乘以某一非零实数、从某行中减去另一行等运算技巧，相当于矩阵的初等变换。但那时并没有现今理解的矩阵概念，虽然它与现有的矩阵形式上相同，但在当时只是作为线性方程组的标准表示与处理方式。矩阵正式作为数学中的研究对象出现，则是在行列式的研究发展起来后。逻辑上，矩阵的概念先于行列式，但在实际的历史上则恰好相反。

稀疏矩阵

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

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

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

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

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

邻接表表示法

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

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

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

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

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

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

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

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