十字链表

十字链表的构成

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

十字链表

十字链表（Orthogonal List)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧都有一个结点，对应于每个定顶点也有一个结点。

　　十字链表之于有向图，类似于邻接表之于无向图。十字链表主要在两个地方应用：稀疏矩阵的存储， 有向图的存储。

 

实现

 

C代码如下：

#include <malloc.h>
#include <stdio.h>

//十字链表的节点定义
typedef struct OLNode
{
  //非零元素的行和列下标
  int row, col;
  int 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)
{
   int m, n, t;
   int i, j, e;
   OLNode* p;
   OLNode* q;

   //采用十字链表存储结构，创建稀疏矩阵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))))
   {
      printf("Error\n");         
   }
   if(!(M->col_head=(OLink*)malloc((n+1)*sizeof(OLink))))
   {
      printf("Error\n");                                            
   }
   
   //初始化行头指针向量，各行链表为空的链表
   for(int h=0; h<m+1; h++)
   {
      M->row_head[h] = NULL;        
   }
   //初始化列头指针向量，各列链表为空的链表
   for(int t=0; t<n+1; t++)
   {
      M->col_head[t] = NULL;        
   }
   
   for(scanf("%d%d%d", &i, &j, &e); i!=0; scanf("%d%d%d",&i, &j, &e))
   {
      if(!(p = (OLNode*)malloc(sizeof(OLNode))))
      {
         printf("Error\n");  
      }              
      //生成节点
      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;
      }
   }
}