一 概述
1
2
3
| 1.稀疏矩阵的转置
2.稀疏矩阵快速转置
3.示例代码
|
二 稀疏矩阵的转置
2.1 概念
1
2
3
4
5
6
7
| 《稀疏矩阵的转置算法》一节介绍了实现矩阵转置的普通算法，该算法的时间复杂度为 O(n 2 )。
本节给大家介绍一种实现矩阵转置更高效的算法，通常称为稀疏矩阵的快速转置算法。
我们知道，稀疏矩阵的转置需要经历以下 3 步：
1. 将矩阵的行数和列数互换；
2. 将三元组表（存储矩阵）中的 i 列和 j 列互换，实现矩阵的转置；
3. 以 j 列为序，重新排列三元组表中存储各三元组的先后顺序；
|
2.2 图示
1
| 稀疏矩阵快速转置算法和普通算法的区别仅在于第 3 步，快速转置能够做到遍历一次三元组表即可完成第 3 步的工作。
|
三 稀疏矩阵快速转置
1
2
| 如图 1 所示，此为转置之前的矩阵和对应的三元组表。
稀疏矩阵的快速转置是这样的，在普通算法的基础上增设两个数组（假设分别为 array 和 copt）：
|
3.1 说明
一、对应的 array 数组
1
2
| array 数组负责记录原矩阵每一列非 0 元素的个数。以图 1 为例，则对应的 array 数组如图 2 所示：
图 2 中 array 数组表示，原稀疏矩阵中第一列有 1 个非 0 元素，第二列有 2 个非 0 元素。
|
二、 copt 数组
1
2
3
4
5
| copt 数组用于计算稀疏矩阵中每列第一个非 0 元素在新三元组表中存放的位置。
我们通常默认第一列首个非 0 元素存放到新三元组表中的位置为 1，然后通过 cpot[col] = cpot[col-1] + array[col-1]
公式可计算出后续各列首个非 0 元素存放到新三元组表的位置。
拿图 1 中的稀疏矩阵来说，它对应的 copt 数组如图 3 所示：
图 3 中的 copt 数组表示，原稀疏矩阵中第 2 列首个非 0 元素存放到新三元组表的位置为 2。
|
3.2 注意事项
1
2
3
| 注意，cpot[col] = cpot[col-1] + array[col-1] 的意思是，
后一列首个非 0 元素存放的位置等于前一列首个非 0 元素的存放位置加上该列非 0 元素的个数。
由此可以看出，copt 数组才是最终想要的，而 array 数组的设立只是为了帮助我们得到 copt 数组。
|
四 示例代码
4.1 示例代码
这样在实现第 3 步时，根据每个三元组中 j 的数值，可以借助 cpot 数组直接得到此三元组新的存放位置，C 语言实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| //实现快速转置算法的函数
TSMatrix fastTransposeMatrix(TSMatrix M,TSMatrix T) {
//第 1 步：行和列置换
T.m=M.n;
T.n=M.m;
T.num=M.num;
if (T.num) {
//计算 array 数组
int array[number];
for (int col=1; col<=M.m; col++) {
array[col]=0;
}
for (int t=0; t<M.num; t++) {
int j=M.data[t].j;
array[j]++;
}
//创建并初始化 cpot 数组
int cpot[T.m+1];
cpot[1]=1;//第一列中第一个非 0 元素的位置默认为 1
for (int col=2; col<=M.m; col++) {
cpot[col]=cpot[col-1]+array[col-1];
}
//遍历一次即可实现三元组表的转置
for (int p=0; p<M.num; p++) {
//提取当前三元组的列数
int col=M.data[p].j;
//根据列数和 cpot 数组，找到当前元素需要存放的位置
int q=cpot[col];
//转置矩阵的三元组默认从数组下标 0 开始，而得到的 q 值是单纯的位置，所以要减 1
T.data[q-1].i=M.data[p].j;
T.data[q-1].j=M.data[p].i;
T.data[q-1].data=M.data[p].data;
//存放完成后，cpot 数组对应的位置要+1，以便下次该列存储下一个三元组
cpot[col]++;
}
}
return T;
}
|
4.2 使用 fastTransposeMatrix 函数实现图 1 中稀疏矩阵转置的 C 语言完整程序为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<stdio.h>
#define number 10
typedef struct {
int i,j;
int data;
} triple;
typedef struct {
triple data[number];
int rpos[number];
int n,m,num;
} TSMatrix;
//fastTransposeMatrix 放置位置
int main() {
TSMatrix M;
M.m=2;
M.n=3;
M.num=3;
M.data[0].i=1;
M.data[0].j=2;
M.data[0].data=1;
M.data[1].i=2;
M.data[1].j=2;
M.data[1].data=3;
M.data[2].i=3;
M.data[2].j=1;
M.data[2].data=6;
TSMatrix T;
T=fastTransposeMatrix(M, T);
printf("转置矩阵三元组表为：\n");
for (int i=0; i<T.num; i++) {
printf("(%d,%d,%d)\n",T.data[i].i,T.data[i].j,T.data[i].data);
}
return 0;
}
|
程序运行结果为：
1
2
3
4
| 转置矩阵三元组表为：
(1,3,6)
(2,1,1)
(2,2,3)
|
可以看出，稀疏矩阵快速转置算法的时间复杂度为 O(n)。即使在最坏的情况下（矩阵中全部都是非 0 元素），该算法的时间复杂度也才为 O(n 2 )。
五 参考
- C语言中文网—稀疏矩阵的快速转置算法（C语言）详解