稀疏矩阵
一、稀疏矩阵的定义
1、稀疏矩阵的概念
矩阵：矩阵是一个具有m行*n列的数表，共包含m*n个元素（元素），每个元素处在确定行和列的交点位置上，它与一对行号和列号唯一对应。当一个矩阵中的行数和列数相同时，即m=n时，则称为n阶矩阵或方阵。
稀疏矩阵：一般定义为其矩阵中非零元素的个数远远小于零元素的个数。
2、稀疏矩阵的三元组线性表表示
在计算机中存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问到任何一个元素，也就是说，访问任一元素的时间都相同，每个元素的存储位置是通过对下标的简单计算而得到的，因此能够较容易地实现矩阵的各种运算，如转置运算、加法运算、乘法运算等。但对于稀疏矩阵来说，采用二维数组的存储方法既浪费大量的存储空间用来存放零元素，又要在运算中花费大量的时间来进行零元素的无效计算，显然是不可取的。一种较好的方法是：只考虑存储占元素中极少数的非零元素。
对于稀疏矩阵中的每个非零元素，可用它所在的行号、列号以及元素值这3个数据即三元组（i,j,aij）来表示。若把一个稀疏矩阵中的所有三元组依次按照行号为主序，列号为辅序进行升序排列，就构成了一个表示稀疏矩阵的三元组线性表，并且该表是按行、列号有序的。
稀疏矩阵采用三元组线性表表示后，可以使用顺序或链接方式存储，从而比采用二维数组存储要大大地节省存储空间和运算时间。
3、三元组的类型定义
在稀疏矩阵的三元组线性表中，每个元素为一个表示非0元素的三元组，它包括行号，列号和值，假定分别用标识符row,col和val表示，并假定用标识符Triple表示三元组类，则定义为：
public class Triple implements Comparable {
int row; //行号
int col; //列号
double val; //元素值
public Triple(int row, int col, double val) { //构造方法
super();
this.row = row;
this.col = col;
this.val = val;
}
public boolean equals(Object obj) { //定义比较两元素相同的方法
Triple t=(Triple)obj;
if((this.row==t.row)&&(this.col==t.col))
{
return true;
}
else
{
return false;
}
}
public String toString() { //三元组的字符串输出格式
return "("+row+","+col+","+val+")";
}
public int compareTo(Object obj) { //按列号比较两元素的大小
Triple t=(Triple)obj;
if(this.row>t.row)
{
return 1;
}
else if(this.row<t.row)
{
return -1;
}
else
{
//执行到此时必然是this.row==t.row 为真
if(this.col>t.col)
{
return 1;
}
else if(this.col<t.col)
{
return -1;
}
else
{
return 0;
}
}
}
}
4、稀疏矩阵的类型定义
在稀疏矩阵的类型中，其数据成员应当包括稀疏矩阵的总行数，总列数，以及一个存储非零元素的三元有序线性表，假定他们的标识符分别用rows,cols和terms表示；除数据成员外，还应当包含一些对矩阵运算的方法，如转置方法、矩阵相加方法、输出矩阵方法等。假定稀疏矩阵类型用SparseMatrix表示，下面给出它的具体定义：
注：SortedList类，sequenceSortedList类，List接口等来自线性表一文。
public class SparseMatrix {
//稀疏矩阵类的定义
private int rows; //稀疏矩阵的行数
private int cols; //稀疏矩阵的列数
private SortedList terms; //保存稀疏矩阵的三元组有序线性表
public SparseMatrix(int r,int c,List list)
{
rows=r;
cols=c;
terms=new SequenceSortedList(list); //利用线性表list构造有序表
}
//输出稀疏矩阵的行列数和三元组有序线性表表示
public void outputMatrix()
{
System.out.println("稀疏矩阵的行数和列数："+rows+","+cols);
terms.forward();
}
//转置
public SparseMatrix transpose()
{
//定义和创建一个转置矩阵B的独享sm,它的行数为矩阵A的列数，列数为当前矩阵A
//的行数，并用空的顺序或链接线性表初始化sm的三元组有序线性表
SparseMatrix sm=new SparseMatrix(cols,rows,new SequenceList());
//若当前矩阵是零矩阵（即非零元素的个数为0的矩阵），则转换完毕返回
if(terms.size()==0)
{
return sm;
}
//扫描当前矩阵中的三元组线性表中的每个元素，构成转置元素而插入到sm的表中
for(int i=1;i<=terms.size();i++) //用i扫描每个被转换的元素
{
Triple x=(Triple)terms.value(i); //读取一个三元组元素到x中
sm.terms.insert(new Triple(x.col,x.row,x.val));//按值插入新元素
}
//返回根据当前矩阵进行转置运算后而得到的转置矩阵
return sm;
}
//加法
public SparseMatrix sparseAdd(SparseMatrix sm)
{
//进行当前稀疏矩阵this和参数矩阵sm的加法运算，返回运算结果
//若两个矩阵尺寸不同，则给出错误信息并停止运行
if((rows!=sm.rows)||(rows!=sm.cols))
{
System.out.println("两个矩阵的尺寸不同，不能相加！");
System.exit(1);
}
//定义和创建一个保存运算结果的稀疏矩阵tm,它的行，列数与当前矩阵相同
//所采用的三元组线性表可以为顺序表，也可以外链接表
SparseMatrix tm=new SparseMatrix(cols,rows,new SequenceList());
//若两个矩阵均为零矩阵，则无须计算返回tm
if((terms.size()==0&&(sm.terms.size()==0)))
{
return tm;
}
//定义整型变量i1和i2，分别表示待扫描到的两个加数线性表中的元素序号
int i1=1,i2=1; //初始值为1，各自指示三元组线性表中的第1个元素
//当两个加数的三元组有序线性表同时不为空时的处理过程
while(i1<=this.terms.size()&&i2<=sm.terms.size())
{
Triple x1=(Triple)this.terms.value(i1); //取出this中的元素值到x1
Triple x2=(Triple)sm.terms.value(i2); //取出sm中的元素值到x2
if(x1.compareTo(x2)<0) //因x1较小，将x1插入到tm的有序表表尾
{
tm.terms.add(x1, tm.terms.size()+1);
i1++; //为扫描this中的下一个三元组元素做准备
}
else if(x1.compareTo(x2)>0) //因x2较小，将x2插入到tm的表尾
{
tm.terms.add(x2, tm.terms.size()+1);
i2++; //将扫描sm中的下一个元素
}
else //此时两个元素的行列相同若两值之和不为0则新元素插入表尾
{
double y=x1.val+x2.val;
if(Math.abs(y)>1.0E-6) //判定0条件为避免出现误差而采用
{
Triple x3=new Triple(x1.row,x1.col,y);
tm.terms.add(x3,tm.terms.size()+1);
}
i1++;
i2++; //两元素合并后，i1和i2均须后移
}
}
//将this中的剩余三元组元素依次插入到tm的三元组有序线性表的表尾
while(i1<=this.terms.size())
{
tm.terms.add(this.terms.value(i1), tm.terms.size()+1);
i1++;
}
//将sm中的剩余三元组元素依次插入到tm中的三元组有序线性表的表尾
while(i2<=sm.terms.size())
{
tm.terms.add(sm.terms.value(i2), tm.terms.size()+1);
i2++;
}
return tm; //返回this和sm的加运算的结果矩阵tm
}
}