稀疏矩阵可用三元组表存储方法存储，但是当稀疏矩阵中非零元素的位置或者个数经常发生变化时，使用三元组表就不太方便，十字链表存储能够提高访问效率，这种方法不仅为稀疏矩阵的每一行设置一个单独的行循环链表，同样也为每一列设置一个单独的列循环链表。这样，稀疏矩阵中的每一个非零元素同时包含在两个链表中，即包含在它所在的行链表和所在的列链表中，也就是两个链表的交汇处。
稀疏矩阵的链接点构造有5个域值：row, col, value, down, right。其中row, col, value分别表示某非零元素所在的行号，列号，和相应的元素值；down与right分别称为向下指针与向右指针，它们分别用来链接同一列中的及同一行中的某非零元素的结点。也就是说，稀疏矩阵中同一行的所有非零元素是通过right指针链接成一个行链表，同一列中的所有非零元素是通过down指针链接成一个列链表。
对于m个行链表，分别设置m个行链表表头结点，表头结点的构造与链表中其他链接点一样，只是令row与col域的值均为0，right域指向相应行链表的第一个链接点，同理，对于n个列链表，分别设置n个列链表表头结点，头结点也同其他链接点一样，只是令row和col值均为0，down域指向相应列链表的第一个链接点。另外通过value域把所有这些表头链接点也链接成一个循环链表。
十字链表中的链接点类型可以描述如下：
//十字链表中链接点类型
typedef struct node {
int row, col;
union {
int val;
struct node *ptr;
}; //value域包括两种类型
struct node *right, *down;
}CNode, *CrossLink;
可以发现m个行链表的表头结点与n个列链表的表头结点中，行链表的头结点只使用了right域作为指针，列链表的头结点只使用了down域来链接列链表和value域来链接表头链接点。于是可以设想将原来的(m+n)个头结点实际上合并成max(m,n)个头结点。为此，再设置一个结点头结点链表的头结点，称为总头结点，总头结点的构造可以描述为：
//十字链表的总头结点类型
typedef struct {
int m, n, t, nil;
CrossLink link;
}HNode, *HLink;
其中m, n为稀疏矩阵总的行数和总的列数，t为非零元素总的个数，link指向头结点链表的第1个头结点。
下面是创建, 打印及销毁一个具有m行n列及有t个非零元素的稀疏矩阵的十字链表的算法。
1. 创建十字链表
稀疏矩阵用三元组表的形式作为输入，首先输入稀疏矩阵的行数，列数及非零元素的总个数(m, n, t)，然后依次读入t个三元组，算法中用到了一个辅助数组hdnode[0..max(m, n)-1],其中hdnode[i]用来分别存放第i列(也是第i行)链表的头结点的指针(0<=i<=max(m, n)-1).
#define MaxN 100
/*创建一个十字链表*/
HLink makeCrossLink( ){
HLink head;
CrossLink p, last, hdnode[MaxN];
int m, n, t, k, i, current_row;
int rrow, ccol, val;
scanf( "%d %d %d", &m, &n, &t ); /*读入矩阵总的行数，列数和非零元素的个数*/
if( t <= 0 )
return NULL;
k = ( m > n ) ? m : n; /*取矩阵行数和列数中值较大者作为表头结点的个数*/
for( i = 0; i < k; i++ ){ /* 生成k个表头结点,并初始化表头结点中各个元素 */
p = ( CrossLink )malloc( sizeof( CNode ) );
hdnode[i] = p;
p->row = 0;
p->col = 0;
p->ptr = p;
p->right = p;
p->down = p;
}
current_row = 1;
last = hdnode[0];
for( i = 1; i <= t; i++ ){ /* 以三元组表的形式输入元素 */
scanf( "%d %d %d", &rrow, &ccol, &val );
if( rrow > current_row ){ /* 当一行的非零元素读取完毕，则立刻将链表封闭成一个循环链表*/
last->right = hdnode[current_row-1];
last = hdnode[rrow-1];
current_row = rrow;
}
p = ( CrossLink )malloc( sizeof( CNode ) ); /* 申请一个新的链接点来存储新的非零值 */
p->row = rrow;
p->col = ccol;
p->val = val; /* 生成一个新结点 */
last->right = p; /* 将新的链接点链接到相应行链表中 */
last = p;
hdnode[ccol-1]->ptr->down = p;
hdnode[ccol-1]->ptr = p; /* 将新的链接点链接到相应的列链表中 */
}
last->right = hdnode[current_row-1]; /* 将最后一个行链表封闭成循环链表 */
for( i = 0; i < k; i++ ){ /* 将所有列链表封闭成循环链表 */
hdnode[i]->ptr->down = hdnode[i];
}
head = ( HLink )malloc( sizeof( HNode ) ); /* 申请一个总的头结点 */
head->m = m;
head->n = n;
head->t = t;
for( i = 0; i < k-1; i++ ){ /* 利用value域将头结点链接成一个循环链表 */
hdnode[i]->ptr = hdnode[i+1];
}
if( k == 0 )
head->link = ( CrossLink )head;
else{
head->link = hdnode[0]; /* 将总头结点的link域指向头结点链表的第1个头结点 */
hdnode[k-1]->ptr = ( CrossLink )head; /* 将头结点链表的最后一个头结点的ptr域指向总的头结点 */
}
return head;
}
2. 打印十字链表
/* 打印十字链表 */
void printLink( HLink alink ){
CrossLink p, q; /* p用来遍历头结点链表，q用来遍历每个行链表 */
if( alink != NULL ){
printf( "(%d, %d, %d)\n", alink->m, alink->n, alink->t ); /* 打印总头结点信息 */
p = alink->link; /* p指向头结点链表的第1个链接点 */
while( p != (CrossLink)alink ){
q = p->right; /* q指向行链表的第1个元素 */
while( q != p ){
printf( "(%d, %d, %d)\n", q->row, q->col, q->val );
q = q->right;
}
p = p->ptr; /* p指向下一个头结点链表中的元素 */
}
}
}
3. 销毁一个十字链表
/* 销毁一个十字链表 */
void deleteLink( HLink *alink ){
CrossLink p = ( *alink )->link;
CrossLink q, r;
while( p != ( CrossLink )*alink ){
q = p->right; /* 将q指向行链表的第1个元素 */
while( q != p ){ /* 销毁一个行链表 */
r = q;
q = q->right;
free( r );
}
r = p; /* 销毁该行链表的表头结点，将p指向下一个行链表的表头结点 */
p = p->ptr;
free( r );
}
free( *alink ); /* 释放总头结点的空间 */
}
建立十字链表的算法思想可以总结如下：
1，建立max(m, n)个头结点
2，依次输入三元组表的一个三元组(row ,col, value), 同时申请一个新的链接点，分别将row, col, 与value送入新结点的相应域内，并将新结点分别链接到相应的行链表和列链表中
3，当某一行的非零元素全部处理完毕，及时将该链表封闭成一个循环链表
4，将所有列链表封闭成循环链表
5，创建稀疏矩阵十字链表的一个总头结点，并利用value域将总头结点与各个链表的头结点链接成一个循环链表，并设总头结点的指针为head
算法中设置了一个活动指针变量last, 每当输入一个三元组时，先判断是否是当前要处理的那一行元素，若是，申请一个新的链接点后，把新的链接点的存储位置送当前last所指的链接点的right域，同时令last指向新的链接点，可见，last实际上是行链表尾结点的指针。另外，第i个头结点hdnode[i]的value在开始时用来跟踪第i列链表当前最后那个链接点，以便将新的链接点链接到相应列链表的表尾，其功能类似与指针变量last。