除了用三元组顺序表来存储压缩矩阵，我们还可以用链表结构来存储，实际上后者应用更广泛，因为当非零元素的数目较大时，三元组的时间复杂度实在太高。链表结构中最常见的是十字链表，在十字链表中，稀疏矩阵每一行用一个带头结点的循环链表表示，每一列也用一个带头结点的循环链表表示。在这个结构中，除头结点外，每个结点都代表矩阵中的一个非零元素，它由5个域组成：行域（row），列域（col），数据域（data），向下域（down）和向右域（right）。  为了使所有结点的存储结构一致，规定表头结点的结构与非零元素的结点完全一致，只是将其行域和列域设置为0，由于每一行链表的表头（行头）和每一列链表的表头（列头）的行域和列域的值均为0，故这两组表头结点可以共用，即同行号，同列号的行头和列头共同存储在一个结点中，只是将其逻辑分开（实际上行头使用该结点的向右域，而列头使用该结点的向下域），起到资源共享的效果。由此可知，稀疏矩阵的十字链表存储表示的结点总数等于非零元素的个数加上行头和列头（两者共用标号相同的结点，实际上只要提供其中的较大者的个数就可以了），再加上总表头Head[0]，其中总表头Head[0]的行域和列域分别存储矩阵的总行数和总列数，为节省空间，把矩阵非零元素的个数存储在Head[1]的行域。//------稀疏矩阵的十字链表存储表示-------------------#define MAXRC 100 //假设矩阵的行（列）数最多为100typedef struct matnode{ int row, col;  //结点的行域和列域 struct matnode *right, *down;//结点的向下域（down）和向右域（right）  union //结点的数据域，若为表头结点则无数值，而用指向其后继的指针代替  {  ElemType data;  struct matnode *next; } tag;} CrossNode, *CrossList;//---------------------------------------------------------------------------------创建一个十字链表void CreateHead(CrossList Head[], int len) //创建十字链表的表头结点 { CrossList p; int i;  p = (CrossList)malloc(sizeof(CrossNode)); if(!p) {  puts("Error");  exit(1); } Head[0] = p;  //生成总表头结点  for(i=1; i<=len; i++)//先初始化所有的行头（列头）  {  p = (CrossList)malloc(sizeof(CrossNode));  if(!p)  {   puts("Error");   exit(1);  }  Head[i] = p;  Head[i-1]->tag.next = p;//把表头结点按顺序连接起来   p->row = p->col = 0; //表头结点的行域和列域设置为0  p->down = p->rigth = p;//先将表头结点的行域和列域指向自身，以构成循环链表  } //for(i=1; i<=s; i++) Head[s]->tag.next = Head[0];//最后一个表头结点的后继为总表头，即构成循环链表 } void Insert(CrossList Head[], int r, int c, int v) //插入新的结点 {  CrossList q;     p = (CrossList)malloc(sizeof(CrossNode)); if(!p) {  puts("Error");  exit(1); } p->row = r; p->col = c; p->tag.data = v;   q = Head[r];   //完成行插入  while(q->right != Head[r] && q->right->col < c)  q = q->right; p->right = q->right; q->right = p;   q = Head[c]; //完成列插入  while(q->down != Head[c] && q->down->row < r)  q = q->down; p->down = q->down; q->down = p;}CrossList CreateSMatrix_OL(int m, int n) //创建一个十字链表{ int s; //非零元素个数t  int r, c, v;//分别表示元素的行号r,列号c，值v int t = 0; CrossList Head[MAXRC], p, q;  s = m>n ? m:n;//因为序号相同行头和列头共用一个结点，故只要分配s个表头结点就好了  CreateHead(Head, s);//创建十字链表的表头结点   puts("请按行序为主序依次输入矩阵的非零元素的行号，列号和元素值，每行输入一个元素的信息："); printf("注意行号不能超过%d,列号不能超过%d,否则结束输入\n", m, n); //生成结点  do {  scanf("%d%d%d", &r, &c, &v);  fflush(stdin);  if(r > 0 && r <= m && c > 0 && c <= n)   {   Insert(Head, r, c, v);    t++;  } } while(r > 0 && r <= m && c > 0 && c <= n) ; Head[0]->row = m; //总表头Head[0]的行域存储矩阵的总行数 Head[0]->col = n; //总表头Head[0]的列域存储矩阵的总列数 Head[1]->row = t; //非零元素的个数存储在Head[1]的行域  return Head[0]; //返回总表头结点 } void PrintCrossList(CrossList T)//输出十字链表存储矩阵{ int k = 0;  CrossList p, q; //p指向行头，q指向非零元素结点     printf("\n");  p = T->tag.next;  if(p == T) //如果非零元素个数不为零，存储其总行数和总列数    {   puts("非零元素个数为零");   exit(1);  }  while(p != T)  //按行表顺序，把十字链表中的元素写入二维数组   {  q = p->right;  while(q != p) //注意二维数组的下标从0开始，而十字链表的行，列号从1开始   {    printf("T%d (%d,%d,%d)\t", ++k, q->row, q->col, q->tag.data);    q = q->right;  }  p = p->tag.next; } printf("\n");}二维数组存储稀疏矩阵和十字链表的相互转换 CrossList ArrayToCrossList(const int A[][N], int m, int n)//二维数组转换为十字链表 { int s; int i, j, k=0; CrossList Head[MAXRC], p, q;    s = m>n ? m:n;//因为序号相同行头和列头共用一个结点，故只要分配s个表头结点就好了  CreateHead(Head, s);    for(i=0; i

评论