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