稀疏矩阵的十字链表存储的思路

       我们知道稀疏矩阵的三元组存储方式的实现很简单，每个元素有三个域分别是i, j, e。代表了该非零元的行号、列号以及值。那么在十字链表的存储方式下，首先这三个域是肯定少不了的，不然在进行很多操作的时候都要自己使用计数器，很麻烦。而十字链表的形式大家可以理解成每一行是一个链表，而每一列又是一个链表。如图所示：

typedef struct OLNode {  
     int  i, j;          //行号与列号   
     ElemType e;        //值   
     struct OLNode *right, *down;  //指针域   
}OLNode, *OList;

这样我们对结点的插入与删除就要修改两个指针域。为了方便我们对结点的操作，我们要创建头指针或者头结点。至于到底是选择头指针呢还是头结点，请继续看下去..

typedef struct {  
    OLink   *Rhead, *Chead;   
    int mu, nu, tu;       // 稀疏矩阵的行数、列数和非零元个数    
}CrossList;  

注意Rhead与Chead的类型，它们是指向指针的指针，也就是说，它们是指向我们定义的OLNode结构的结点的指针的指针。这话有点绕，不过相信C学的不错的朋友都应该清楚。如果不清楚的请看这个帖子  

现在结构体已经定义好了，我们来想想下面应该干什么。首先需要用户输入稀疏矩阵的行数与列数以及非零元的个数。那么就需要定义一个CrossList的结构体变量来存储这些值。

int main(void)  
{  
    CrossList M;  
    CreateSMatrix(&M);  
} 

CreatSMatrix函数是我们今天要创建的函数，它用来建立稀疏矩阵并使用十字链表的方式存储矩阵。该函数的原型为int CreateSMatrix(CrossList *M);

当我们创建好了M就需要用户输入了，那么就要对用户的输入进行检查，看是否符合要求，首先mu, nu, tu都不能小于0，并且mu, nu不能等于0（我们这里假设行号与列号都是从1开始的，所以不能等于0），tu的值必须在0与mu * nu之间。

int CreateSMatrix(CrossList *M)  
{     
    int i, j, m, n, t;  
    int k, flag;  
    ElemType e;  
    OLNode *p, *q;  
      
    if (M->Rhead)  
        DestroySMatrix(M);  
  
    do {  
        flag = 1;  
        printf("输入需要创建的矩阵的行数、列数以及非零元的个数");  
        scanf("%d%d%d", &m, &n, &t);  
        if (m<0 || n<0 || t<0 || t>m*n)  
            flag = 0;  
    }while (!flag);  
    M->mu = m;  
    M->nu = n;  
    M->tu = t;  
        ...................................
         return 1;  
}  

当用户输入了正确的值以后，我们要创建头指针的数组

//创建行链表头数组   
M->Rhead = (OLink *)malloc((m+1) * sizeof(OLink));  
if(!M->Rhead)  
    exit(-1);  
//创建列链表头数组   
M->Chead = (OLink *)malloc((n+1) * sizeof(OLink));  
if(!(M->Chead))  
    exit(-1);  

创建完以后必须初始化，因为我们后面的插入就其中一个判断条件就是它们的值为NULL，也就是该行或者该列中没有结点

for(k=1;k<=m;k++) // 初始化行头指针向量;各行链表为空链表    
    M->Rhead[k]=NULL;  
for(k=1;k<=n;k++) // 初始化列头指针向量;各列链表为空链表    
    M->Chead[k]=NULL;

现在我们就可以进行结点的输入了，显而易见的要输入的结点个数刚才已经存放到了t变量中，那么我们要创建t个结点。这就是一个大的循环

而每创建一个结点我们都要修改它的两个指针域以及链表头数组。那么我们可以分开两次来修改，第一次修改行的指针域，第二次修改列的指针域。

do {  
            flag = 1;  
            printf("输入第%d个结点行号、列号以及值", k);  
            scanf("%d%d%d", &i, &j, &e);  
            if (i<=0 || j<=0)  
                flag = 0;  
        }while (!flag);  
  
        p = (OLink) malloc (sizeof(OLNode));  
        if (NULL == p)  
            exit(-1);  
        p->i = i;  
        p->j = j;  
        p->e = e;  

当用户输入一系列正确的值，并且我们也创建了一个OLNode类型的结点之后我们要讲它插入到某一行中。首先要确定插入在哪一行？我们输入的时候已经输入了行号i,那么我们自然要插入到i行中，那么应该怎样去插入？分两种情况

1、当这一行中没有结点的时候，那么我们直接插入

2、当这一行中有结点的时候我们插入到正确的位置

逐个来分析：

怎么判定一行中有没有结点？ 记得我们前面对Rhead的初始化吗？ 所有的元素的值都为NULL，所以我们的判断条件就是 NULL==M->Rhead[i].

现在我们来解决第二个问题。

if(NULL==M->Rhead[i] || M->Rhead[i]->j>j)     
        {  
            // p插在该行的第一个结点处   
            // M->Rhead[i]始终指向该行的第一个结点                                      p->right = M->Rhead[i];   
            M->Rhead[i] = p;  
        }   

现在我们再想一下怎么去插入到某一个结点的后面？ 我们新创建的P结点要插入到现有的A结点的后面，那么P的列号必定是大于A的列号，那么我们只要找到第一个大于比P的列号大的结点B，然后插入到B结点之前！如果现有的结点没有一个结点列号是大于P结点的列号的，那么我们就应该插入到最后一个结点之后！所以我们首先要寻找符合条件的位置进行插入  

for(q=M->Rhead[i]; q->right && q->right->j < j; q=q->right)   
    ;  
   p->right=q->right; // 完成行插入    
   q->right=p;  

这样就插入完成了，至于列的指针域的修改和这个类似！现在贴出所有代码 

int CreateSMatrix(CrossList *M)  
{   
 int i, j, m, n, t;  
 int k, flag;  
 ElemType e;  
 OLNode *p, *q;  
   
 if (M->Rhead)  
  DestroySMatrix(M); do {  
  flag = 1;  
  printf("输入需要创建的矩阵的行数、列数以及非零元的个数");  
  scanf("%d%d%d", &m, &n, &t);  
  if (m<0 || n<0 || t<0 || t>m*n)  
   flag = 0;  
 }while (!flag);  
 M->mu = m;  
 M->nu = n;  
 M->tu = t;  
   
 //创建行链表头数组   
 M->Rhead = (OLink *)malloc((m+1) * sizeof(OLink));  
 if(!M->Rhead)  
  exit(-1);  
 //创建列链表头数组   
 M->Chead = (OLink *)malloc((n+1) * sizeof(OLink));  
 if(!(M->Chead))  
  exit(-1);  
 for(k=1;k<=m;k++) // 初始化行头指针向量;各行链表为空链表    
  M->Rhead[k]=NULL;  
 for(k=1;k<=n;k++) // 初始化列头指针向量;各列链表为空链表    
  M->Chead[k]=NULL;  
 //输入各个结点   
 for (k=1; k<=t; ++k)  
 {  
  do {  
   flag = 1;  
   printf("输入第%d个结点行号、列号以及值", k);  
   scanf("%d%d%d", &i, &j, &e);  
   if (i<=0 || j<=0)  
    flag = 0;  
  }while (!flag);  p = (OLink) malloc (sizeof(OLNode));  
  if (NULL == p)  
   exit(-1);  
  p->i = i;  
  p->j = j;  
  p->e = e;  
  if(NULL==M->Rhead[i] || M->Rhead[i]->j>j)   
  {  
   // p插在该行的第一个结点处   
   // M->Rhead[i]始终指向它的下一个结点   
  
   p->right = M->Rhead[i];  
   M->Rhead[i] = p;  
  }  
  else // 寻查在行表中的插入位置   
  {  
   //从该行的行链表头开始，直到找到   
   for(q=M->Rhead[i]; q->right && q->right->j < j; q=q->right)   
    ;  
   p->right=q->right; // 完成行插入    
   q->right=p;  
  }  if(NULL==M->Chead[j] || M->Chead[j]->i>i)   
  {  
   p->down = M->Chead[j];  
   M->Chead[j] = p;  
  }  
  else // 寻查在列表中的插入位置   
  {  
   //从该列的列链表头开始，直到找到   
   for(q=M->Chead[j]; q->down && q->down->i < i; q=q->down)   
    ;  
   p->down=q->down; // 完成行插入    
   q->down=p;  
  }  
 } return 1;  
}