苗火 Nicholas

[Data structures]Triple sequential matrix

2019-8-19 萧 写技术

#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");

}

标签: Data Structures data_structures