阅读:0       作者:严长生

稀疏矩阵的转置算法详解(带源码+解析)

一个 m*n 的矩阵 A,它的转置矩阵 B 是一个 n*m 的矩阵,且满足 aij = bji。如下图所示,矩阵 B 就是矩阵 A 的转置矩阵。


图 1 稀疏矩阵的转置

试编写一个程序,实现稀疏矩阵的转置,题目要求用三元组顺序表来表示。

实现思路

拿图 1 中的矩阵 A 和 B 来说,其各自用三元组顺序表表示(分别用 a 和b 表示),如下图所示:


图2 矩阵 A、B的三元组顺序表

在三元组表的存储形式下,求稀疏矩阵 A 的转置矩阵 B ,实际上就是求由 a 得到 b:
  • 由 a 的行数、列数以及非 0 元素数可以直接得到 b 的列数、行数和非 0 元素数。
  • 由 a 中的数据得到 b 中的数据,可采用两种方法实现:
  1. 对 a 中的数据进行遍历,即依次扫描第 0 列、第 1 列、……、最后一列,扫描过程交换行和列的顺序,并存储到 b 中对应的位置即可。
  2. 要想扫描一次 a 就能得到 b,必须每次扫描到一个三元组就直接将其放到 b 中相应的位置上,因此,需要知道 a 中的元素在 b 中的存储位置,这就要预先确定矩阵 A 的每一列的第一个非 0 元素在 b 中相应的位置。为此,需要附设两个数组,num 和cpot,分别用于存储矩阵 A 中每一列的非 0 元素个数和矩阵 A 中每一列第 1 个非0 元素在 b 中的存储位置。

显然,有如下的公式成立:
  • cpot[0] = 1
  • cpot[col] = cpot[col - 1] + num[col -1],col 取大于等于 1 且小于 n 的数

所以,图 1 中的矩阵 A ,其 num 和 cpot 数组的值为:

方法一的具体实现(附有详细注释)

#include <stdio.h>
#define MAXSIZE 50
#define MAXRC 10
//三元组结构体
typedef struct{
    //所在行数,列数
    int i,j;
    //值
    int e;
}triple;
//存储矩阵的三元组顺序表
typedef struct{
    //存储数据
    triple data[MAXSIZE + 1];
    //存储矩阵的行数,列数和非 0 元的个数
    int mu,nu,tu;
}TSMatrix;
//初始化三元组顺序表
TSMatrix tcreate(int m,int n,int t){
    TSMatrix M;
    int k;
    M.mu = m;
    M.nu = n;
    M.tu = t;
    printf("input %d data",M.tu);
    printf("i j e ");
    for(k=1;k<=M.tu;k++){
        scanf("%d%d%d",&M.data[k].i,&M.data[k].j,&M.data[k].e);
    }
    return M;
}
//输出矩阵 M 的函数,以二维的格式呈现
void printt(TSMatrix M){
    int i,j,k=1;
    //输出矩阵的每一行
    for(i=0;i<M.mu;i++){
        printf("\n");
        //输出矩阵的每一列
        for(j=0;j<M.nu;j++){
            //判断矩阵中是否有非 0 元存在
            if(k>M.tu){
                printf("%3d",0);
            }
            else{
                //如果对应位置为非 0 元,则输出
                if((i==M.data[k].i) && (j == M.data[k].j)){
                    printf("%3d",M.data[k].e);
                    k++;
                }else{
                    //否输出 0
                    printf("%3d",0);
                }
            }
        }
    }
    printf("\n");
}
//矩阵的转置函数
TSMatrix transpose(TSMatrix a){
    TSMatrix b;
    int col,p,q;
    //将矩阵 a 存储的行数、列数和非0 元个数赋值给转置矩阵 b
    b.mu=a.nu;
    b.nu=a.mu;
    b.tu=a.tu;
    //如果存在非 0 元,则逐个对其进行转置
    if(b.tu){
        q = 1;
        //从列依次遍历
        for(col=0;col<a.nu;col++){
            for(p=1;p<=a.tu;p++){
                if(a.data[p].j == col){
                    b.data[q].i=a.data[p].j;
                    b.data[q].j=a.data[p].i;
                    b.data[q].e=a.data[p].e;
                    q++;
                }
            }
        }
    }
    return b;
}
int main(){
    int m,n,t;
    TSMatrix E,F;
    printf("input m,n,t:\n");
    scanf("%d%d%d",&m,&n,&t);
    E = tcreate(m,n,t);
    printt(E);
    F = transpose(E);
    printt(F);
}
运行结果为:
input m,n,t:
3 5 6
input 6 datai j e
0 1 5
0 4 7
1 0 1
1 1 5
1 2 3
2 1 6

  0  5  0  0  7
  1  5  3  0  0
  0  6  0  0  0

  0  1  0
  5  5  6
  0  3  0
  0  0  0
  7  0  0

方法二的具体实现(附有详细注释)

#include <stdio.h>
#define MAXSIZE 50
#define MAXRC 10
//三元组结构体
typedef struct{
    //所在行数,列数
    int i,j;
    //值
    int e;
}triple;
//存储矩阵的三元组顺序表
typedef struct{
    //存储数据
    triple data[MAXSIZE + 1];
    //存储矩阵的行数,列数和非 0 元的个数
    int mu,nu,tu;
}TSMatrix;
//初始化三元组顺序表
TSMatrix tcreate(int m,int n,int t){
    TSMatrix M;
    int k;
    M.mu = m;
    M.nu = n;
    M.tu = t;
    printf("input %d data",M.tu);
    printf("i j e \n");
    for(k=1;k<=M.tu;k++){
        scanf("%d%d%d",&M.data[k].i,&M.data[k].j,&M.data[k].e);
    }
    return M;
}
//输出矩阵 M 的函数,以二维的格式呈现
void printt(TSMatrix M){
    int i,j,k=1;
    //输出矩阵的每一行
    for(i=0;i<M.mu;i++){
        printf("\n");
        //输出矩阵的每一列
        for(j=0;j<M.nu;j++){
            //判断矩阵中是否有非 0 元存在
            if(k>M.tu){
                printf("%3d",0);
            }
            else{
                //如果对应位置为非 0 元,则输出
                if((i==M.data[k].i) && (j == M.data[k].j)){
                    printf("%3d",M.data[k].e);
                    k++;
                }else{
                    //否输出 0
                    printf("%3d",0);
                }
            }
        }
    }
    printf("\n");
}
//矩阵的转置函数
TSMatrix fasttrans(TSMatrix a){
    TSMatrix b;
    int col,p,q,t;
    int num[MAXSIZE];
    int cpot[MAXSIZE];
    //转置行数、列数和非 0 元个数
    b.mu = a.nu;
    b.nu = a.mu;
    b.tu = a.tu;
    //如果存在非 0 元
    if(b.tu){
        //num数组全置为 0
        for(col = 0;col<a.nu;col++){
            num[col] = 0;
        }
        //根据矩阵 a ,对num数组进行初始化
        for(t=1;t<=a.tu;t++){
            num[a.data[t].j]++;
        }
        //初始化cpot数组
        cpot[0]=1;
        for(col=1;col<a.nu;col++){
            cpot[col] = cpot[col-1]+num[col-1];
        }
        //结束num和cpot,对矩阵 a 进行转置
        for(p=1;p<=a.tu;p++){
            col =a.data[p].j;
            q = cpot[col];
            b.data[q].i = a.data[p].j;
            b.data[q].j = a.data[p].i;
            b.data[q].e = a.data[p].e;
            cpot[col]++;
        }
    }
    return b;
}
int main(){
    int m,n,t;
    TSMatrix E,F;
    printf("input m,n,t:\n");
    scanf("%d%d%d",&m,&n,&t);
    E = tcreate(m,n,t);
    printt(E);
    F = fasttrans(E);
    printt(F);
}
运行结果:
input m,n,t:
3 5 6
input 6 datai j e
0 1 5
0 4 7
1 0 1
1 1 5
1 2 3
2 1 6

  0  5  0  0  7
  1  5  3  0  0
  0  6  0  0  0

  0  1  0
  5  5  6
  0  3  0
  0  0  0
  7  0  0