利用三元組表表示稀疏矩陣時(shí)，若矩陣的運(yùn)算使非零元素的個(gè)數(shù)發(fā)生變化，就必須對(duì)三元組表進(jìn)行插入、刪除，也就是說必須移動(dòng)三元組表中的元素，由于三元組表是順序存儲(chǔ)結(jié)構(gòu)，所以這些操作將花費(fèi)大量的時(shí)間，十字鏈表可以克服三元組表的上述缺點(diǎn)。

  在十字鏈表中，數(shù)組的每一行的非零元素結(jié)點(diǎn)構(gòu)成一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈表，每一列的非零元素結(jié)點(diǎn)也構(gòu)成一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈表，這種組織方法使同一非零元素結(jié)點(diǎn)既處在某一行的鏈表中，又處在某一列的鏈表中。因此非零元素結(jié)點(diǎn)中設(shè)有兩個(gè)指針域：指針域down指向其同列的下一個(gè)非零元素的結(jié)點(diǎn)，right域指向其同行的下一個(gè)非零元素結(jié)點(diǎn)。除這兩個(gè)域外，結(jié)點(diǎn)中還應(yīng)設(shè)有存放該非零元素的行值、列值、元素值的域，設(shè)他們分別為row、col和e。十字鏈表中非零元素結(jié)點(diǎn)的結(jié)構(gòu)如下所示：

   為了使整個(gè)鏈表中的結(jié)點(diǎn)結(jié)構(gòu)一致，我們規(guī)定行（列）循環(huán)鏈表的表頭結(jié)點(diǎn)和表中非零元素的結(jié)點(diǎn)一樣，也設(shè)5個(gè)域，并且均置表頭結(jié)點(diǎn)的行域和列域?yàn)榱恪?/p>

   由于行表頭結(jié)點(diǎn)不使用down域，而列表頭結(jié)點(diǎn)不使用right域，因此，第i行的行表頭結(jié)點(diǎn)和第i列的列表頭結(jié)點(diǎn)可以合用一個(gè)結(jié)點(diǎn)，稱為行列表頭結(jié)點(diǎn)。

   由于行表頭結(jié)點(diǎn)的數(shù)據(jù)域沒有意義的，而且我們希望將行列表頭結(jié)點(diǎn)組織在一個(gè)循環(huán)鏈表中，因此，使用C語言中共用體的概念，將這個(gè)域作為指針域，將各行列表頭鏈接起來。

   我門為整個(gè)十字鏈表再設(shè)一個(gè)總表頭結(jié)點(diǎn)，其row域和col域的值分別是稀疏矩陣的行數(shù)和列數(shù)，行列指針無意義，用指針域（非零元素結(jié)點(diǎn)的元素值域，行列表頭結(jié)點(diǎn)相鏈的指針域）指向第一個(gè)列表頭結(jié)點(diǎn)。設(shè)head為指向總表頭結(jié)點(diǎn)的指針，因此，只要給定head指針值，便可取得稀疏矩陣的全部信息了。

十字鏈表的結(jié)構(gòu)類型說明：

typedef  int ElemType;typedef struct OLNode{	int row, col;	union 	{		struct OLNode *next;	//表頭結(jié)點(diǎn)使用next域		ElemType e;				//表中元素結(jié)點(diǎn)使用e域	}uval;	struct OLNode *down, *right;}OLNode,*OLink;建立十字鏈表的算法分為兩步：
（1）建立表頭結(jié)點(diǎn)的循環(huán)鏈表。讀入矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)。因?yàn)樾小⒘墟湵砉蚕硗唤M表頭結(jié)點(diǎn)，所以表頭結(jié)點(diǎn)的個(gè)數(shù)應(yīng)是行數(shù)、列數(shù)中的較大者。建立整個(gè)十字鏈表的頭結(jié)點(diǎn)*head以及所有行、列鏈表的頭結(jié)點(diǎn)，將頭結(jié)點(diǎn)通過next域鏈接成循環(huán)鏈表。初始時(shí)每一行、列鏈表都是空的循環(huán)鏈表。
（2）依次讀入非零元素的三元組表（row，col，e），生成一個(gè)結(jié)點(diǎn)*p，然后將其插入到第row行的行鏈表的正確位置上，以及第col列的列鏈表的正確位置上。*p的正確位置應(yīng)為：在行鏈表上，首先查找到第row行的頭結(jié)點(diǎn)，然后沿著結(jié)點(diǎn)的right域找到第一個(gè)列號(hào)大于col的結(jié)點(diǎn)*（q->right）,而*（q->right）即為*p及結(jié)點(diǎn)的后繼，*q即為*p結(jié)點(diǎn)的前驅(qū)，*p應(yīng)插入到*q結(jié)點(diǎn)之后。如果行鏈表上所有結(jié)點(diǎn)的列號(hào)均小于col，則*p應(yīng)插入到行鏈表的表尾。查找第col列的列鏈表的正確插入位置與此類似。
完整代碼如下：
#include<iostream>using namespace std;#define  max    100typedef  int ElemType;typedef struct OLNode{	int row, col;	union 	{		struct OLNode *next;	//表頭結(jié)點(diǎn)使用next域		ElemType e;				//表中元素結(jié)點(diǎn)使用e域	}uval;	struct OLNode *down, *right;}OLNode,*OLink;OLink CreateCrossList() {		//建立十字鏈表	int m, n, t,row,col,e, maxmn;	OLink h[max],p,q;	cout << "請(qǐng)輸入行數(shù)、列數(shù)以及非零元素的個(gè)數(shù)" << endl;	cin >> m >> n >> t;	if (m > n) maxmn = m;	else maxmn = n;	OLink head = (OLNode*)malloc(sizeof(OLNode));	head->row = m;	head->col = n;	h[maxmn] = head;		//h[maxmn+1]為一組指示行列表頭結(jié)點(diǎn)的指針	for (int i = 0; i < maxmn;i++) {	//建立表頭結(jié)點(diǎn)的循環(huán)鏈表		    p= (OLNode*)malloc(sizeof(OLNode));		p->row = 0; p->col = 0;		p->down = p; p->right = p;		h[i] = p;		if (i == 0) head->uval.next = p;		else h[i - 1]->uval.next = p;	}	p->uval.next = head;		//最后一個(gè)結(jié)點(diǎn)指向表頭結(jié)點(diǎn)*head	for (int num = 1; num <= t;num++) {		cout << "請(qǐng)輸入一個(gè)非零元素的三元組" << endl;		cin >> row >> col >> e;		p= (OLNode*)malloc(sizeof(OLNode));  //生成結(jié)點(diǎn)		p->row = row;		p->col = col;		p->uval.e = e;		q = h[row];		while (q->right!=h[row] && q->right->col<col) {	//查*p在第row行的插入位置			q = q->right;		}		p->right = q->right; q->right = p;  //將*p插入到第row行的循環(huán)鏈表中		q = h[col];		while (q->down != h[col] && q->down->row < row) {//查*p在第col列的插入位置			q = q->down;		}		p->down = q->down; q->down = p;  //將*p插入到第col列的循環(huán)鏈表中	}	return head;}void PRint(OLink head) {	OLink p = head->uval.next;	int m = 0,n = 0;	while (m != head->row) {		p = p->right;		while (n != head->col) {			if (m == p->row && n == p->col && p->uval.e!=NULL) {				cout << p->uval.e << " ";				p = p->right;			}			else {				cout << "0 ";			}			n++;		}		n = 0;		m++;		p = p->uval.next;		cout << endl;	}}void main() {	OLink list;	list = CreateCrossList();	cout << "鏈表內(nèi)容為:" << endl;	print(list);	system("pause");}