稀疏矩陣基于“三元組”的轉置算法實作
一、定義“三元組”結構
/**
* 三元組元素類
* @author wcqx64
*
*/
public class Triple {
//行标
private int row;
//清單
private int col;
//數值
private int date;
public Triple() {
super();
}
public Triple(int row, int col, int date) {
super();
this.row = row;
this.col = col;
this.date = date;
}
public int getRow() {
return row;
}
public void setRow(int row) {
this.row = row;
}
public int getCol() {
return col;
}
public void setCol(int col) {
this.col = col;
}
public int getDate() {
return date;
}
public void setDate(int date) {
this.date = date;
}
}
import java.util.ArrayList;
import java.util.List;
/**
* 三元組結構
* @author wcqx64
*
*/
public class TSMatrix {
//非零元素 位置與數值資訊清單
List<Triple> tripleList=new ArrayList<>();
//矩陣行數
int row_num;
//矩陣列數
int col_num;
//非零元素個數
int count;
//構造函數
public TSMatrix(List<Triple> tripleList, int row_num, int col_num, int count) {
super();
this.tripleList = tripleList;
this.row_num = row_num;
this.col_num = col_num;
this.count = count;
}
public TSMatrix() {
super();
}
//getter與setter方法
public int getRow_num() {
return row_num;
}
public List<Triple> getTripleList() {
return tripleList;
}
public void setTripleList(List<Triple> tripleList) {
this.tripleList = tripleList;
}
public void setRow_num(int row_num) {
this.row_num = row_num;
}
public int getCol_num() {
return col_num;
}
public void setCol_num(int col_num) {
this.col_num = col_num;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
}
二、轉置操作實作類
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TransitionMatrix {
/**
* 初始化矩陣三元組結構
*
* @param a
* @return
*/
public static TSMatrix createSMatrix(int a[][]) {
// 定義三元組
TSMatrix tsmatrix = new TSMatrix();
List<Triple> tripleList = new ArrayList<>();
// 三元組初始化
for (int i = ; i < a.length; i++) {
for (int j = ; j < a[i].length; j++) {
if (a[i][j] != ) {
Triple triple = new Triple();
triple.setRow(i);
triple.setCol(j);
triple.setDate(a[i][j]);
tripleList.add(triple);
}
}
}
// 初始化行
tsmatrix.setRow_num(a.length);
// 初始化列
tsmatrix.setCol_num(a[].length);
// 非零元素個數
tsmatrix.setCount(tripleList.size());
tsmatrix.setTripleList(tripleList);
return tsmatrix;
}
/**
* 基于三元組存儲的矩陣“普通轉置算法”
* 利用三元組轉換矩陣 三步： 1、将矩陣行列值互換 2、将每個三元組中行列互調換
* 3、重排三元組之間的次序實作矩陣轉置 思想：按照原有矩陣的列序進行轉置。即掃描pre_Transposition三元組 進行轉置.
* 時間複雜度：O（col_num*count）矩陣列數與非零元素個數的乘積
*
* @param tsmatrix
* @return
*/
public static TSMatrix transposeSMtrix(TSMatrix pre_Transposition) {
// 轉置前三元組清單
List<Triple> pre_tripleList = new ArrayList<>();
// 轉置前三元組對象
pre_tripleList = pre_Transposition.getTripleList();
// 轉置後三元組清單
List<Triple> post_tripleList = new ArrayList<>();
// 轉置後三元組對象
TSMatrix post_Transposition = null;
// 按照原有矩陣列進行周遊
for (int i = ; i < pre_Transposition.getCol_num(); i++) {
// 掃描pre_Transposition三元組
// 2、将每個三元組中行列互調換
// 3、重排三元組之間的次序實作矩陣轉置
for (int j = ; j < pre_Transposition.getCount(); j++) {
if (pre_tripleList.get(j).getCol() == i) {
//實作轉置
Triple triple = new Triple(i, pre_tripleList.get(j).getRow(), pre_tripleList.get(j).getDate());
post_tripleList.add(triple);
}
}
}
// 1、矩陣行列數交換
post_Transposition = new TSMatrix(post_tripleList, pre_Transposition.getCol_num(),
pre_Transposition.getRow_num(), pre_Transposition.getCount());
return post_Transposition;
}
/**
* 基于三元組存儲的矩陣“快速轉置算法”
* 思想： 假設：在實作轉置之前，已經确定原有矩陣每一列的第一個非零元素在轉置後矩陣三元組的位置，
* 那麼在周遊原有矩陣三元組便可得到轉置後矩陣的三元組。将大大雖短時間複雜度。
* 是以在進行轉置之前，需要先确定原有矩陣每列非零元素的個數和每列第一個非零元素在轉置後矩陣三元組的位置。
* 設：cpot[col]為原有矩陣第col列第一個非零元素在轉置後三元組的位置； num[col] 為原有矩陣第col列中非零元素的個數；
* 則一定滿足： cpot[1]=1; cpot[col]=cpot[col-1]+num[col-1];
*
* @return
*/
public static TSMatrix fastTransposeSMtrix(TSMatrix pre_Transposition) {
// 轉置前三元組清單
List<Triple> pre_tripleList = new ArrayList<>();
// 轉置前三元組對象
pre_tripleList = pre_Transposition.getTripleList();
// 轉置後三元組清單
List<Triple> post_tripleList = new ArrayList<>();
Triple[] mild=new Triple[pre_tripleList.size()];
// 轉置後三元組對象
TSMatrix post_Transposition = null;
// 确定copt[]與num[]
int copt[] = new int[pre_Transposition.getCol_num()];
copt[] = ;
int num[] = new int[pre_Transposition.getCol_num()];
// 确定每列非零元素的個數
for (int i = ; i < pre_Transposition.getCount(); i++) {
num[pre_tripleList.get(i).getCol()]++;
}
// 确定每列第一個非零元素在轉置後三元組中的位置
for (int i = ; i < copt.length; i++) {
copt[i] = copt[i - ] + num[i - ];
}
Triple triple = new Triple();
for (int i = ; i < pre_Transposition.getCount(); i++) {
triple = pre_Transposition.getTripleList().get(i);
//獲得周遊的三元組元素在轉置後三元組的位置
int index = copt[triple.getCol()]-;
mild[index]=new Triple(triple.getCol(), triple.getRow(), triple.getDate());
//下一個位置
copt[triple.getCol()]++;
}
Collections.addAll(post_tripleList, mild);
post_Transposition = new TSMatrix(post_tripleList, pre_Transposition.getCol_num(),
pre_Transposition.getRow_num(), pre_Transposition.getCount());
return post_Transposition;
}
/**
* 列印三元組
*
* @param tsmatrix
*/
public static void display(TSMatrix tsmatrix) {
// 轉換前三元組
List<Triple> tripleList = tsmatrix.getTripleList();
System.out.print("row ");
System.out.print("col ");
System.out.println("value ");
for (int i = ; i < tripleList.size(); i++) {
System.out.print(tripleList.get(i).getRow() + " ");
System.out.print(tripleList.get(i).getCol() + " ");
System.out.println(tripleList.get(i).getDate() + " ");
}
}
}
三、測試類
public class SMtest {
public static void main(String[] args) {
int a[][] = { { 0, 12, 9, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0 }, { 3, 0, 0, 0, 0, 14, 0 },
{ 0, 0, 24, 0, 0, 0, 0 }, { 0, 18, 0, 0, 0, 0, 0 }, { 15, 0, 0, 7, 0, 0, 0 } };
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
System.out.print(a[i][j]+" ");
}
System.out.println();
}
// 初始化矩陣 三元組
System.out.println("初始化矩陣 三元組");
TSMatrix tsmatrix_original = TransitionMatrix.createSMatrix(a);
TransitionMatrix.display(tsmatrix_original);
// 基于三元組存儲的矩陣“普通轉置算法”
System.out.println("基于三元組存儲的矩陣“普通轉置算法”");
TSMatrix post_Transposition1 = TransitionMatrix.transposeSMtrix(tsmatrix_original);
TransitionMatrix.display(post_Transposition1);
//基于三元組存儲的矩陣“快速轉置算法”
System.out.println("基于三元組存儲的矩陣“快速轉置算法” ");
TSMatrix post_Transposition2=TransitionMatrix.fastTransposeSMtrix(tsmatrix_original);
TransitionMatrix.display(post_Transposition2);
}
}
四、測試結果
0 12 9 0 0 0 0
0 0 0 0 0 0 0
3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 7 0 0 0
初始化矩陣 三元組
row col value
0 1 12
0 2 9
2 0 3
2 5 14
3 2 24
4 1 18
5 0 15
5 3 7
基于三元組存儲的矩陣“普通轉置算法”
row col value
0 2 3
0 5 15
1 0 12
1 4 18
2 0 9
2 3 24
3 5 7
5 2 14
基于三元組存儲的矩陣“快速轉置算法”
row col value
0 2 3
0 5 15
1 0 12
1 4 18
2 0 9
2 3 24
3 5 7
5 2 14
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)