十字链表的定义及C语言描述

时间:2022-01-06 11:12:16

十字链表常用于表示稀疏矩阵,可视作稀疏矩阵的一种链式表示,因此,这里以稀疏矩阵为背景介绍十字链表。不过,十字链表的应用远不止稀疏矩阵,一切具有正交关系的结构,都可用十字链表存储。

1、存储方式

(a)稀疏矩阵中每个非0元素对应一个十字链表结点,每个结点的结构为

十字链表的定义及C语言描述

其中各字段的含意为:
row
──元素在稀疏矩阵中的行号
col
──元素在稀疏矩阵中的列号
val
──元素值
down
──指向同列中下一个非0元素结点
right
──指向同行中下一个非0元素结点

(b)每行/列设一个表头结点(结构同元素结点),以down/right为链构成循环链表,即第i列头结点的down指向该列上第1个非0元素,第i行头结点的right指向该行第1个非0元素。第i/行上最后一个结点的down/right指向该列/行的头结点。若某列/行中无非0元素,则令它的头结点down/right域指向自己。
      (c)
设一个总头结点(结构同元素结点),令总头结点和各个列/行头结点用val字段,按列/行序构成一个循环单链表。

(d)可令总头结点的rowcolval分别表示矩阵的最大行号、列号与非0元素个数,而down/right指向第1/行的头结点。该总头结点可作为整个十字链表的代表。

 (e)由于行与列的头结点分别使用right域与down(不同时使用),故第i列与第i行头结点可合用同一个头结点(对所有可能的i),以节省存储空间。
 (f)
有时,为了快速访问行/列头结点,设置一个一维数组headNodes[],使headNodes[i]指向i/列的头结点。但这并不是必须的,因为各行/列的头结点已形成了一个循环单链表,故若已知十字链表总头结点,即可搜索到任一头结点。

设有一个如下形式的矩阵,它所对应的十字链表如下图所示。

 十字链表的定义及C语言描述

十字链表的定义及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, i, j, e; 
  OLNode* p; 
  OLNode* q; 
  /*采用十字链表存储结构,创建稀疏矩阵M*/ 
  scanf("%d%d%d", &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); 
  /*初始化行、列头指针向量,各行、列链表为空的链表*/ 
  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)))) 
  exit(OVERFLOW); 
  p->row=i; 
  p->col=j; 
  p->value=e; /*生成结点*/ 
  if(M->row_head[i]==NULL) 
  M->row_head[i]=p; 
  p->right=NULL; 
  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; 
  p->down=NULL; 
  else 
  { 
  /*寻找列表中的插入位置*/ 
  for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down); /*空循环体*/ 
  p->down=q->down; 
  q->down=p; /*完成插入*/ 
  } 
  } 
  }