欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

Java數(shù)據(jù)結(jié)構(gòu)之稀疏矩陣定義與用法示例

本文實(shí)例講述了Java數(shù)據(jù)結(jié)構(gòu)之稀疏矩陣定義與用法。分享給大家供大家參考，具體如下：

創(chuàng)新互聯(lián)是一家專(zhuān)業(yè)提供呼倫貝爾企業(yè)網(wǎng)站建設(shè),專(zhuān)注與網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、HTML5、小程序制作等業(yè)務(wù)。10年已為呼倫貝爾眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專(zhuān)業(yè)網(wǎng)站制作公司優(yōu)惠進(jìn)行中。

稀疏矩陣非零元素的三元組類(lèi):

package com.clarck.datastructure.matrix;
/**
 * 稀疏矩陣的壓縮存儲(chǔ)
 *
 * 稀疏矩陣非零元素的三元組類(lèi)
 *
 * @author clarck
 *
 */
public class Triple implements Comparable<Triple> {
  // 行號(hào)，列號(hào)， 元素值，默認(rèn)訪問(wèn)權(quán)限
  int row, colum, value;
  public Triple(int row, int colum, int value) {
    if (row < 0 || colum < 0) {
      throw new IllegalArgumentException("稀疏矩陣元素三元組的行/列序號(hào)非正數(shù)");
    }
    this.row = row;
    this.colum = colum;
    this.value = value;
  }
  /**
   * 拷貝構(gòu)造方法，復(fù)制一個(gè)三元組
   *
   * @param elem
   */
  public Triple(Triple elem) {
    this(elem.row, elem.colum, elem.value);
  }
  @Override
  public String toString() {
    return "(" + row + ", " + colum + ", " + value + ")";
  }
  /**
   * 兩個(gè)三元組是否相等，比較位置和元素值
   */
  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;
  }
  /**
   * 根據(jù)三元組位置比較兩個(gè)三元組的大小，與元素值無(wú)關(guān)，約定三元組排序次序
   */
  @Override
  public int compareTo(Triple elem) {
    //當(dāng)前三元組對(duì)象小
    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;
    //當(dāng)前三元組對(duì)象大
    return 1;
  }
  /**
   * 加法， +=運(yùn)算符作用
   * @param term
   */
  public void add(Triple term) {
    if (this.compareTo(term) == 0)
      this.value += term.value;
    else
      throw new IllegalArgumentException("兩項(xiàng)的指數(shù)不同，不能相加");
  }
  /**
   * 約定刪除元素
   *
   * @return
   */
  public boolean removable() {
    //不存儲(chǔ)為0的元素
    return this.value == 0;
  }
  /**
   * 返回對(duì)稱(chēng)位置矩陣元素的三元組
   * @return
   */
  public Triple toSymmetry() {
    return new Triple(this.colum, this.row, this.value);
  }
  /**
   * 加法運(yùn)算，重載運(yùn)算符+
   * @return
   */
  public Triple plus(Triple term) {
    Triple tmp = new Triple(this);
    tmp.add(term);
    return tmp;
  }
}

三元組順序存儲(chǔ)的稀疏矩陣類(lèi):

package com.clarck.datastructure.matrix;
import com.clarck.datastructure.linear.SeqList;
/**
 * 稀疏矩陣的壓縮存儲(chǔ)
 *
 * 稀疏矩陣三元組順序表
 *
 * 三元組順序存儲(chǔ)的稀疏矩陣類(lèi)
 *
 * @author clarck
 *
 */
public class SeqSparseMatrix {
  // 矩陣行數(shù)、列數(shù)
  private int rows, columns;
  // 稀疏矩陣三元組順序表
  private SeqList<Triple> list;
  /**
   * 構(gòu)造rows行，colums列零矩陣
   *
   * @param rows
   * @param columns
   */
  public SeqSparseMatrix(int rows, int columns) {
    if (rows <= 0 || columns <= 0)
      throw new IllegalArgumentException("矩陣行數(shù)或列數(shù)為非正數(shù)");
    this.rows = rows;
    this.columns = columns;
    // 構(gòu)造空順序表，執(zhí)行SeqList()構(gòu)造方法
    this.list = new SeqList<Triple>();
  }
  public SeqSparseMatrix(int rows, int columns, Triple[] elems) {
    this(rows, columns);
    // 按行主序插入一個(gè)元素的三元組
    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("矩陣元素的行或列序號(hào)越界");
    Triple item = new Triple(i, j, 0);
    int k = 0;
    Triple elem = this.list.get(k);
    // 在排序順序表list中順序查找item對(duì)象
    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;
  }
  /**
   * 以三元組設(shè)置矩陣元素
   *
   * @param elem
   */
  public void set(Triple elem) {
    this.set(elem.row, elem.colum, elem.value);
  }
  /**
   * 設(shè)置矩陣第row行第column列的元素值為value，按行主序在排序順序表list中更改或插入一個(gè)元素的三元組， O(n)
   *
   * @param row
   * @param column
   * @param value
   */
  public void set(int row, int column, int value) {
    // 不存儲(chǔ)值為0元素
    if (value == 0)
      return;
    if (row >= this.rows || column >= this.columns)
      throw new IllegalArgumentException("三元組的行或列序號(hào)越界");
    Triple elem = new Triple(row, column, value);
    int i = 0;
    // 在排序的三元組順序表中查找elem對(duì)象，或更改或插入
    while (i < this.list.length()) {
      Triple item = this.list.get(i);
      // 若elem存在，則更改改位置矩陣元素
      if (elem.compareTo(item) == 0) {
        // 設(shè)置順序表第i個(gè)元素為elem
        this.list.set(i, elem);
        return;
      }
      // elem 較大時(shí)向后走
      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個(gè)元素，若k指定序號(hào)無(wú)效則返回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;
  }
  /**
   * 返回當(dāng)前矩陣與smat相加的矩陣， smatc=this+smat,不改變當(dāng)前矩陣，算法同兩個(gè)多項(xiàng)式相加
   *
   * @param smat
   * @return
   */
  public SeqSparseMatrix plus(SeqSparseMatrix smat) {
    if (this.rows != smat.rows || this.columns != smat.columns)
      throw new IllegalArgumentException("兩個(gè)矩陣階數(shù)不同，不能相加");
    // 構(gòu)造rows*columns零矩陣
    SeqSparseMatrix smatc = new SeqSparseMatrix(this.rows, this.columns);
    int i = 0, j = 0;
    // 分別遍歷兩個(gè)矩陣的順序表
    while (i < this.list.length() && j < smat.list.length()) {
      Triple elema = this.list.get(i);
      Triple elemb = smat.list.get(j);
      // 若兩個(gè)三元組表示相同位置的矩陣元素，則對(duì)應(yīng)元素值相加
      if (elema.compareTo(elemb) == 0) {
        // 相加結(jié)果不為零，則新建元素
        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) { // 將較小三元組復(fù)制添加到smatc順序表最后
        // 復(fù)制elema元素執(zhí)行Triple拷貝構(gòu)造方法
        smatc.list.append(new Triple(elema));
        i++;
      } else {
        smatc.list.append(new Triple(elemb));
        j++;
      }
    }
    // 將當(dāng)前矩陣順序表的剩余三元組復(fù)制添加到smatc順序表最后
    while (i < this.list.length())
      smatc.list.append(new Triple(this.list.get(i++)));
    // 將smat中剩余三元組復(fù)制添加到smatc順序表最后
    while (j < smatc.list.length()) {
      Triple elem = smat.list.get(j++);
      if (elem != null) {
        smatc.list.append(new Triple(elem));
      }
    }
    return smatc;
  }
  /**
   * 當(dāng)前矩陣與smat矩陣相加，this+=smat, 改變當(dāng)前矩陣，算法同兩個(gè)多項(xiàng)式相加
   *
   * @param smat
   */
  public void add(SeqSparseMatrix smat) {
    if (this.rows != smat.rows || this.columns != smat.columns)
      throw new IllegalArgumentException("兩個(gè)矩陣階數(shù)不同，不能相加");
    int i = 0, j = 0;
    // 將mat的各三元組依次插入(或相加)到當(dāng)前矩陣三元組順序表中
    while (i < this.list.length() && j < smat.list.length()) {
      Triple elema = this.list.get(i);
      Triple elemb = smat.list.get(j);
      // 若兩個(gè)三元組表示相同位置的矩陣元素，則對(duì)應(yīng)元素值相加
      if (elema.compareTo(elemb) == 0) {
        // 相加結(jié)果不為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) { // 繼續(xù)向后尋找elemb元素的插入元素
        i++;
      } else {
        // 復(fù)制elemb元素插入作為this.list的第i個(gè)元素
        this.list.insert(i++, new Triple(elemb));
        j++;
      }
    }
    // 將mat中剩余三元組依次復(fù)制插入當(dāng)前矩陣三元組順序表中
    while (j < smat.list.length()) {
      this.list.append(new Triple(smat.list.get(j++)));
    }
  }
  // 深拷貝
  public SeqSparseMatrix(SeqSparseMatrix smat) {
    this(smat.rows, smat.columns);
    // 創(chuàng)建空順序表，默認(rèn)容量
    this.list = new SeqList<Triple>();
    // 復(fù)制smat中所有三元組對(duì)象
    for (int i = 0; i < smat.list.length(); i++)
      this.list.append(new Triple(smat.list.get(i)));
  }
  /**
   * 比較兩個(gè)矩陣是否相等
   */
  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);
  }
  /**
   * 返回轉(zhuǎn)置矩陣
   * @return
   */
  public SeqSparseMatrix transpose() {
    //構(gòu)造零矩陣，指定行數(shù)和列數(shù)
    SeqSparseMatrix trans = new SeqSparseMatrix(columns, rows);
    for (int i = 0; i < this.list.length(); i++) {
      //插入矩陣對(duì)稱(chēng)位置元素的三元組
      trans.set(this.list.get(i).toSymmetry());
    }
    return trans;
  }
}

測(cè)試類(lèi)：

package com.clarck.datastructure.matrix;
/**
 * 稀疏矩陣的壓縮存儲(chǔ)
 *
 * 稀疏矩陣三元組順序表
 *
 * 三元組順序表表示的稀疏矩陣及其加法運(yùn)算
 *
 * @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轉(zhuǎn)置" + smata.transpose().toString());
  }
}

運(yùn)行結(jié)果：

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轉(zhuǎn)置三元組順序表：((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

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

網(wǎng)頁(yè)標(biāo)題：Java數(shù)據(jù)結(jié)構(gòu)之稀疏矩陣定義與用法示例
本文網(wǎng)址：http://www.chinadenli.net/article34/igjese.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開(kāi)發(fā)、品牌網(wǎng)站制作、、用戶(hù)體驗(yàn)、靜態(tài)網(wǎng)站、網(wǎng)頁(yè)設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

網(wǎng)站建設(shè)網(wǎng)站維護(hù)公司