十字链表存储

（耿《数据结构》原文）为避免大量移动元素，采用稀疏矩阵的链式存储法——十字链表。

它的好处是能灵活地插入因运算而产生的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。

1.十字链表的存储表示（五要素）

矩阵的每一个非零元素用一个结点表示，该结点除了（row,col,value)以外，还要添加两个链域：

right：用于链接同一行中的下一个非零元素

down：用于链接同一列中的下一个非零元素

在十字链表的储存结构中，可以看成是两个单链表的组合沟通。可以类比行指针，列指针。

同一行的非零元素通过right域链接成一个单链表，

同一列的非零元素通过down域链接成一个单链表。

相应的，需要附设一个存放所有行链表头指针的一维数组和一个存放所有列链表的头指针的一维数组。

2.十字链表的类型定义

一个结点的定义;

typedef struct OLNode
{
int row,col;
ElementType value;
struct OLNode *right,*down;//指向的下一个结点也是同样的结构
}OLNode;*OLink;

十字链表存储结构

typedef struct
{
OLink *row_head,*col_head;//头指针
int m,n,len;//行，列，非零元素个数
}CrossList;

3.十字链表的算法实现

步骤：

①读入稀疏矩阵的行数，列数，非零元素个数；

②申请行，列链表的头指针空间；

③逐个读入非零元素，分别插入行链表，列链表。

算法（建立稀疏矩阵的十字链表，实质是在两个单链表中完成插入）

CreateCrossList(CrossList *M)
{
scanf("%d %d %d",&m,&n,&t);
M->m=m;
M->n=n;
M->len=t;
if(!(M->row_head=(OLink*)malloc((m+1)sizeof(OLink)))) exit(OVERFLOW);
if(!(M->col_head=(OLink*)malloc((n+1)sizeof(OLink)))) exit(OVERFLOW);
M->row_head[]=M->col_head[]=NULL;//初始化
for(scanf(&i,&j,&e);i!=0；scanf(&i,&j,&e))//读入非零的数据，信息包括它的行，列，数据
{
if(!(p=(OLNode*)malloc(sizeof(OLNode)))) exit(OVERFLOW);
p->row=i;
p->col=j;
p->value=e;//生成结点
//插入行链表
if(M->row_head[i]==NULL)//如果原先的稀疏矩阵这一行全为零，直接以这个插入的结点创建这一行行链表的头指针
M->row_head[i]=p;
else
{
//寻找插入的位置
q=M->row_head[i];//用来指向这一行的插入点的前一个结点，一开始指向行表头
while(q->right!=NULL&&q->right->col<j)
{
q=q->right;
p->right=q->right;//随循环右移
q->right=p;//完成插入
}
//插入列链表
if(M->col_head[j]==NULL)
M->col_head[j]=p;
else
{
//寻找插入位置
q=M->col_head[j];
while(q->down！=NULL&&q->down->row<i)
q=q->down;
p->down=q->down;
q->down=p;
}
}
}