稀疏矩阵的普通转置与快速转置

例题

输入

输入的第一行是两个整数r和c（r*c <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r行，每行有c个整数，表示这个稀疏矩阵的各个元素。

输出

输出c行，每行有r个整数，每个整数后跟一个空格。该结果为输入稀疏矩阵的转置矩阵。

样例输入

6 7
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0

样例输出

0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 0 14 0 0 0
0 0 0 0 0 0

一、普通转置解决

#include<cstring> #include<cstdio> #define M 100 typedef struct { int x; //非零元素行 int y; //非零元素列 int v; //非零元素本身的值 }node; //即非零元素所对应的三元组 typedef struct { int nu; //矩阵的行 int mu; //矩阵的列 int tu; //矩阵非零元素的个数 node data[2000]; }matrix; //整个矩阵的所有三元组所组成的结构 matrix A; matrix B; void trans_A() //矩阵转置 { B.mu=A.nu; B.nu=A.mu; B.tu=A.tu; if(B.tu>0) { int p=1; for(int j=1;j<=A.mu;j++) { for(int i=1;i<=A.tu;i++) { if(A.data[i].y==j) { B.data[p].x=A.data[i].y; B.data[p].y=A.data[i].x; B.data[p].v=A.data[i].v; p++; } } } } } int main() { int r,c; int num; int t=1; scanf("%d%d",&r,&c); A.mu=r; A.nu=c; A.tu=0; for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) { scanf("%d",&num); if(num!=0) //非零元素进三元表 { A.data[t].x=i; A.data[t].y=j; A.data[t].v=num; t++; A.tu++; } } } trans_A(); //矩阵转置 t=1; int sum=0; for(int i=1;i<=c;i++) { for(int j=1;j<=r;j++) { if(B.data[t].x==i&&B.data[t].y==j) { printf("%d ",B.data[t].v); t++; } else printf("0 "); sum++; if(sum%r==0) printf("\n"); } } return 0; }

二、快速转置

快速矩阵转置利用两个数组：
copt[n+1]：表示每列的第一个非零元素在三元组表的位置
num[n+1]：表示每列的非零元素的个数

其中：
copt[1]=1;
copt[i]=copt[i-1]+num[i-1] (i>=2）
于是代码实现：

#include<cstdio> #include<cstring> #include<cstdlib> #define M 500 typedef struct { int x; //非零元素行 int y; //非零元素列 int v; //非零元素本身的值 }node; //即非零元素所对应的三元组 typedef struct { int nu; //矩阵的行 int mu; //矩阵的列 int tu; //矩阵非零元素的个数 node data[2000]; //居然要这么大的数组，太粗心了 }matrix; //整个矩阵的所有三元组所组成的结构 matrix A; matrix B; int copt[M]; int num[M]; void trans_A() { B.mu=A.nu; B.nu=A.mu; B.tu=A.tu; if(B.tu>0) { for(int i=1; i<=A.mu; i++) num[i]=0; //num数组初始化 for(int i=1; i<=A.tu; i++) { int j=A.data[i].y; num[j]++; //计算每列的非零元素的值 } copt[1]=1; for(int i=2; i<=A.mu; i++) copt[i]=copt[i-1]+num[i-1]; //套用公式 for(int i=1; i<=A.tu; i++) //不难发现每行非零元素都是按列的大小从小到大排序 { int j=A.data[i].y; int k=copt[j]; B.data[k].x=A.data[i].y; B.data[k].y=A.data[i].x; B.data[k].v=A.data[i].v; copt[j]++; //该列第一个非零元素的位置+1 } } } int main() { int r,c; int t=1; int num; scanf("%d%d",&r,&c); A.nu=r; A.mu=c; A.tu=0; for(int i=1; i<=r; i++) { for(int j=1; j<=c; j++) { scanf("%d",&num); if(num!=0) { A.data[t].x=i; A.data[t].y=j; A.data[t].v=num; t++; A.tu++; } } } trans_A(); t=1; int sum=0; for(int i=1; i<=c; i++) { for(int j=1; j<=r; j++) { if(B.data[t].x==i&&B.data[t].y==j) { printf("%d ",B.data[t].v); t++; } else printf("0 "); sum++; if(sum%r==0) printf("\n"); } } return 0; }