设稀疏矩阵M(m×n)中有t个非零元素,用三元组表的方式存储。设计一个算法并写出代码,计算矩阵M的转置矩阵N,且算法的时间复杂性为O(n+t)
时间: 2023-06-04 13:06:48 浏览: 285
好的,我可以帮你解决这个问题。以下是算法的伪代码:
1. 初始化一个t行3列的矩阵T,其中第i行表示第i个非零元素的行、列、和值。
2. 对矩阵T按列排序。
3. 初始化一个n行t列的矩阵N,矩阵中的每个元素都设为0。
4. 对于每个非零元素i,将其值填入矩阵N的第T(i,2)列第T(i,1)行。
算法的时间复杂度为O(n t)。以下是代码实现:
void matrixTranspose(int **M, int m, int n, int **&N, int &t) {
//1. 将稀疏矩阵M转化为三元组表存储
int **T = new int*[t];
for(int i=0; i<t; i++) {
T[i] = new int[3];
}
int k = 0;
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(M[i][j] != 0) {
T[k][0] = i;
T[k][1] = j;
T[k][2] = M[i][j];
k++;
}
}
}
//2. 按列排序
for(int i=0; i<3; i++) {
for(int j=0; j<t-1; j++) {
if(T[j][i] > T[j+1][i]) {
swap(T[j], T[j+1]);
}
}
}
//3. 计算矩阵N的大小
N = new int*[n];
for(int i=0; i<n; i++) {
N[i] = new int[t];
for(int j=0; j<t; j++) {
N[i][j] = 0;
}
}
//4. 计算矩阵N
for(int i=0; i<t; i++) {
N[T[i][1]][T[i][0]] = T[i][2];
}
//释放内存
for(int i=0; i<t; i++) {
delete [] T[i];
}
delete [] T;
}
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)