数组

数组

稀疏矩阵

• 结构定义

  #define MAXSIZE 50  /*非零元素的个数最多为1000*/
  #define ElementType int
  
  /*稀疏矩阵三元组表的类型定义*/
  typedef struct {
      int row, col; /*该非零元素的行下标和列下标*/
      ElementType e; /*该非零元素的值*/
  } Triple;
  
  typedef struct {
      int m, n, len;        /*矩阵的行数、列数和非零元素的个数*/
      Triple data[MAXSIZE + 1]; /* 非零元素的三元组表。data[0]未用*/
  } TSMatrix;

十字链表

• 结构定义

  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, OLNode nodes[], int m, int n, int len) {
      OLNode *p, *q;
      int i, j, k, e;
  
      M->m = m;
      M->n = n;
      M->len = len;
  
      //创建行头数组并初始化
      M->row_head = (OLink*)malloc((m+1)*sizeof(OLink));
      for (i = 1; i <= m; ++i) M->row_head[i] = NULL;
  
      //创建列头数组并初始化
      M->col_head = (OLink*)malloc((n+1)*sizeof(OLink));
      for (i = 1; i <= n; ++i) M->col_head[i] = NULL;
  
      //根据nodes数组里的每一个数据
      for (k = 0; k < len; ++k) {
          //生成新结点并填入数据
          p = (OLNode *)malloc(sizeof(OLNode));
          p->row = i = nodes[k].row;
          p->col = j = nodes[k].col;
          p->value = e = nodes[k].value;  
          p->right = p->down = NULL;
  
          //将新节点插入到行链表中
          if (M->row_head[i] == NULL) //如果行链表为空。
              M->row_head[i] = p;
          else {
              //寻找行表中的插入位置：工作指针q指向插入位置的前一个结点，然后插入
              for (q = M->row_head[i]; q->right != NULL && 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 {
              //寻找行表中的插入位置：工作指针q指向插入位置的前一个结点，然后插入
              for (q = M->col_head[j]; q->down != NULL && q->down->row < i; q = q->down);
              p->down = q->down;
              q->down = p;
          }
      }
  }