#include <stdio.h>
#include <stdlib.h>
#define MAX 1024
typedef struct _Triple{
int i,j;
int e;
}Triple;
typedef struct _TSMatrix{
Triple data[MAX+1];
int rpos[MAX+1]; //Sequential table of row logical link
int m,n,t; //m rows, n cols, t none zero
}TSMatrix;
void CreateMatrix(TSMatrix *M)
{
int m,n;
int e;
int i,j;
int row,t;
int num[MAX];
scanf(" %d %d", &m, &n);
M->m = m;
M->n = n;
M->t = 0;
for(i=1; i<=m; i++){
for(j=1; j<=n; j++){
scanf(" %d", &e);
if(e){
M->t++;
M->data[M->t].i = i;
M->data[M->t].j = j;
M->data[M->t].e = e;
}
}
}
for(row = 1; row <= M->m; row++){
num[row] = 0;
}
for(t = 1; t <=M->t; t++){
num[M->data[t].i]++;
}
M->rpos[1] = 1;
for(row = 2; row <= M->m; row++){
M->rpos[row] = M->rpos[row-1] + num[row-1];
}
}
void PrintMatrix(TSMatrix M)
{
int i,j;
int p = 1;
for(i=1; i<=M.m; i++){
for(j=1; j<=M.n; j++){
if(M.data[p].i == i && M.data[p].j == j){
printf(" %2d", M.data[p++].e);
}else{
printf(" %2d", 0);
}
}
printf("\n");
}
}
int TransposeSMatrix(TSMatrix M, TSMatrix *T)
{
int col;
int p;
int q = 1;
for(col = 1; col <= M.n; col++){
for(p = 1; p <= M.t; p++){
if(M.data[p].j == 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;
q++;
}
}
}
return 1;
}
int FastTransposeSMatrix(TSMatrix M, TSMatrix *T)
{
int cpot[MAX];
int num[MAX];
int col,t,p,q;
T->n = M.m;
T->m = M.n;
T->t = M.t;
for(col = 1; col <= M.n; col++){
num[col] = 0;
}
for(t = 1; t <=M.t; t++){
num[M.data[t].j]++;
}
cpot[1] = 1;
for(col = 2; col <= M.n; col++){
cpot[col] = cpot[col-1] + num[col-1];
}
for(p = 1; p <= M.t; 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];
}
return 1;
}
int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)
{
int i;
int ctemp[MAX];
int arow,tp,brow,t,ccol,p,q;
Q->m = M.m;
Q->n = N.n;
Q->t = 0;
for(arow = 1; arow <= M.m; arow++){
for(i=1; i<=N.n; i++){
ctemp[i] = 0;
}
Q->rpos[arow] = Q->t + 1;
if(arow < M.m){
tp = M.rpos[arow+1];
}else{
tp = M.t + 1;
}
for(p = M.rpos[arow]; p < tp; p++){
brow = M.data[p].j;
if(brow < N.m){
t = N.rpos[brow+1];
}else{
t = N.t + 1;
}
for(q = N.rpos[brow]; q < t; q++){
ccol = N.data[q].j;
ctemp[ccol] += M.data[p].e * N.data[q].e;
}
}
for(ccol = 1; ccol <= Q->n; ccol++){
if(ctemp[ccol]){
Q->t++;
Q->data[Q->t].i = arow;
Q->data[Q->t].j = ccol;
Q->data[Q->t].e = ctemp[ccol];
}
}
}
}
void main()
{
TSMatrix M,N,Q;
printf("log.anycle.com\n\n");
printf("Create matrix M:\n");
CreateMatrix(&M);
PrintMatrix(M);
printf("Create matrix N:\n");
CreateMatrix(&N);
PrintMatrix(N);
printf("\n");
printf("Transpose M:\n");
Q.m = M.n;
Q.n = M.m;
Q.t = M.t;
TransposeSMatrix(M, &Q);
PrintMatrix(Q);
printf("\n");
printf("Fast transpose N:\n");
Q.m = N.n;
Q.n = N.m;
Q.t = N.t;
TransposeSMatrix(N, &Q);
PrintMatrix(Q);
printf("\n");
printf("Multipy M and N:\n");
MultSMatrix(M, N, &Q);
PrintMatrix(Q);
printf("\n");
}