稀疏矩阵的压缩存储
程序员文章站
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[];//存储每列的第一个元素
}
上一篇: POJ-3176 Cow Bowling
下一篇: 物理引擎探究(8)---碰撞处理