java什么是特殊矩阵

Question

如题所述

Answer 1

对于一个m×n的矩阵，设s为矩阵的元素总个数s=m×n，设t为矩阵中非零元素的个数，满足t<<s的矩阵称为稀疏矩阵。一个不稀疏的矩阵称作稠密矩阵。

稀疏矩阵的零元素非常多，且分布无规律，所以稀疏矩阵的压缩存储方法为：只存储矩阵中的非零元素，按照三元组的形式存储。三元组由非零元素，该元素行下标和该元素列下标三个数据构成，放在一个列数为3的数组中。

存储结构又分数组结构和链表结构两个大类，其中链表结构又有一般链表、行指针数组链表和行指针的十字链表存储结构，是链表的直接应用和组合应用。

数组结构

基于向量类，首先要设计三元组类，用于存放位置和数值信息：

[java] view plain copy

package ArrayVectorSetMatrix;  

/** 

* @author sun 

* åˆ›å»ºæ—¶é—´ï¼š2017å¹´4月15日下午3:54:37 

*/  

public class Three {  

public int row;//行号  

public int col;//列号  

public double value;//数值  

public Three(int r,int c,double v){  

row = r;  

col = c;  

value = v;  

}  

Three(){  

this(0,0,0.0);  

}  

}  


接着建立稀疏矩阵类：

[java] view plain copy

package ArrayVectorSetMatrix;  

/** 

* @author sun 

* åˆ›å»ºæ—¶é—´ï¼š2017å¹´4月15日下午3:57:32 

*/  

//借用MyVectorç±»  

public class SpaMatrix {  

int rows;//行数  

int cols;//列数  

int dNum;//非零元素个数  

MyVector v;  

SpaMatrix(int max){  

rows = cols = dNum = 0;  

v = new MyVector(max);  

}  

public void evaluate(int r,int c,int d,Three[] item)throws Exception{  

//给矩阵赋值  

rows = r;  

cols = c;  

dNum = d;  

for(int i=0;i<d;i++){  

v.add(i,item[i]);  

}  

}  

public SpaMatrix transpose(){//转置  

SpaMatrix a = new SpaMatrix(v.size());  

a.cols = rows;  

a.rows = cols;  

a.dNum = dNum;  

for(int i=0;i<dNum;i++){  

Three t = (Three)v.get(i);//取得三元组  

a.v.add(i,new Three(t.col,t.row,t.value));//注意行列号变换  

}  

return a;  

}  

public void print(){  

System.out.print("矩阵行数为："+rows);  

System.out.print(",矩阵列数为："+cols);  

System.out.println(",非零元素个数为："+dNum);  

System.out.println("矩阵非零元素三元组为：");  

for(int i=0;i<dNum;i++){  

System.out.println("a<"+((Three)v.get(i)).row+","  

+((Three)v.get(i)).col+">="  

+((Three)v.get(i)).value);  

}  

}  

}  


最后测试并完成矩阵转置（无序），其实在三元组中就是行号和列号互换：

[java] view plain copy

package ArrayVectorSetMatrix;  

/** 

* @author sun 

* åˆ›å»ºæ—¶é—´ï¼š2017å¹´4月15日下午4:15:38 

*/  

public class TestSpaMatrix {  

public static void main(String[] args) {  

SpaMatrix matrixA = new SpaMatrix(10);  

SpaMatrix matrixB;  

Three[] a = new Three[6];  

a[0] = new Three(1,3,11.0);  

a[1] = new Three(1,5,17.0);  

a[2] = new Three(2,2,25.0);  

a[3] = new Three(4,1,19.0);  

a[4] = new Three(5,4,37.0);  

a[5] = new Three(6,7,50.0);  

try{  

matrixA.evaluate(6, 7, 6, a);  

System.out.println("原矩阵：");  

matrixA.print();  

System.out.println("转置后的矩阵：");  

matrixB = matrixA.transpose();  

matrixB.print();  

}  

catch(Exception e){  

System.out.println(e.getMessage());  

}  

}  

}  

/* 

原矩阵： 

矩阵行数为：6,矩阵列数为：7,非零元素个数为：6 

矩阵非零元素三元组为： 

a<1,3>=11.0 

a<1,5>=17.0 

a<2,2>=25.0 

a<4,1>=19.0 

a<5,4>=37.0 

a<6,7>=50.0 

转置后的矩阵： 

矩阵行数为：7,矩阵列数为：6,非零元素个数为：6 

矩阵非零元素三元组为： 

a<3,1>=11.0 

a<5,1>=17.0 

a<2,2>=25.0 

a<1,4>=19.0 

a<4,5>=37.0 

a<7,6>=50.0 

*/  


三元组链表（链表结构存储）

（1）带头结点的三元组链表：头结点存储矩阵的行数列数，其他结点按行号排序，每个结点存的是三元组中的三个元素。该法实现矩阵运算的时间效率不高，因为访问慢。

（2）行指针数组结构的三元组链表：没有头结点，就是设置一个行指针数组，第一列为行号，第二列为指针，每个指针指向该行的第一个不为0元素值和其列号构成的结点，然后继续向后直到把本行所有不为0元素结点连接完成。这样，从某行进入找某列元素的操作比较容易，但从列进入找比较难。

（3）三元组十字链表结构：在上一问题基础上再加一个列指针数组，这样每个结点既有横向勾连，也有纵向勾连，都没有头结点，但每个结点的行号和列号不能省略。

不做演示。

Answer 2

好巧我们在纠结同一个问题问题