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

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


相关介绍


稀疏矩阵即:由于矩阵大小较大,而大部分元素都是零,非零元素极少,于是稀疏矩阵采用三元组表存储

三元组的表示

typedef struct { int x; //非零元素行 int y; //非零元素列 int v; //非零元素本身的值 }node; //即非零元素所对应的三元组 typedef struct { int nu; //矩阵的行 int mu; //矩阵的列 int tu; //矩阵非零元素的个数 node data[2000]; }matrix; //整个矩阵的所有三元组所组成的结构 

例题


输入


输入的第一行是两个整数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; } 
全部评论

相关推荐

10-28 15:45
门头沟学院 C++
西南山:海康威视之前不是大规模裁员吗
点赞 评论 收藏
分享
点赞 评论 收藏
分享
我朋友的华子2012,HR已经开始问意向地区了,好急
不讲武德的黑眼圈很能干:急得不行 也不说评级 不知道报的多少啊😡
点赞 评论 收藏
分享
点赞 1 评论
分享
牛客网
牛客企业服务