十字链表的构成用链表模拟矩阵的行(或者列,这可以根据个人喜好来定),然后,再构造代表列的链表,将每一行中的元素节点插入到对应的列中去。十字链表的逻辑结构就像是一个围棋盘(没见过,你就想一下苍蝇拍,这个总见过吧),而非零元就好像是在棋盘上放的棋子,总共占的空间就是,确定那些线的表头节点和那些棋子代表的非零元节点。最后,我们用一个指针指向这个棋盘,这个指针就代表了这个稀疏矩阵。
链表链表(orthogonallist)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中,对应于有向图中每一条弧都有一个结点,对应于每个定顶点也有一个结点。
举例#include<malloc.h>
#include<stdio.h>
/*十字链表的结构类型定义如下:*/
typedefstructolnode
{
introw,col;/*非零元素的行和列下标*/
elementtypevalue;
structolnode*right;/*非零元素所在行表、列表的后继链域*/
structolnode*down;
}olnode;*olink;
typedefstruct
{
olink*row_head;/*行、列链表的头指针向量*/
olink*col_head;
intm,n,len;/*稀疏矩阵的行数、列数、非零元素的个数*/
}crosslist;
/*建立稀疏矩阵的十字链表的算法*/
voidcreatecrosslist(crosslist*m)
{
/*采用十字链表存储结构,创建稀疏矩阵m*/
scanf(&m,&n,&t);/*输入m的行数,列数和非零元素的个数*/
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==null)
m->row_head=p;
else
{
/*寻找行表中的插入位置*/
for(q=m->row_head;q->right&&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
{
/*寻找列表中的插入位置*/
for(q=m->col_head[j];q->down&&q->down->row<i;q=q->down);/*空循环体*/
p->down=q->down;
q->down=p;/*完成插入*/
}
}
}