欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

稀疏矩阵的压缩存储

程序员文章站 2022-07-04 20:06:49
...

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[];//存储每列的第一个元素
}
相关标签: 数据结构