本文实例讲述了Java数据结构之稀疏矩阵定义与用法。分享给大家供大家参考，具体如下：
稀疏矩阵非零元素的三元组类:
package com.clarck.datastructure.matrix;/** * 稀疏矩阵的压缩存储 * * 稀疏矩阵非零元素的三元组类 * * @author clarck * */public class Triple implements Comparable<Triple> { // 行号，列号， 元素值，默认访问权限 int row, colum, value; public Triple(int row, int colum, int value) { if (row < 0 || colum < 0) { throw new IllegalArgumentException("稀疏矩阵元素三元组的行/列序号非正数"); } this.row = row; this.colum = colum; this.value = value; } /** * 拷贝构造方法，复制一个三元组 * * @param elem */ public Triple(Triple elem) { this(elem.row, elem.colum, elem.value); } @Override public String toString() { return "(" + row + ", " + colum + ", " + value + ")"; } /** * 两个三元组是否相等，比较位置和元素值 */ public boolean equals(Object obj) { if (!(obj instanceof Triple)) return false; Triple elem = (Triple) obj; return this.row == elem.row && this.colum == elem.colum && this.value == elem.value; } /** * 根据三元组位置比较两个三元组的大小，与元素值无关，约定三元组排序次序 */ @Override public int compareTo(Triple elem) { //当前三元组对象小 if (this.row < elem.row || this.row == elem.row && this.colum < elem.colum) return -1; //相等，与equals方法含义不同 if (this.row == elem.row && this.colum == elem.colum) return 0; //当前三元组对象大 return 1; } /** * 加法， +=运算符作用 * @param term */ public void add(Triple term) { if (this.compareTo(term) == 0) this.value += term.value; else throw new IllegalArgumentException("两项的指数不同，不能相加"); } /** * 约定删除元素 * * @return */ public boolean removable() { //不存储为0的元素 return this.value == 0; } /** * 返回对称位置矩阵元素的三元组 * @return */ public Triple toSymmetry() { return new Triple(this.colum, this.row, this.value); } /** * 加法运算，重载运算符+ * @return */ public Triple plus(Triple term) { Triple tmp = new Triple(this); tmp.add(term); return tmp; }}三元组顺序存储的稀疏矩阵类:
package com.clarck.datastructure.matrix;import com.clarck.datastructure.linear.SeqList;/** * 稀疏矩阵的压缩存储 * * 稀疏矩阵三元组顺序表 * * 三元组顺序存储的稀疏矩阵类 * * @author clarck * */public class SeqSparseMatrix { // 矩阵行数、列数 private int rows, columns; // 稀疏矩阵三元组顺序表 private SeqList<Triple> list; /** * 构造rows行，colums列零矩阵 * * @param rows * @param columns */ public SeqSparseMatrix(int rows, int columns) { if (rows <= 0 || columns <= 0) throw new IllegalArgumentException("矩阵行数或列数为非正数"); this.rows = rows; this.columns = columns; // 构造空顺序表，执行SeqList()构造方法 this.list = new SeqList<Triple>(); } public SeqSparseMatrix(int rows, int columns, Triple[] elems) { this(rows, columns); // 按行主序插入一个元素的三元组 for (int i = 0; i < elems.length; i++) this.set(elems[i]); } /** * 返回矩阵第i行第j列元素，排序顺序表的顺序查找算法，O(n) * * @param i * @param j * @return */ public int get(int i, int j) { 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() && item.compareTo(elem) >= 0) { // 只比较三元组元素位置，即elem.row == i && elem.column == j if (item.compareTo(elem) == 0) return elem.value; // 查找到(i, j), 返回矩阵元素 k++; elem = this.list.get(k); } return 0; } /** * 以三元组设置矩阵元素 * * @param elem */ public void set(Triple elem) { this.set(elem.row, elem.colum, elem.value); } /** * 设置矩阵第row行第column列的元素值为value，按行主序在排序顺序表list中更改或插入一个元素的三元组， O(n) * * @param row * @param column * @param value */ public void set(int row, int column, int value) { // 不存储值为0元素 if (value == 0) return; if (row >= this.rows || column >= this.columns) throw new IllegalArgumentException("三元组的行或列序号越界"); Triple elem = new Triple(row, column, value); int i = 0; // 在排序的三元组顺序表中查找elem对象，或更改或插入 while (i < this.list.length()) { Triple item = this.list.get(i); // 若elem存在，则更改改位置矩阵元素 if (elem.compareTo(item) == 0) { // 设置顺序表第i个元素为elem this.list.set(i, elem); return; } // elem 较大时向后走 if (elem.compareTo(item) >= 0) i++; else break; } this.list.insert(i, elem); } @Override public String 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"; } return str; } /** * 返回当前矩阵与smat相加的矩阵， smatc=this+smat,不改变当前矩阵，算法同两个多项式相加 * * @param smat * @return */ public SeqSparseMatrix 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 < smat.list.length()) { Triple elema = this.list.get(i); Triple elemb = smat.list.get(j); // 若两个三元组表示相同位置的矩阵元素，则对应元素值相加 if (elema.compareTo(elemb) == 0) { // 相加结果不为零，则新建元素 if (elema.value + elemb.value != 0) smatc.list.append(new Triple(elema.row, elema.colum, elema.value + elemb.value)); i++; j++; } else if (elema.compareTo(elemb) < 0) { // 将较小三元组复制添加到smatc顺序表最后 // 复制elema元素执行Triple拷贝构造方法 smatc.list.append(new Triple(elema)); i++; } else { smatc.list.append(new Triple(elemb)); j++; } } // 将当前矩阵顺序表的剩余三元组复制添加到smatc顺序表最后 while (i < this.list.length()) smatc.list.append(new Triple(this.list.get(i++))); // 将smat中剩余三元组复制添加到smatc顺序表最后 while (j < smatc.list.length()) { Triple elem = smat.list.get(j++); if (elem != null) { smatc.list.append(new Triple(elem)); } } return smatc; } /** * 当前矩阵与smat矩阵相加，this+=smat, 改变当前矩阵，算法同两个多项式相加 * * @param smat */ public void add(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 < smat.list.length()) { Triple elema = this.list.get(i); Triple elemb = smat.list.get(j); // 若两个三元组表示相同位置的矩阵元素，则对应元素值相加 if (elema.compareTo(elemb) == 0) { // 相加结果不为0,则新建元素 if (elema.value + elemb.value != 0) this.list.set(i++, new Triple(elema.row, elema.colum, elema.value + elemb.value)); else this.list.remove(i); j++; } else if (elema.compareTo(elemb) < 0) { // 继续向后寻找elemb元素的插入元素 i++; } else { // 复制elemb元素插入作为this.list的第i个元素 this.list.insert(i++, new Triple(elemb)); j++; } } // 将mat中剩余三元组依次复制插入当前矩阵三元组顺序表中 while (j < smat.list.length()) { this.list.append(new Triple(smat.list.get(j++))); } } // 深拷贝 public SeqSparseMatrix(SeqSparseMatrix smat) { this(smat.rows, smat.columns); // 创建空顺序表，默认容量 this.list = new SeqList<Triple>(); // 复制smat中所有三元组对象 for (int i = 0; i < smat.list.length(); i++) this.list.append(new Triple(smat.list.get(i))); } /** * 比较两个矩阵是否相等 */ public boolean equals(Object obj) { if (this == obj) return true; if (!(obj instanceof SeqSparseMatrix)) return false; SeqSparseMatrix smat = (SeqSparseMatrix) obj; return this.rows == smat.rows && this.columns == smat.columns && this.list.equals(smat.list); } /** * 返回转置矩阵 * @return */ public SeqSparseMatrix transpose() { //构造零矩阵，指定行数和列数 SeqSparseMatrix trans = new SeqSparseMatrix(columns, rows); for (int i = 0; i < this.list.length(); i++) { //插入矩阵对称位置元素的三元组 trans.set(this.list.get(i).toSymmetry()); } return trans; }}测试类：
package com.clarck.datastructure.matrix;/** * 稀疏矩阵的压缩存储 * * 稀疏矩阵三元组顺序表 * * 三元组顺序表表示的稀疏矩阵及其加法运算 * * @author clarck * */public class SeqSparseMatrix_test { public static void main(String args[]) { Triple[] elemsa = { new Triple(0, 2, 11), new Triple(0, 4, 17), new Triple(1, 1, 20), new Triple(3, 0, 19), new Triple(3, 5, 28), new Triple(4, 4, 50) }; SeqSparseMatrix smata = new SeqSparseMatrix(5, 6, elemsa); System.out.print("A " + smata.toString()); Triple[] elemsb = { new Triple(0, 2, -11), new Triple(0, 4, -17), new Triple(2, 3, 51), new Triple(3, 0, 10), new Triple(4, 5, 99), new Triple(1, 1, 0) }; SeqSparseMatrix smatb = new SeqSparseMatrix(5,6,elemsb); System.out.print("B " + smatb.toString()); SeqSparseMatrix smatc = smata.plus(smatb); System.out.print("C=A+B"+smatc.toString()); System.out.println(); smata.add(smatb); System.out.print("A+=B" + smata.toString()); System.out.println("C.equals(A)?" + smatc.equals(smata)); SeqSparseMatrix smatd = new SeqSparseMatrix(smatb); smatb.set(0,2,1); System.out.print("B " + smatb.toString()); System.out.print("D " + smatd.toString()); System.out.println("A转置" + smata.transpose().toString()); }}运行结果：
A 三元组顺序表：((0, 2, 11), (0, 4, 17), (1, 1, 20), (3, 0, 19), (3, 5, 28), (4, 4, 50))稀疏矩阵SeqSparseMatrix(5 * 6): 0 0 11 0 17 0 0 20 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 28 0 0 0 0 50 0B 三元组顺序表：((0, 2, -11), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))稀疏矩阵SeqSparseMatrix(5 * 6): 0 0 -11 0 -17 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99C=A+B三元组顺序表：((1, 1, 20), (2, 3, 51), (3, 0, 29), (3, 5, 28), (4, 4, 50), (4, 5, 99))稀疏矩阵SeqSparseMatrix(5 * 6): 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99A+=B三元组顺序表：((1, 1, 20), (2, 3, 51), (3, 0, 29), (3, 5, 28), (4, 4, 50), (4, 5, 99))稀疏矩阵SeqSparseMatrix(5 * 6): 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99C.equals(A)?trueB 三元组顺序表：((0, 2, 1), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))稀疏矩阵SeqSparseMatrix(5 * 6): 0 0 1 0 -17 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99D 三元组顺序表：((0, 2, -11), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))稀疏矩阵SeqSparseMatrix(5 * 6): 0 0 -11 0 -17 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99A转置三元组顺序表：((0, 3, 29), (1, 1, 20), (3, 2, 51), (4, 4, 50), (5, 3, 28), (5, 4, 99))稀疏矩阵SeqSparseMatrix(6 * 5): 0 0 0 29 0 0 20 0 0 0 0 0 0 0 0 0 0 51 0 0 0 0 0 0 50 0 0 0 28 99
更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。