首页 > 代码库 > 矩阵倒置

矩阵倒置

文字描述

 

倒置:把矩阵A的行换成相应的列,得到的新矩阵称为A的转置矩阵,记作AT或A。

 

通常矩阵的第一列作为转置矩阵的第一行,第一行作为转置矩阵的第一列。

 

那么,在已经存储好的三元组的顺序存储结构中,如果如何实现矩阵的倒置呢???

 

第一反应肯定是直接遍历,然后行列对换即可,但是因为要求按照行号优先(也可以是列号优先,但是必须倒置前和倒置后都按照一种优先的方式排列),所以如果直接对换,那么就会变得没有顺序,还需要一次排序,这样反而不妙。

 

 

1、正常倒置

 

既然要进行行列对换,那么对换后的行号就是对换前的列号,因此可以多次扫描列号,

从列号小的开始扫描对换,那么进行对换后一定能够满足行号优先

 

2、快速倒置

 

很显然对于正常的倒置来说,要多次扫描整个存储空间,浪费大量的时间,因此可以对其进行优化

 

我们可以首先记录每一列(倒置后就是行)有多少元素,然后预留出空间

 

然后一遍扫描直接将其元素放入合适的预留位置即可

 

 

 

代码实现

 

 

1、正常倒置

/** 
* @Stone6762 
*/ 
public SparseArray transpose() { 
SparseArray tm = new SparseArray(nums);// 创建一个转置后的矩阵对象 
tm.cols = rows;// 行列变化,非零个数不变 
tm.rows = cols; 
tm.nums = nums; 
int q = 0; 
// 从小到大扫描列号,然后进行变化 
for (int col = 0; col < cols; col++) { 
for (int p = 0; p < nums; p++) { 
if (data[p].getColumn() == col) { 
tm.data[q].setColumn(data[p].getRow()); 
tm.data[q].setRow(data[p].getColumn()); 
tm.data[q].setValue(data[p].getValue()); 
q++; 



return tm; 
}

2、快速倒置

/** 
* @Stone6762 
*/ 
public SparseArray fastTranspose() { 
/* 
* 首先将位置进行预留,然后再“填空”。 num [cols];每一个“空”的大小 。 
copt[cols];每一个“空”的起始位置 
*/ 
SparseArray tm = new SparseArray(nums);// 创建一个转置后的对象 
tm.cols = rows;// 行列变化,非零元素个数不变 
tm.rows = cols; 
tm.nums = nums; 
int tCol = 0, indexOfC = 0; 
if (nums > 0) { 
int[] num = new int[cols];// 原始矩阵中第Col列的非零元素的个数 
int[] copt = new int[cols];// 初始值为N中的第col列的第一个非零元素在TM中的位置 
// 初始化num和copt数组 
for (int i = 0; i < nums; i++) { 
tCol = data[i].getColumn(); 
num[tCol]++; 

copt[0] = 0; 
for (int i = 1; i < cols; i++) { 
copt[i] = copt[i - 1] + num[i - 1]; 

// 找到每一个元素在转置后的三元组中的位置 
for (int i = 0; i < nums; i++) { 
tCol = data[i].getColumn();// 取得扫描TN中的第i个元素的列值tCol 
indexOfC = copt[tCol];// 取得该tCol列的下一个元素应该存储的位置 
tm.data[indexOfC].setRow(data[i].getColumn()); 
tm.data[indexOfC].setColumn(data[i].getRow()); 
tm.data[indexOfC].setValue(data[i].getValue()); 
copt[tCol]++;// 此时的copt[col]表示的是下一个该 col列元素会存储的位置 


return tm; 
}

 

矩阵倒置