博客

稀疏矩阵(Sparse Matrix)

注：压缩存储的矩阵可以分为特殊矩阵和稀疏矩阵。对于那些具有相同元素或零元素在矩阵中分布具有一定规律的矩阵，被称之为特殊矩阵。对于那些零元素数据远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称之为稀疏矩阵。

1. 稀疏矩阵的概念

• 在矩阵中，若数值为0的元素数目远远多于非0元素的数目时，则称该矩阵为稀疏矩阵。与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。

2. 稀疏矩阵的特性

• 稀疏矩阵其非零元素的个数远远小于零元素的个数，而且这些非零元素的分布也没有规律。
• 稀疏因子是用于描述稀疏矩阵的非零元素的比例情况。设一个n*m的稀疏矩阵A中有t个非零元素，则稀疏因子$\delta$的计算公式如下：$\delta = \frac{t}{n*m}$(当这个值小于等于0.05时，可以认为是稀疏矩阵)

3. 稀疏矩阵的压缩存储

• 存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种运算，如转置运算、加法运算、乘法运算等。但对于稀疏矩阵来说，采用二维数组的存储方法既浪费大量的存储单元用来存放零元素，又要在运算中花费大量的时间来进行零元素的无效计算，显然不科学。所以必须考虑对稀疏矩阵进行压缩存储。
• 对稀疏矩阵进行压缩存储的一种较好的方法是：只存储在矩阵中极少数的非零元素，为此必须对每一个非零元素，保存它的下标和值。可以采用一个三元组Trituple
  <row,column,value>
  <script type=”math/tex” id=”MathJax-Element-4″>

  </script>来唯一地确定一个矩阵元素。因此，稀疏矩阵需要使用一个三元组数组(亦称为三元组表)来表示。
  

• 可以仿照对称矩阵的压缩存储，可用一维数组B存储稀疏矩阵A(这要区分两种存储方式：行优先方式和列优先方式)。

参考文献：
[1]《数据结构(用面向对象方法与C++语言描述)(第2版)》殷人昆——第四章
[2] 百度搜索关键字：稀疏矩阵