Java数据结构之稀疏矩阵定义与用法示例

本文实例讲述了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  0
b 三元组顺序表：((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 99
c=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 99
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 99
c.equals(a)?true
b 三元组顺序表：((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 99
d 三元组顺序表：((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 99
a转置三元组顺序表：((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程序设计有所帮助。