稀疏矩阵存储和转置及乘法 c++源代码 原创

#include <iostream> using namespace std; #define MAXSIZE 10 #define MAXMN 10 #define ElemType int typedef struct { int i, j; //该非零元的行下标和列下标 ElemType e; // 该非零元的值 } Triple; // 三元组类型 typedef struct { Triple data[MAXSIZE + 1]; int mu, nu, tu; } Matrix; // 稀疏矩阵类型1 typedef struct { Triple data[MAXSIZE + 1]; int rpos[MAXMN+1]; int mu, nu, tu; } MMatrix; // 稀疏矩阵类型2 bool FastTransposeSMatrix(Matrix M, Matrix &T);//稀疏矩阵转置函数 bool MultSMatrix(MMatrix M, MMatrix N, MMatrix &Q) ;//稀疏矩阵乘法函数 int main() { cout<<"/***************稀疏矩阵转置操作显示区域**************/"<<endl; //求转置程序段 int a1[]= { 0,3,0,0,-5, 0,-1,0,0,0, 6,0,0,8,0, -4,0,0,0,7 }; //相应于a1的三元组法存储到M0中 int num=0; Matrix M0,T; M0.mu=4;//矩阵行数 M0.nu=5;//矩阵列数 M0.tu=7;//矩阵中非0元个数 for(int i=0;i<4;i++) { for(int j=0;j<5;j++) { if(a1[i*5+j]!=0) { M0.data[++num].i=i+1; M0.data[num].j=j+1; M0.data[num].e=a1[i*5+j]; } } } cout<<"原始矩阵三元组法存储显示："<<endl; for(i=1;i<=M0.tu;i++) cout<<"("<<M0.data[i].i<<", "<<M0.data[i].j<<", "<<M0.data[i].e <<")"<<endl; FastTransposeSMatrix(M0, T); cout<<"原始矩阵转置矩阵三元组法存储显示："<<endl; for(i=1;i<=T.tu;i++) cout<<"("<<T.data[i].i<<", "<<T.data[i].j<<", "<<T.data[i].e <<")"<<endl; //求转置程序段 cout<<"/***************稀疏矩阵转置操作显示区域**************/"<<endl<<endl; cout<<"/***************稀疏矩阵乘法操作显示区域**************/"<<endl; //乘法程序段 int a2[]= { 0,2,0,0,3, 0,-1,5,0,0, 4,0,0,7,6, 0,0,-3,0,0 }; int a3[]= { 0,3, 2,4, 1,0, 0,0, 0,-2 }; MMatrix M,N,Q; num=0; M.mu=4;//矩阵行数 M.nu=5;//矩阵列数 M.tu=8;//矩阵中非0元个数 for(i=0;i<4;i++) { for(int j=0;j<5;j++) { if(a2[i*5+j]!=0) { M.data[++num].i=i+1; M.data[num].j=j+1; M.data[num].e=a2[i*5+j]; } } } int num1[10]; for (i=1; i<=M.mu; ++i) num1[i] = 0; for (int t=1; t<=M.tu; ++t) ++num1[M.data[t].i]; M.rpos[1] = 1; for (i=2; i<=M.mu; ++i) M.rpos[i] = M.rpos[i-1] + num1[i-1]; cout<<"参与乘法操作的第一个矩阵三元组法存储显示："<<endl; for(i=1;i<=M.tu;i++) cout<<"("<<M.data[i].i<<", "<<M.data[i].j<<", "<<M.data[i].e <<")"<<endl; cout<<endl; num=0; N.mu=5;//矩阵行数 N.nu=2;//矩阵列数 N.tu=5;//矩阵中非0元个数 for(i=0;i<5;i++) { for(int j=0;j<2;j++) { if(a3[i*2+j]!=0) { N.data[++num].i=i+1; N.data[num].j=j+1; N.data[num].e=a3[i*2+j]; } } } for (i=1; i<=N.mu; ++i) num1[i] = 0; for (t=1; t<=N.tu; ++t) ++num1[N.data[t].i]; N.rpos[1] = 1; for (i=2; i<=N.mu; ++i) N.rpos[i] = N.rpos[i-1] + num1[i-1]; cout<<"参与乘法操作的第二个矩阵三元组法存储显示："<<endl; for(i=1;i<=N.tu;i++) cout<<"("<<N.data[i].i<<", "<<N.data[i].j<<", "<<N.data[i].e <<")"<<endl; cout<<endl; MultSMatrix( M, N, Q) ; cout<<"乘法操作结果矩阵三元组法存储显示："<<endl; for(i=1;i<=Q.tu;i++) cout<<"("<<Q.data[i].i<<", "<<Q.data[i].j<<", "<<Q.data[i].e <<")"<<endl; //乘法程序段 cout<<"/***************稀疏矩阵乘法操作显示区域**************/"<<endl<<endl; return 0; } bool FastTransposeSMatrix(Matrix M, Matrix &T) { int col,num[6],t,cpot[6],q,p; T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j]; cpot[1] = 1; for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1]; for (p=1; p<=M.tu; ++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]; } } // if return true; } // FastTransposeSMatrix bool MultSMatrix(MMatrix M, MMatrix N, MMatrix &Q) { int arow,ccol,brow,p,t,q,rpos[5],ctemp[3]; if (M.nu != N.mu) return false; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) { // Q是非零矩阵 for (arow=1; arow<=M.mu; ++arow) { memset(ctemp,0,3*sizeof(int));// 当前行各元素累加器清零 Q.rpos[arow] = Q.tu+1; int xx; if(arow<M.mu) { xx=M.rpos[arow+1]; } else { xx=M.tu+1; } for (p=M.rpos[arow]; p<xx;++p) { //对当前行中每一个非零元 brow=M.data[p].j; if (brow < N.mu ) { t = N.rpos[brow+1]; } else { t = N.tu+1 ; } for (q=N.rpos[brow]; q< t; ++q) { ccol = N.data[q].j; // 乘积元素在Q中列号 ctemp[ccol] += M.data[p].e * N.data[q].e; } // for q } // 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol<=Q.nu; ++ccol) if (ctemp[ccol]) { if (++Q.tu > MAXSIZE) return false; Q.data[Q.tu].i=arow; Q.data[Q.tu].j=ccol; Q.data[Q.tu].e=ctemp[ccol]; } // if } // for arow } // if return true; } // MultSMatrix