1.什么是稀疏矩阵 

稀疏矩阵指的是矩阵中的非零元素个数明显小于矩阵元素的个数。 

而稀疏矩阵的压缩存储是指只存储非零元素。

2.稀疏矩阵的存储方式 

以下是一个稀疏矩阵： 


(1)表示稀疏矩阵非零元素的三元组 


需要一种数据结构来存储非零元素的行数，列数，值。

public class Triple{
    private int row;//行数
    private int col;//列数
    private int value;//值
}

(2)稀疏矩阵三元组顺序表表示 


用顺序表存储的缺点：也就是顺序表的缺点，删除和查找元素，以及设置元素值的时间复杂度是O(n),n是数组中的元素个数。

(3)稀疏矩阵三元组单链表表示 


注意:这个图没有画出上面那个稀疏矩阵全部的元素。 

缺点:需要存储矩阵的行数和列数，找到某个元素，需要遍历这个元素前面的所有元素。

//结点
public class Node<T>{
    private T data;
    private Node<T> next;
}
这里的T是上面提到的Triple，三元组
//单链表
public class SinglyLinkedList<T>{
   private Node<T> head;
}
//稀疏矩阵三元组单链表表示
public class MatrxiList{
  private int row;
  private int col;
  private SinglyLinkedList<Triple> list;
}

(4)稀疏矩阵三元组行的单链表表示 


注意:这图表示的意思就是一个链表里面包含了其他链表(这里是4个) 

缺点：可以很快找到同一行中的其他元素，但是很难找到同一列中的其他元素。

(5)稀疏矩阵十字链表表示 


public class CrossNode{
    private Triple data;//存储的非零元素
    private CrossNode right;//下一个行元素
    private CrossNode down;//下一个列元素
}
public class CrossList{
    private int row;//矩阵的行数
    private int col;//矩阵的列数
    private int[] rowheads[];//存储每行的第一个元素
    private int[] colheads[];//存储每列的第一个元素
}

什么是稀疏矩阵：
在矩阵中，我们常见的都是稠密矩阵，即非0元素数目占大多数时；若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵。与之相区别的是，如果非零元素的分布存在规律(如上三角矩阵、下三角矩阵、对角矩阵)，则称该矩阵为特殊矩阵。
下图1为一个稀疏矩阵的示例
稀疏因子是用于描述稀疏矩阵的非零元素的比例情况。设一个n*m的稀疏矩阵A中有t个非零元素，则稀疏因子δ的计算公式如下：δ=t/(n∗m), 当这个值小于等于0.05时，可以认为是稀疏矩阵
稀疏矩阵的存储方式
存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种运算。但对于稀疏矩阵而言，若用二维数组来表示，会重复存储了很多个0了，浪费空间，而且要花费时间来进行零元素的无效计算。所以必须考虑对稀疏矩阵进行压缩存储。
稀疏矩阵的压缩存储，数据结构提供有 3 种具体实现方式：三元组顺序表；
行逻辑链接的顺序表：可以看作是三元组顺序表的升级版，即在三元组顺序表的基础上改善了提取数据的效率。
十字链表；
使用十字链表压缩存储稀疏矩阵时，矩阵中的各行各列都各用一各链表存储，与此同时，所有行链表的表头存储到一个数组(rhead)，所有列链表的表头存储到另一个数组(chead)中。
想要了解更多相关知识，请关注 html中文网！！