阅读:0       作者:严长生

矩阵转置算法及代码实现(三元组顺序表)

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

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

实现三元组的转换,重点在第三步,实现算法有两种。

普通算法

普通算法的实现过程为:
  1. 将矩阵的行数和列数进行调换;
  2. 遍历表 a 的 j 列(查找 j 的值,从 1 一直到未转置之前的矩阵的列数 m ),遍历的过程,就可以自动存储为表 b 的形式。
因为在表 a 中 i 列的数值是从小到大的,在根据 j 列由上到下的遍历时, i 列同样也是有序的。
实现代码:
TSMatrix transposeMatrix(TSMatrix M,TSMatrix T){
    //行和列置换
    T.m=M.n;
    T.n=M.m;
    T.num=M.num;
   
    if (T.num) {
        int q=0;
        //依次遍历M矩阵的列(从1开始),的遍历的过程中将行标和列标置换,得到置换后的三元表T
        for (int col=1;col<=M.m; col++) {
            for (int p=0; p<M.num; p++) {
                if (M.data[p].j==col) {
                    T.data[q].i=M.data[p].j;
                    T.data[q].j=M.data[p].i;
                    T.data[q].data=M.data[p].data;
                    q++;
                }
            }
        }
    }
    return T;
}

此算法的时间复杂度关键在于嵌套的两个 for 循环,时间复杂度为O(m*num),和矩阵的列数以及非 0 元素的个数的乘积成正比,如果稀疏矩阵的非 0 元素很多的情况,使用这个算法,虽然一定程度上节省了空间,但是时间复杂度会很高。

快速转置算法

快速转置算法在普通算法的基础上,对遍历存储的过程做了改进。

首先将每一列中非 0 元素的个数对应地存储在一个数组(数组名为array)中。在此基础上,计算出每一列第一个元素存放在三元组表中的位置,存储在数组(数组名为 cpot )中。
第一列第一个非 0 元素肯定存放在第一个位置,第二列第一个非 0 元素的位置 = 第一列存放的起始位置 + 第一列的非 0 元素个数,以此类推。

用图 2 中置换之前的表举例:

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

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

计算方法是:cpot[col] = cpot[col-1] + array[col-1],即后边一列第一个非 0 元素存放的位置为前边一列第一个非 0 元素存放的位置加上该列非 0 元素的个数的和。
在以上两个数组的基础上,当遍历表 a 的 j 列时,根据每个元素 j 列的数值,就可以判断出它在表 b 中的存放位置,整个三元组表只需要遍历一次,就能实现矩阵的转置。

实现代码:
TSMatrix fastTransposeMatrix(TSMatrix M,TSMatrix T){
    //行和列置换
    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;
}
这个算法中含有四个并列的单循环,时间复杂度为O(m+num)(实际得到的是O(2*m+2*num),当 m 和 num 足够大时,可以省略常数参数),即使最坏情况下,矩阵中的元素都是非 0 元素,时间负责度为O(m*n)。称此算法为快速转置算法

两种算法的完整代码

#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 transposeMatrix(TSMatrix M,TSMatrix T){
    T.m=M.n;
    T.n=M.m;
    T.num=M.num;
   
    if (T.num) {
        int q=0;
        for (int col=1;col<=M.m; col++) {
            for (int p=0; p<M.num; p++) {
                if (M.data[p].j==col) {
                    T.data[q].i=M.data[p].j;
                    T.data[q].j=M.data[p].i;
                    T.data[q].data=M.data[p].data;
                    q++;
                }
            }
        }
    }
    return T;
}

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=transposeMatrix(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);
    }
    printf("\n");
    TSMatrix T1;
    T1=fastTransposeMatrix(M, T1);
    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;
}
输出结果
使用普通方法:
(1,3,6)(2,1,1)(2,2,3)(2,3,5)
使用改进方法:
(1,3,6)(2,1,1)(2,2,3)(2,3,5)