Java數(shù)據(jù)結(jié)構(gòu)之稀疏矩陣定義與用法示例
更新時(shí)間：2018年01月26日 11:25:22 作者：雪夜&流星
這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)之稀疏矩陣定義與用法,結(jié)合實(shí)例形式分析了java稀疏矩陣的定義、運(yùn)算、轉(zhuǎn)換等相關(guān)操作技巧,需要的朋友可以參考下
本文實(shí)例講述了Java數(shù)據(jù)結(jié)構(gòu)之稀疏矩陣定義與用法。分享給大家供大家參考，具體如下：
稀疏矩陣非零元素的三元組類:
package com.clarck.datastructure.matrix;
/**
* 稀疏矩陣的壓縮存儲
*
* 稀疏矩陣非零元素的三元組類
*
* @author clarck
*
*/
public class Triple implements Comparable<Triple> {
// 行號，列號， 元素值，默認(rèn)訪問權(quán)限
int row, colum, value;
public Triple(int row, int colum, int value) {
if (row < 0 || colum < 0) {
throw new IllegalArgumentException("稀疏矩陣元素三元組的行/列序號非正數(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è)三元組的大小，與元素值無關(guān)，約定三元組排序次序
*/
@Override
public int compareTo(Triple elem) {
//當(dāng)前三元組對象小
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)前三元組對象大
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() {
//不存儲為0的元素
return this.value == 0;
}
/**
* 返回對稱位置矩陣元素的三元組
* @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;
}
}
三元組順序存儲的稀疏矩陣類:
package com.clarck.datastructure.matrix;
import com.clarck.datastructure.linear.SeqList;
/**
* 稀疏矩陣的壓縮存儲
*
* 稀疏矩陣三元組順序表
*
* 三元組順序存儲的稀疏矩陣類
*
* @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("矩陣元素的行或列序號越界");
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;
}
/**
* 以三元組設(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) {
// 不存儲值為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) {
// 設(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指定序號無效則返回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è)三元組表示相同位置的矩陣元素，則對應(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è)三元組表示相同位置的矩陣元素，則對應(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中所有三元組對象
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++) {
//插入矩陣對稱位置元素的三元組
trans.set(this.list.get(i).toSymmetry());
}
return trans;
}
}
測試類：
package com.clarck.datastructure.matrix;
/**
* 稀疏矩陣的壓縮存儲
*
* 稀疏矩陣三元組順序表
*
* 三元組順序表表示的稀疏矩陣及其加法運(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)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設(shè)計(jì)有所幫助。
相關(guān)文章
這篇文章主要介紹了Spring實(shí)戰(zhàn)之清除緩存操作,結(jié)合實(shí)例形式詳細(xì)分析了spring清除緩存操作具體步驟、配置、領(lǐng)域模型及相關(guān)使用技巧,需要的朋友可以參考下2020-01-01
大家好，本篇文章主要講的是java方法重寫時(shí)需要注意的問題，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
SpringMVC中Controller類數(shù)據(jù)響應(yīng)的方法
這篇文章主要介紹了SpringMVC中的數(shù)據(jù)響應(yīng)的問題，主要來了解 Controller 類如何進(jìn)行數(shù)據(jù)響應(yīng)的，本文給大家介紹的非常詳細(xì)，需要的朋友可以參考下2021-07-07
Spring定時(shí)任務(wù)使用及如何使用郵件監(jiān)控服務(wù)器
這篇文章主要介紹了Spring定時(shí)任務(wù)使用及如何使用郵件監(jiān)控服務(wù)器,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07
spring boot整合jsp及設(shè)置啟動頁面的方法
這篇文章主要給大家介紹了關(guān)于spring boot整合jsp及設(shè)置啟動頁面的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用spring boot具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-09-09
這篇文章主要介紹了Spring?MVC請求處理流程和九大組件,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2023-12-12
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)俄羅斯方塊小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-06-06
Java如何使用httpclient檢測url狀態(tài)及鏈接是否能打開
這篇文章主要介紹了Java如何使用httpclient檢測url狀態(tài)及鏈接是否能打開，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
一篇文章帶你認(rèn)識Java8接口的默認(rèn)方法
這篇文章主要給大家介紹了如何通過一篇文章帶你認(rèn)識Java8接口的默認(rèn)方法的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Java8具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05
基于@RequestParam name和value屬性的區(qū)別
這篇文章主要介紹了@RequestParam name和value屬性的區(qū)別，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-08-08