三元矩阵模板
#include<bits/stdc++.h> #define MAXSIZE 12500 using namespace std; //row column//行 列 typedef struct { int i,j; int e; }Triple; typedef struct { Triple data[MAXSIZE]; int rpos[MAXSIZE]; int nr,nc,nm;//非零元行数列数和个数 }TSMatrix; int mr,mc,nr,nc; int** MM; int** NN; void init() { cin>>mr>>mc; MM=new int *[mr]; for(int i=0;i<mr;i++) { MM[i]=new int[mc]; for(int j=0;j<mc;j++) cin>>MM[i][j]; } cin>>nr>>nc; NN=new int *[nr]; for(int i=0;i<nr;i++) { NN[i]=new int[nc]; for(int j=0;j<nc;j++) cin>>NN[i][j]; } } void transformation(int** a,int r,int c,TSMatrix &M) { int p=0,flag=1; for(int i=0;i<r;i++) { flag=1; for(int j=0;j<c;j++) if(a[i][j]) { if(flag) { M.rpos[i]=p; flag=0; } M.data[p].i=i; M.data[p].j=j; M.data[p++].e=a[i][j]; } } M.nr=r; M.nc=c; M.nm=p; // for(int i=0;i<M.nm;i++) // cout<<M.data[i].i<<' '<<M.data[i].j<<' '<<M.data[i].e<<endl; } void get_Transpose_matrix(TSMatrix M,TSMatrix &T) { T.nr=M.nr; T.nc=M.nc; T.nm=M.nm; int p,q,col; int num[M.nc];//第i列的非零元个数 int cpot[M.nc];//第i列第一个非零元位置 if(T.nm) { for(col=0;col<M.nc;col++) num[col]=0; for(int i=0;i<M.nm;i++) num[M.data[i].j]++; cpot[0]=0; for(col=1;col<M.nm;col++) cpot[col]=cpot[col-1]+num[col-1]; for(p=0;p<M.nm;p++) { col=M.data[p].j; q=cpot[col];//位置 T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; cpot[col]++; } } // for(int i=0;i<T.nm;i++) // cout<<T.data[i].e<<' '; } bool matrix_multiplication(TSMatrix M,TSMatrix N,TSMatrix &Q) { for(int i=0;i<M.nm;i++) { cout<<M.data[i].i<<' '<<M.data[i].j<<' '<<M.data[i].e<<endl; } cout<<endl; for(int i=0;i<N.nm;i++) { cout<<N.data[i].i<<' '<<N.data[i].j<<' '<<N.data[i].e<<endl; } cout<<endl; //求矩阵乘积Q=M*N，采用行逻辑链接储存表示； if(M.nc!=N.nr) return false; Q.nm=0; Q.nr=M.nr; Q.nc=N.nc;//初始化 int temp[M.nr]={0}; int tp,t,brow,ccol; if(M.nm*N.nm!=0) { for(int arow=0;arow<M.nr;arow++) { memset(temp,0,sizeof(temp)); Q.rpos[arow]=Q.nm;//行arow起始位置 if(arow<M.nr-1) tp=M.rpos[arow+1];//结束位置 else tp=M.nm; for(int p=M.rpos[arow];p<tp;p++)//对当前航每一个非零元 { brow=M.data[p].j;//找到对应元在N中的行号； if(brow<N.nr-1) t=N.rpos[brow+1];//t同上tp else t=N.nm; for(int q=N.rpos[brow];q<t;q++) { ccol=N.data[q].j;//乘积元素在Q中的列号 temp[ccol]+=M.data[p].e*N.data[q].e; } }//求得Q中第crow行的非零元 for(ccol=0;ccol<Q.nc;ccol++)//压缩储存该行非零元 { if(temp[ccol]) { if(Q.nm > MAXSIZE) return false; Q.data[Q.nm].i=arow; Q.data[Q.nm].j=ccol; Q.data[Q.nm].e=temp[ccol]; Q.nm++; } } } } return true; } int main() { freopen("in.txt","r",stdin); TSMatrix M,N,T,Q; init();//输入 transformation(MM,mr,mc,M);//将普通矩阵MM转换成三元矩阵M transformation(NN,nr,nc,N);//将NN转换成N get_Transpose_matrix(M,T);//获得三元矩阵M的转置矩阵 matrix_multiplication(M,N,Q);//将矩阵M和N相乘保存到Q中 free(MM); free(NN); return 0; }