作者：解学武

矩阵的转置实际上就是将数据元素的行标和列标互换，即 T(i,j) = M(j,i) 。例如：
相应地，三元组表转变为： 总结矩阵的转置过程，共经历了三个步骤：

• 矩阵的行数 n 和列数 m 的值交换；
• 将三元组中的 i 和 j 调换；
• 转换之后的表同样按照行序（置换前的列序）为主序，进行排序；

矩阵转置的快速转置算法和普通转置算法，区别就在于实现第 3 步的方法不同，快速转置算法在普通算法的基础上，对遍历存储的过程做了改进。下面我们对快速转置算法做详细地讲解。 首先将每一列中非 0 元素的个数对应地存储在一个数组（数组名为 array）中。在此基础上，计算出每一列第一个元素存放在三元组表中的位置，存储在数组（数组名为 cpot ）中。
用图 2 中置换之前的表举例：

array 数组中的数据表示，第一列有一个非 0 元素，第二列中 3 个非0元素。
 

cpot 数组中的数据表示，第一列中第一个数据存储的位置默认是 1 ，第二列第一个非 0 元素存放的位置是 2。

在以上两个数组的基础上，当遍历表 a 的 j 列时，根据每个元素 j 列的数值，就可以判断出它在表 b 中的存放位置，整个三元组表只需要遍历一次，就能实现矩阵的转置。

实现代码：

#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;

TSMatrix fastTransposeMatrix(TSMatrix M,TSMatrix T){
    T.m=M.n;
    T.n=M.m;
    T.num=M.num;

    if (T.num) {
        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]++;
        }
        int cpot[T.m+1];
        cpot[1]=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;
            int q=cpot[col];
            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[col]++;
        }
    }
    return T;
}
int main() {
    TSMatrix M;
    M.m=2;
    M.n=3;
    M.num=4;
   
    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;
   
    M.data[3].i=3;
    M.data[3].j=2;
    M.data[3].data=5;
   
    TSMatrix T;
    T=fastTransposeMatrix(M, T);
    printf("使用改进方法：\n");
    for (int i=0; i<T.num; i++) {
        printf("(%d,%d,%d)",T.data[i].i,T.data[i].j,T.data[i].data);
    }
    return 0;
}

输出结果 这个算法中含有四个并列的单循环，时间复杂度为 O(m+num)(实际得到的是 O(2*m+2*num)，当 m 和 num 足够大时，可以省略常数参数)，即使最坏情况下，矩阵中的元素都是非 0 元素，时间负责度为O（m*n）。称此算法为快速转置算法。
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。