데이터 구조 (4) - 희소 행렬

#include
#include
#define N 30 //           
#pragma warning(disable:4996)

typedef struct mytripple//   
{
	int i,j;
	int data;
}TR;

typedef struct mymatrix//    
{
	TR T[N];//   
	int mu,nu,tu;//  ，  ，      
}MA;

void init(MA *A,MA *B);//     A,B
void showMatrix(MA *A);//    A
MA reverse(MA *A);//    A，        ，     O(tu+nu)
MA addition(MA *A,MA *B);//   A,B  ，   ，          ，     O(A->tu+B->tu)

main()
{
	MA A,B,C;
	init(&A,&B);
	showMatrix(&A);
	showMatrix(&B);

	C=reverse(&B);
	showMatrix(&C);	

	C=addition(&A,&B);
	showMatrix(&C);
}

void init(MA *A,MA *B)
{
	A->mu=3;
	A->nu=4;
	A->tu=4;
	A->T[1].data=3;
	A->T[1].i=1;
	A->T[1].j=2;
	A->T[2].data=-1;
	A->T[2].i=2;
	A->T[2].j=2;
	A->T[3].data=12;
	A->T[3].i=2;
	A->T[3].j=4;
	A->T[4].data=9;
	A->T[4].i=3;
	A->T[4].j=1;
	///////////////////////////////////////////////////////////////////
	B->mu=3;
	B->nu=4;
	B->tu=5;
	B->T[1].data=4;
	B->T[1].i=1;
	B->T[1].j=4;
	B->T[2].data=1;
	B->T[2].i=2;
	B->T[2].j=2;
	B->T[3].data=5;
	B->T[3].i=2;
	B->T[3].j=3;
	B->T[4].data=2;
	B->T[4].i=3;
	B->T[4].j=1;
	B->T[5].data=-6;
	B->T[5].i=3;
	B->T[5].j=2;
}

void showMatrix(MA *A)
{
	int i,j,k;//i    ，j    ，k            
	k=1;
	for(i=1;i<=A->mu;i++)
	{
		for(j=1;j<=A->nu;j++)
		{
			if(i==A->T[k].i&&j==A->T[k].j)
			{
				printf("%4d",A->T[k].data);
				k++;
			}
			else
				printf("%4d",0);			
		}
		printf("
");
	}
	printf("
");
}

MA reverse(MA *A)//    A，        
{
	int i;
	int pos;
	TR temp;
	int *cpos,*cnum;//       
	MA B;
	cnum=(int *)malloc((A->nu+1)*sizeof(int));
	cpos=(int *)malloc((A->nu+1)*sizeof(int));
	//   cnum
	for (i = 1; i <= A->nu; i++)
		cnum[i]=0;
	for (i = 1; i <= A->tu; i++)
		cnum[A->T[i].j]++;

	//  cpos
	cpos[1]=1;
	for(i=2;i<=A->nu;i++)
		cpos[i]=cpos[i-1]+cnum[i-1];
	free(cnum);

	//        ，    
	B.mu=A->nu;
	B.nu=A->mu;
	B.tu=A->tu;
	//  cpos    
	for (i = 1; i <= A->tu; i++)
	{
		temp=A->T[i];
		pos=cpos[temp.j];
		B.T[pos].i=temp.j;
		B.T[pos].j=temp.i;
		B.T[pos].data=temp.data;
		cpos[temp.j]++;
	}

	free(cpos);
	return B;
}

MA addition(MA *A, MA *B)//   A,B  ，   
{
	int i,j,k;//   
	int temp;
	int p1,p2;//     A,B    
	int mu,nu;
	MA C;

	mu=A->mu;
	nu=A->nu;
	C.mu=mu;
	C.nu=nu;

	k=0;//  C       
	for (i = 1, j = 1; i <= A->tu && j <= B->tu;)//    
	{
		p1=(A->T[i].i-1)*nu+A->T[i].j;
		p2=(B->T[j].i-1)*nu+B->T[j].j;
		if (p1 < p2)
		{
			k++;
			C.T[k]=A->T[i];
			i++;
		}
		else if (p2 < p1)
		{
			k++;
			C.T[k]=B->T[j];
			j++;
		}
		else //p1==p2
		{
			temp=A->T[i].data+B->T[j].data;
			if (temp != 0)//        0，    C 
			{
				k++;
				C.T[k].i=A->T[i].i;
				C.T[k].j=A->T[i].j;
				C.T[k].data=temp;
			}
			i++;
			j++;
		}
	}
	//        ，        C 
	while (i <= A->tu)
	{
		k++;
		C.T[k]=A->T[i];
		i++;
	}
	while (j <= B->tu)
	{
		k++;
		C.T[k]=B->T[j];
		j++;
	}
	//  C       
	C.tu=k;
	return C;
}