对于基本类型数组,比如int数组,如果new了之后没有显式的初始化,数组中的元素值将自动初始化为0,如果是float数组值为0.0,
而对于对象数组将被初始化为null。
稀疏矩阵可以说是存在较多的0(int数组)或null值(对象数组),手动化初始的值较少的二维数组
(或多阶数组),稀疏矩阵的压缩存储是为了节省空间而对这类矩阵进行压缩存储。
所谓的压缩存储是:为多个相同的值分配一个存储空间,为null或0不分配空间。
前者只能是对特殊矩阵(比如对称矩阵或特殊矩阵)的压缩,这里只讨论的是后者。
直接上代码,注释完善
import java.util.Arrays;
/**
* 关于稀疏矩阵的压缩存储与基本运算
* 压缩存储只存储矩阵的非空元素
* 数组索引都是从0开始
*/
public class MatrixDemo<E> {
public static void main(String[] args) {
MatrixDemo<Integer> md = new MatrixDemo<Integer>();
Integer[][] M = new Integer[6][7];
M[0][1] = 12; M[0][2] = 9;
M[2][0] = -3; M[2][5] = 14;
M[3][2] = 24; M[4][1] = 18;
M[5][0] = 15; M[5][3] = -7;
//md.compreMatrix(M);
Integer[][] m = new Integer[3][4];
m[0][0]=3;m[0][3]=5;
m[1][1]=-1;m[2][0]=2;
Integer[][] n = new Integer[4][2];
n[0][0]=5;n[0][1]=2; n[1][0]=1;
n[2][0]=-2; n[2][1]=4;
md.multiMatrix(m, n);
System.out.println();
md.multiMatrix(md.compreMatrix(m), md.compreMatrix(n));
}
/**
* 把稀疏矩阵进行压缩
*/
public Matrix compreMatrix(E[][] e){
Matrix matrix = new Matrix();
int mu = e.length;
int nu = e[0].length;
for(int i=0;i<mu;i++){
for(int j=0;j<nu;j++){
if(e[i][j] != null){ //压缩非空元素
Triple<E> triple = new Triple<E>(i,j,e[i][j]);
matrix.add(triple);
}
}
}
matrix.mu = mu;
matrix.nu = nu;
//下面是查看元素
for(int i=0;i<matrix.tu;i++){
Triple<E> t = matrix.data[i];
System.out.print(t.i + " " + t.j + " " + t.e);
System.out.println();
}
System.out.println("----------");
// transMatrix(matrix);
// transMatrix2(matrix);
return matrix;
}
/**
* 压缩矩阵的转置,方法一
* 原理:1.将矩阵的行列对应的值相互交换
* 2.将矩阵的行列下标交换
* 3.重新排列新矩阵的顺序(按行排,即行中非空元素出现的次序)
*/
public Matrix transMatrix(Matrix m){
Matrix t = new Matrix(); //转置后的矩阵
t.mu = m.nu;
t.nu = m.mu;
if(m.tu == 0) return null;
for(int col=0; col<m.nu;col++){ //根据m的列的顺序排列转换矩阵的顺序
for(int p=0;p<m.tu;p++){
if(m.data[p].j == col){
Triple<E> triple = new Triple<E>(m.data[p].j, m.data[p].i, (E)m.data[p].e);
t.add(triple);
}
}
}
System.out.println("矩阵置换方法一");
for(int i=0;i<t.tu;i++){
Triple<E> tr = t.data[i];
System.out.print(tr.i + " " + tr.j + " " + tr.e);
System.out.println();
}
return t;
}
/**
* 压缩矩阵的转置,方法二
* 原理:欲求得转置后的矩阵t的顺序,可以先求得m的每一列的第一个非空元素在
* t中的索引cpot[col],并确定m每一列中的非空元素的个数num[col]
* 公式很容易得到:1.cpot[0] = 0;
* 2.cpot[col] = cpot[col - 1]+ num[col-1] (1<col<m.nu)
*/
public Matrix transMatrix2(Matrix m){
Matrix t = new Matrix(); //转置后的矩阵
t.mu = m.nu;
t.nu = m.mu;
//num和cpot数组的初始化
int[] num = new int[m.nu];
for(int ti=0;ti<m.tu;ti++){ //num初始化
num[m.data[ti].j]++;
}
int[] cpot = new int[m.nu];
cpot[0] = 0;
//求第col列中第一个非空元素在t中的位置
for(int col=1;col<m.nu;col++){ //cpot初始化
cpot[col] = cpot[col-1] + num[col - 1];
}
//进行转换
for(int p=0;p<m.tu;p++){
int col = m.data[p].j;
int q = cpot[col];
Triple<E> triple = new Triple<E>(m.data[p].j, m.data[p].i, (E)m.data[p].e);
t.add(q, triple);
cpot[col]++; //这个位置的下一个位置存储此列的下一个元素
}
//查看
System.out.println("矩阵置换方法二");
for(int i=0;i<t.tu;i++){
Triple<E> tr = t.data[i];
System.out.print(tr.i + " " + tr.j + " " + tr.e);
System.out.println();
}
return t;
}
/**
* 两稀疏矩阵相乘。
* 前提:1.矩阵元素能够相乘
* 2.一个矩阵的列等于另一个矩阵的行
* 原理:假设两矩阵M与N相乘,前提M的列M.col要等于N的行N.row(反之亦可)
* 得到结果矩阵Q, Q.row=M.row, Q.col = N.col
* 而且Q[i][j] += M[i][k] * N[k][j] 0<i<M.row,0<j<N.col,0<k<M.col或N.row
*/
public Integer[][] multiMatrix(Integer[][] m,Integer[][] n){
Integer[][] q = new Integer[m.length][n[0].length];
for(int i=0;i<m.length;i++){
for(int j=0;j<n[0].length;j++){
int num = 0;
for(int k=0;k<n.length;k++){
num += (m[i][k]==null?0:m[i][k]) * (n[k][j]==null?0:n[k][j]);
}
q[i][j] = num;
}
}
//打印结果
for(int i=0;i<q.length;i++){
for(int j=0;j<q[0].length;j++){
System.out.print(q[i][j]+" ");
}
System.out.println();
}
return q;
}
/**
* 压缩矩阵的乘法运算
* 稀疏矩阵进行乘法运算时即使含有0元素也相乘了,
* 为避免这种情况,进行矩阵压缩后再相乘
* 压缩矩阵相乘原理:
* 1.先把稀疏矩阵进行压缩
* 2.求出m与n的每一行的第一个非0元素在m与n中的位置
* 3.遍历m每行的非0元素,
*/
public Matrix multiMatrix(Matrix m,Matrix n){
Matrix q = new Matrix();
q.mu = m.mu;
q.nu = n.nu;
//初始化各行第一个非0元素的位置表
int[] mNum = new int[m.mu];
for(int len=0;len<m.tu;len++){ //每行有多少个非0元素
mNum[m.data[len].i]++;
}
m.rpos = new int[m.mu];
m.rpos[0] = 0;
for(int mRow=1;mRow<m.mu;mRow++){ //每行第一个非0元素在m中的位置
m.rpos[mRow] = m.rpos[mRow-1] + mNum[mRow-1];
}
int[] nNum = new int[n.mu];
for(int len=0;len<n.tu;len++){ //每行有多少个非0元素
nNum[n.data[len].i]++;
}
n.rpos = new int[n.mu];
n.rpos[0] = 0;
for(int nRow=1;nRow<n.mu;nRow++){ //每行第一个非0元素在n中的位置
n.rpos[nRow] = n.rpos[nRow-1] + nNum[nRow-1];
}
//初始化完毕,开始计算
if(m.tu * n.tu !=0){
for(int arow=0;arow<m.mu;arow++){ //一行一行处理
int mlast=0;
if(arow < m.mu-1)
mlast = m.rpos[arow+1];
else
mlast = m.tu;
for(int p=m.rpos[arow];p<mlast;p++){ //从这一行第一个非0索引到最后一个非0索引
int brow = m.data[p].j; //由于m.j=n.i,由此可以求出与此m元素相乘的n元素
int nlast=0;
if(brow < n.mu-1)
nlast = n.rpos[brow+1];
else
nlast = n.tu;
for(int w=n.rpos[brow];w<nlast;w++){
int ccol = n.data[w].j; //同一行的非0元素的列索引必然不相同
int sum = (Integer)m.data[p].e * (Integer)n.data[w].e;
if(sum!=0){ //除去0元素
Triple<Integer> triple = new Triple<Integer>(arow, ccol , sum);
q.add(triple);
}
}
}
}
}
//打印结果
for(int i=0;i<q.tu;i++){
Triple<E> tr = q.data[i];
System.out.print(tr.i + " " + tr.j + " " + tr.e);
System.out.println();
}
return q;
}
/**
* 非空元素用三元组表示
*/
class Triple<E>{
int i; //元素的行下标
int j; //元素的列下标
E e; //元素值
Triple(int i,int j,E e) {
this.i = i;
this.j = j;
this.e = e;
}
}
/**
* 压缩矩阵
*/
class Matrix{
Triple[] data; //存储三元组的数组
int mu; //矩阵的行数
int nu; //矩阵的列数
int tu; //非空个数
int[] rpos; //各行第一个非0元素的位置表
public Matrix(){
this(10);
}
public Matrix(int capacity) {
data = new Triple[capacity];
}
/**
* 是否需要扩充容量
*/
public void ensureCapacity(int minCapacity) {
int oldCapacity = data.length;
if (minCapacity > oldCapacity) { //指定最小容量比原来容量大才扩充
int newCapacity = (oldCapacity * 3) / 2 + 1; //扩充原容量的1.5倍加1
if (newCapacity < minCapacity) //扩充后还是小于要求的最小容量,则扩充容量为最小容量
newCapacity = minCapacity;
data = Arrays.copyOf(data, newCapacity);
}
}
//添加元素到压缩矩阵
public boolean add(Triple triple){
ensureCapacity(tu + 1);
data[tu++] = triple; //size++
return true;
}
//在指定位置添加元素(此添加非彼添加)
public boolean add(int index,Triple triple){
if (index >= tu || index < 0) //检查是否越界
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "+ tu);
ensureCapacity(tu + 1);
data[index] = triple;
tu++;
return true;
}
}
}
分享到:
相关推荐
c 语言实现 稀疏矩阵 的创建 和 C语言 压缩存储 压缩矩阵转置
1、 掌握稀疏矩阵的压缩存储存储方法。 2、 能利用三元组顺序表表示并实现稀疏矩阵。 3、 会利用三元组顺序表实现矩阵的加法运算。 二、 实验要求 1、 进行加法运算的两个矩阵由用户输入。并且用三元组顺序表表示。...
稀疏矩阵的压缩存储方法及主要运算的实现
稀疏矩阵的运算源代码实验报告,自己做的实验报告,传上来大家享用。稀疏矩阵的运算源代码实验报告,自己做的实验报告,传上来大家享用。
实现矩阵的存储及运算;实现特殊矩阵的压缩存储方法。
在矩阵运算中和矩阵输入输出中,最方便的存储方式就是二维数组,对矩阵进行压缩不能简化矩阵运算,对输入输出也不能提供便利,而降低运算的时间复杂度主要与算法有关,一般对矩阵压缩后其运算的复杂度会增加。...
三对角矩阵是一类很重要的...但是,对于那些非零元素在矩阵中的分布没有规律的特殊矩阵(如稀疏矩阵),则需要寻求其他的方法来解决压缩存储问题。另外,给出两个三角矩阵,然后对这两个三角矩阵进行加减乘法运算和转置
数据结构与算法课程实验报告 实验三:稀疏矩阵的压缩存储及运算 姓名:CLL 班级: 学号:2014326601072 实验三 稀疏矩阵的压缩存储及运算 实验内容: 实现稀疏矩阵的压缩存储方法以及在特定存储方法下的基本运算。...
1、掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩...掌握稀疏矩阵的各种存储结构以及基本运算实现算法。 2、掌握广义表的定义、存储结构和运算。 3、掌握递归算法的设计,递归算法到非递归算法的转换
稀疏矩阵的压缩存储。 包含算法:快速转置算法、矩阵乘法运算、矩阵加法运算、打印矩阵信息。
本程序简单实现了《数据结构》课本 严蔚敏 吴伟民编著 清华大学出版社 算法5.1和5.2即稀疏矩阵的压缩存储及其转置算法。
稀疏矩阵压缩存储的基本操作实现实验 要求:数据元素类型ElemType取float。 1)从键盘输入两个稀疏矩阵A、B的各元素。(行<=5,列<=5) 2)完成矩阵的加法运算,并输出。
按照压缩存储的概念,只存储稀疏矩阵的非零元,以两个三元组{i,j,e}来表示矩阵的非零元的行,列和数值,就确定了一个非零元.由此,稀疏矩阵可由表示非零元的三元数组及行列数确定. 2.用户输入数据作为三元组的...
5.1.3 特殊矩阵的压缩存储 5.2 稀疏矩阵的三元组存储 5.2.1 三元组表 5.2.2 稀疏矩阵的运算 5.3 稀疏矩阵的十字链表存储 5.3.1 十字链表的组成 5.3.2 十字链表的有关算法 5.4 广义表 5.4.1 广义表的概念和...
按照压缩存储的概念,只存储稀疏矩阵的非零元,以两个三元组{i,j,e}来表示矩阵的非零元的行,列和数值,就确定了一个非零元.由此,稀疏矩阵可由表示非零元的三元数组及行列数确定.  2.用户输入数据作为...
1.掌握使用VC++上机调试数组的基本方法; 2.通过此问题掌握了解数组的类型定义和表示方法;特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现。
稀疏矩阵和矢量格式:稀疏格式避免存储和处理零条目,从而减少了内存消耗和计算时间。 压缩的稀疏行,压缩的稀疏列:矩阵向量乘法和矩阵矩阵乘法的最佳选择 密钥字典:创建稀疏矩阵然后将其复制为另一种格式的最佳...
在线压缩感知方法及其在漏磁检测中的应用.pdf,以长...仿真试验证明了所提出在线压缩算法极大地减少了在线环境压缩编码的运算复杂度,具有简单迅速、压缩比高、重构精度高等优点,符合漏磁检测数据在线压缩的实际要求。