建立稀疏矩阵的十字链表

[c]代码库

typedef struct node
{
	int row, col;
	struct node *down , *right;
	union v_next
	{
		datatype v;
		struct node *next;
	}
} MNode，*MLink;


MLink CreatMLink( ) /* 返回十字链表的头指针*/
｛
MLink H;
Mnode *p,*q,*hd[s+1];
int i,j,m,n,t;
datatype v;
scanf ( “%d,%,%d”,&m,&n,&t );
H=malloc ( sizeof ( MNode ) ); /*申请总头结点*/
H->row=m;
H->col=n;
hd[0]=H;
for ( i=1; i<S; i++ )
{
	p=malloc ( sizeof ( MNode ) ); /*申请第i 个头结点*/
	p->row=0;
	p->col=0;
	p->right=p;
	p->down=p;
	hd[i]=p;
	hd[i-1]->v_next.next=p;
}
hd[S]->v_next.next=H; /*将头结点们形成循环链表*/
for ( k=1; k<=t; k++ )
{
	scanf ( “%d,%d,%d”,&i,&j,&v ); /*输入一个三元组，设值为int*/
	p=malloc ( sizeof ( MNode ) );
	p->row=i ;
	p->col=j;
	p->v_next.v=v
	            /*以下是将*p 插入到第i 行链表中去，且按列号有序*/
	            q=hd[i];
	while ( q->right!=hd[i] && ( q->right->col ) <j ) /*按列号找位置*/
		q=q->right;
	p->right=q->right; /*插入*/
	q->right=p;
	/*以下是将*p 插入到第j 行链表中去，且按行号有序*/
	q=hd[i];
	while ( q->down!=hd[j] && ( q->down->row ) <i ) /*按行号找位置*/
		q=q->down;
	p-> down =q-> down; /*插入*/
	q-> down =p;
} /*for k*/
return H;
} /* CreatMLink */