作者：解学武

一个 m*n 的矩阵 A，它的转置矩阵 B 是一个 n*m 的矩阵，且满足 a_ij = b_ji。如下图所示，矩阵 B 就是矩阵 A 的转置矩阵。
试编写一个程序，实现稀疏矩阵的转置，题目要求用三元组顺序表来表示。

实现思路

拿图 1 中的矩阵 A 和 B 来说，其各自用三元组顺序表表示（分别用 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 的数

方法一的具体实现（附有详细注释）

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

运行结果为：

方法二的具体实现（附有详细注释）

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

运行结果：
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。