#include<iostream.h>

struct node
{
	int i;
	int j;
	int aa;
	node * right;
	node * down;
};

int m;
int n;
int a;


int * matrix(int c,int d)
{
	int * M;
	M=new int [c*d];

	cout<<"請(qǐng)輸入稀疏矩陣各元素："<<endl;

	for(int e=0;e<m;e++)
	{
		for(int f=0;f<n;f++)
		{
			cin>>M[e*n+f];
		}
	}

	return M;
}

void showmatrix(node * head)
{
	while(head)
	{
		if(head->aa==0)
		{
			cout<<"   ";
		}
		if(head->aa!=0)
		{
			cout<<head->aa<<"  ";
		}
		head=head->right;
	}
	cout<<endl;
}

void main()
{
	cout<<"請(qǐng)輸入矩陣的行和列："<<endl;
    cin>>m>>n;
	int * ma;
	ma=matrix(m,n);

	node * * chead;
	chead=new node * [n];
	node * * rhead;
	rhead=new node * [m];
    
	node * NN;
	NN=new node [m*n];
	node * * N;
	N=new node * [m*n];
	for(int k=0;k<m;k++)
	{
		for(int l=0;l<n;l++)
		{
			N[k*n+l]=&NN[k*n+l];
		}
	}

	for(int f=0;f<m;f++)
	{
		for(int g=0;g<n;g++)
		{
			N[f*n+g]->i=f;
			N[f*n+g]->j=g;
			N[f*n+g]->aa=ma[f*n+g];
		}

	}

	node * p1;
	node * p2;

	for(int b=0;b<m;b++)
	{
		a=0;
		p1=N[b*n+a];
		rhead[b]=NULL;
		p2=p1;

		for(a=0;a<n;a++)
		{
			if(rhead[b]==NULL)
			{
				rhead[b]=p1;
			}
			else
				p2->right=p1;
			p2=p1;
			p1=N[b*n+a+1];
		}

		p2->right=NULL;
	}

	for(b=0;b<n;b++)
	{
		a=0;
		p1=N[b*m+a];
		chead[b]=NULL;
		p2=p1;

		for(a=0;a<m;a++)
		{
			if(chead[b]==NULL)
			{
				chead[b]=p1;
			}
			else
				p2->down=p1;
			p2=p1;
			p1=N[b*n+a+1];
		}
		p2->down=NULL;
	}

    cout<<"十字鏈表各元素為："<<endl;
	for(int count=0;count<m;count++)
	{
		showmatrix(rhead[count]);
	}

}