#include<stdio.h>
#define MAXSIZE 100
#define MAXRC 100
typedef int ElemType;

typedef struct{
	int i,j;
	ElemType e;
}Triple;

typedef struct{
	Triple data[MAXSIZE+1];
	int rpos[MAXRC+1];
	int lpos[MAXRC+1];
	int mu,nu,tu;
	}RLSMatrix;

void CreateSMatrix(RLSMatrix &M)
{
	int col,t;
	int num[MAXSIZE+1];
	
	printf("輸入該矩陣的行數、列數和非零元個數，以空格分隔：\n\n");
	scanf("%d %d %d",&M.mu,&M.nu,&M.tu);
	for(col=1;col<=M.nu;++col)  num[col]=0;
	for(t=1;t<=M.tu;++t)
	{
		printf("輸入第%d個元素的行號i、列號j與值e:",t);
		scanf("%d %d %d",&M.data[t].i,&M.data[t].j,&M.data[t].e);
	}
	for(t=1;t<=M.tu;++t)
	{
		++num[M.data[t].j];
	}
	M.rpos[1]=1;
	for(col=2;col<=M.nu;++col)
		M.rpos[col]=M.rpos[col-1]+num[col-1];

    for(col=1;col<=M.mu;++col)  num[col]=0;
	for(t=1;t<=M.tu;++t)
	{
		++num[M.data[t].i];
	}
	M.lpos[1]=1;
	for(col=2;col<=M.mu;++col)
		M.lpos[col]=M.lpos[col-1]+num[col-1];
}

void DispMatrix(RLSMatrix &M)
{
	int p;
	if (M.tu<=0) 
		return;
	printf("\t%d\t%d\t%d\n",M.mu,M.nu,M.tu);
		printf("\t------------------\n");
	for (p=1;p<=M.tu;p++)
		printf("\t%d\t%d\t%d\n",M.data[p].i,M.data[p].j,M.data[p].e);
        printf("\n");

}

void TransposeSMatrix()
{
	RLSMatrix M,T;
	int col,p,q;
	printf("\n");
	printf("首先實現矩陣的轉置\n");printf("\n");
    printf("//創建需被轉置的矩陣M：//\n");
	CreateSMatrix(M);
	printf("M的三元組:\n");
	DispMatrix(M);	
	T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
	for(p=1;p<=M.tu;++p)
	{
		col=M.data[p].j;q=M.rpos[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;
		++M.rpos[col];
	}
  	printf("M轉置為T\n");
    DispMatrix(T);
}
void AddSMatrix()
{
	RLSMatrix M,N,P;
	int p=1,q=1,k=1;
	ElemType v;
	printf("\n");
	printf("實現矩陣的加法M+N\n");printf("\n");
    printf("//創建矩陣M：//\n");
	CreateSMatrix(M);
    printf("//創建矩陣N：//\n");
	CreateSMatrix(N);
	if (M.mu!=N.mu || M.nu!=N.nu)
	printf("ERROR!");			
	P.mu=M.mu;P.nu=M.nu; 
{
	while (p<=M.tu && q<=N.tu) 
	{	
		if (M.data[p].i==N.data[q].i)
		{	
			if(M.data[p].j<N.data[q].j) 
			{	
				P.data[k].i=M.data[p].i;
				P.data[k].j=M.data[p].j;
				P.data[k].e=M.data[p].e;
				k++;p++;
           	}
           	else if (M.data[p].j>N.data[q].j)
			{	
				P.data[k].i=N.data[q].i;
               	P.data[k].j=N.data[q].j;
               	P.data[k].e=N.data[q].e;
               	k++;q++;
           	}
           	else
			{ 	
				v=M.data[p].e+N.data[q].e;
				if (v!=0)
				{	
					P.data[k].i=M.data[p].i;
					P.data[k].j=M.data[p].j;
					P.data[k].e=v;
					k++;
				}
				p++;q++;
			}
          	 
		}
     	else if (M.data[p].i<N.data[q].i) 
		{	
			P.data[k].i=M.data[p].i;	 
			P.data[k].j=M.data[p].j;
			P.data[k].e=M.data[p].e;
			k++;p++;
		}
    	else							
		{	
			P.data[k].i=N.data[q].i;	 
			P.data[k].j=N.data[q].j;
			P.data[k].e=N.data[q].e;
			k++;q++;
     	}
	
	}
    if(p<=M.tu)
		for(p;p<=M.tu;p++)
		{	
			P.data[k].i=M.data[p].i;	  
			P.data[k].j=M.data[p].j;
			P.data[k].e=M.data[p].e;
			k++;
		}
	else if(q<=N.tu)
		for(q;q<=N.tu;q++)
		{	
			P.data[k].i=N.data[q].i;	
			P.data[k].j=N.data[q].j;
			P.data[k].e=N.data[q].e;
			k++;
     	}
	}
		P.tu=k-1;
    printf("M的三元組:\n");
	DispMatrix(M);	
    printf("N的三元組:\n");
	DispMatrix(N);	
	printf("M與N矩陣之和：\n");
	DispMatrix(P);
}

void MultSMatrix()
{
	
	RLSMatrix M,N,Q;
	int arow,brow,p,tp,ccol,t,q;
	ElemType ctemp[10];
	for(t=0;t<=10;t++)ctemp[t]=0;
	printf("\n");
	printf("實現矩陣的乘法M*N\n");printf("\n");
    printf("//創建矩陣M：//\n");
	CreateSMatrix(M);
    printf("//創建矩陣N：//\n");
	CreateSMatrix(N);
	if(M.nu!=N.mu)printf("ERROR!");
		Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;
	if(M.tu*N.tu!=0)
	{
		for(arow=1;arow<=M.mu;++arow)
		{
			
			Q.lpos[arow]=Q.tu+1;
			if(arow<M.mu)tp=M.lpos[arow+1];
			else{tp=M.tu+1;}
			for(p=M.lpos[arow];p<tp;++p)
			{
				brow=M.data[p].j;
				if(brow<N.mu) t=N.lpos[brow+1];
				else {t=N.tu+1;}
				for(q=N.lpos[brow];q<t;++q)
				{
					ccol=N.data[q].j;
					ctemp[ccol]+=M.data[p].e*N.data[q].e;
				}
			}
			
			for(ccol=1;ccol<=Q.nu;++ccol)
				if(ctemp[ccol])
				{
					if(++Q.tu>MAXSIZE) printf("ERROR!");
				    	Q.data[Q.tu].i=arow;	 
		            	Q.data[Q.tu].j=ccol;
		            	Q.data[Q.tu].e=ctemp[ccol];
					
				}
		    for(ccol=1;ccol<=Q.nu;++ccol)
				ctemp[ccol]=0;
		}
	}
    printf("M的三元組:\n");
	DispMatrix(M);	
    printf("N的三元組:\n");
	DispMatrix(N);	
	printf("M與N矩陣之積：\n");
    DispMatrix(Q);
}

void main()
{
	TransposeSMatrix();
 	AddSMatrix();
	MultSMatrix();
}