村上春树 1q84 mobi:什么是十字链表

十字链表是这样构成的：用链表模拟矩阵的行（或者列，这可以根据个人喜好来定），然后，再构造代表列的链表，将每一行中的元素节点插入到对应的列中去。十字链表的逻辑结构就像是一个围棋盘（没见过，你就想一下苍蝇拍，这个总见过吧），而非零元就好像是在棋盘上放的棋子，总共占的空间就是，确定那些线的表头节点和那些棋子代表的非零元节点。最后，我们用一个指针指向这个棋盘，这个指针就代表了这个稀疏矩阵。
=================
说了一堆还是举个例子吧：
#include <malloc.h>
#include <stdio.h>

/*十字链表的结构类型定义如下：*/
typedef struct OLNode
{
int row,col; /*非零元素的行和列下标*/
ElementType value;
struct OLNode *right; /*非零元素所在行表、列表的后继链域*/
struct OLNode *down;
}OLNode; *OLink;

typedef struct
{
OLink *row_head; /*行、列链表的头指针向量*/
OLink *col_head;
int m,n,len; /*稀疏矩阵的行数、列数、非零元素的个数*/
}CrossList;

/*建立稀疏矩阵的十字链表的算法*/

void CreateCrossList(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[i]==NULL)
M->row_head[i]=p;
else
{
/*寻找行表中的插入位置*/
for(q=M->row_head[i];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; /*完成插入*/
}
}
}

更多相关知识自己去找数据结构的书来看。
编程爱好者群：24410693 只要对c有兴趣就可以申请加入本群.