packagecom.clarck.datastructure.matrix;importcom.clarck.datastructure.linear.SeqList;/*** 稀疏矩阵的压缩存储
*
* 稀疏矩阵三元组顺序表
*
* 三元组顺序存储的稀疏矩阵类
*
*@authorclarck
**/
public classSeqSparseMatrix {//矩阵行数、列数
private introws, columns;//稀疏矩阵三元组顺序表
private SeqListlist;/*** 构造rows行，colums列零矩阵
*
*@paramrows
*@paramcolumns*/
public SeqSparseMatrix(int rows, intcolumns) {if (rows <= 0 || columns <= 0)throw new IllegalArgumentException("矩阵行数或列数为非正数");this.rows =rows;this.columns =columns;//构造空顺序表，执行SeqList()构造方法
this.list = new SeqList();
}public SeqSparseMatrix(int rows, intcolumns, Triple[] elems) {this(rows, columns);//按行主序插入一个元素的三元组
for (int i = 0; i < elems.length; i++)this.set(elems[i]);
}/*** 返回矩阵第i行第j列元素，排序顺序表的顺序查找算法，O(n)
*
*@parami
*@paramj
*@return
*/
public int get(int i, intj) {if (i < 0 || i >= rows || j < 0 || j >=columns)throw new IndexOutOfBoundsException("矩阵元素的行或列序号越界");
Triple item= new Triple(i, j, 0);int k = 0;
Triple elem= this.list.get(k);//在排序顺序表list中顺序查找item对象
while (k < this.list.length() && pareTo(elem) >= 0) {//只比较三元组元素位置，即elem.row == i && elem.column == j
if (pareTo(elem) == 0)returnelem.value;//查找到(i, j), 返回矩阵元素
k++;
elem= this.list.get(k);
}return 0;
}/*** 以三元组设置矩阵元素
*
*@paramelem*/
public voidset(Triple elem) {this.set(elem.row, elem.colum, elem.value);
}/*** 设置矩阵第row行第column列的元素值为value，按行主序在排序顺序表list中更改或插入一个元素的三元组， O(n)
*
*@paramrow
*@paramcolumn
*@paramvalue*/
public void set(int row, int column, intvalue) {//不存储值为0元素
if (value == 0)return;if (row >= this.rows || column >= this.columns)throw new IllegalArgumentException("三元组的行或列序号越界");
Triple elem= newTriple(row, column, value);int i = 0;//在排序的三元组顺序表中查找elem对象，或更改或插入
while (i < this.list.length()) {
Triple item= this.list.get(i);//若elem存在，则更改改位置矩阵元素
if (pareTo(item) == 0) {//设置顺序表第i个元素为elem
this.list.set(i, elem);return;
}//elem 较大时向后走
if (pareTo(item) >= 0)
i++;else
break;
}this.list.insert(i, elem);
}
@OverridepublicString toString() {
String str= "三元组顺序表：" + this.list.toString() + "\n";
str+= "稀疏矩阵" + this.getClass().getSimpleName() + "(" + rows + " * "
+ columns + "): \n";int k = 0;//返回第k个元素，若k指定序号无效则返回null
Triple elem = this.list.get(k++);for (int i = 0; i < this.rows; i++) {for (int j = 0; j < this.columns; j++)if (elem != null && i == elem.row && j ==elem.colum) {
str+= String.format("%4d", elem.value);
elem= this.list.get(k++);
}else{
str+= String.format("%4d", 0);
}
str+= "\n";
}returnstr;
}/*** 返回当前矩阵与smat相加的矩阵， smatc=this+smat,不改变当前矩阵，算法同两个多项式相加
*
*@paramsmat
*@return
*/
publicSeqSparseMatrix plus(SeqSparseMatrix smat) {if (this.rows != smat.rows || this.columns !=smat.columns)throw new IllegalArgumentException("两个矩阵阶数不同，不能相加");//构造rows*columns零矩阵
SeqSparseMatrix smatc = new SeqSparseMatrix(this.rows, this.columns);int i = 0, j = 0;//分别遍历两个矩阵的顺序表
while (i < this.list.length() && j
Triple elema= this.list.get(i);
Triple elemb=smat.list.get(j);//若两个三元组表示相同位置的矩阵元素，则对应元素值相加
if (pareTo(elemb) == 0) {//相加结果不为零，则新建元素
if (elema.value + elemb.value != 0)
smatc.list.append(newTriple(elema.row, elema.colum,
elema.value+elemb.value));
i++;
j++;
}else if (pareTo(elemb) < 0) { //将较小三元组复制添加到smatc顺序表最后//复制elema元素执行Triple拷贝构造方法
smatc.list.append(newTriple(elema));
i++;
}else{
smatc.list.append(newTriple(elemb));
j++;
}
}//将当前矩阵顺序表的剩余三元组复制添加到smatc顺序表最后
while (i < this.list.length())
smatc.list.append(new Triple(this.list.get(i++)));//将smat中剩余三元组复制添加到smatc顺序表最后
while (j
Triple elem= smat.list.get(j++);if (elem != null) {
smatc.list.append(newTriple(elem));
}
}returnsmatc;
}/*** 当前矩阵与smat矩阵相加，this+=smat, 改变当前矩阵，算法同两个多项式相加
*
*@paramsmat*/
public voidadd(SeqSparseMatrix smat) {if (this.rows != smat.rows || this.columns !=smat.columns)throw new IllegalArgumentException("两个矩阵阶数不同，不能相加");int i = 0, j = 0;//将mat的各三元组依次插入(或相加)到当前矩阵三元组顺序表中
while (i < this.list.length() && j
Triple elema= this.list.get(i);
Triple elemb=smat.list.get(j);//若两个三元组表示相同位置的矩阵元素，则对应元素值相加
if (pareTo(elemb) == 0) {//相加结果不为0,则新建元素
if (elema.value + elemb.value != 0)this.list.set(i++, newTriple(elema.row, elema.colum,
elema.value+elemb.value));else
this.list.remove(i);
j++;
}else if (pareTo(elemb) < 0) { //继续向后寻找elemb元素的插入元素
i++;
}else{//复制elemb元素插入作为this.list的第i个元素
this.list.insert(i++, newTriple(elemb));
j++;
}
}//将mat中剩余三元组依次复制插入当前矩阵三元组顺序表中
while (j
}
}//深拷贝
publicSeqSparseMatrix(SeqSparseMatrix smat) {this(smat.rows, smat.columns);//创建空顺序表，默认容量
this.list = new SeqList();//复制smat中所有三元组对象
for (int i = 0; i < smat.list.length(); i++)this.list.append(newTriple(smat.list.get(i)));
}/*** 比较两个矩阵是否相等*/
public booleanequals(Object obj) {if (this ==obj)return true;if (!(obj instanceofSeqSparseMatrix))return false;
SeqSparseMatrix smat=(SeqSparseMatrix) obj;return this.rows == smat.rows && this.columns ==smat.columns&& this.list.equals(smat.list);
}/*** 返回转置矩阵
*@return
*/
publicSeqSparseMatrix transpose() {//构造零矩阵，指定行数和列数
SeqSparseMatrix trans = newSeqSparseMatrix(columns, rows);for (int i = 0; i < this.list.length(); i++) {//插入矩阵对称位置元素的三元组
trans.set(this.list.get(i).toSymmetry());
}returntrans;
}
}
如果觉得《java 稀疏矩阵_数据结构学习----稀疏矩阵(Java实现)》对你有帮助，请点赞、收藏，并留下你的观点哦！
