对稀疏矩阵的十字链表的表示形式,进行插入一个非0节点

//对稀疏矩阵的十字链表的表示形式,进行插入一个非0节点

#define m0 100

#define n0 100

struct node

{

 int row,col; //行列下标

 int val;     //值

 node* down;  //指向同列的 下一个 元素

 node* right; //指向同行的 右边的元素

}

struct crosslist

{//十字链表

 node* chead[m0+1];  //col列 的 头指针列表

 node* rhead[n0+1];  //row行 的 头指针列表

 int m; //行?

 int n; //列?

 int t; //非0元素的个数

}

crosslist A;

void insert(crosslist &A,int i,int j,int x)

{//给十字链表A的(i,j)位置上设置为x

 node *s;

 node *p;

 node *q;

 p = NULL;

 q = A.rhead[i] ;//q指向第i行的第一个元素

 while(q&&(q->col<j))

 {//如果q存在,并且列比要插入的小,就继续向右移动

  p = q;   //p是上一个

  q = q->right;   //q是下一个

 }

 if((q==NULL)||(q->col>j))

 {//不管是把整行都遍历完了,还是没有遍历完就找到了正确的位置

  s = new node; //s为新增加了节点

  A.t++;

  s->row = i;

  s->col = j;

  s->val = x;

  if(p==NULL)

  {//说明i行原来就没有一个节点

   s->right = A.rhead[i]; //要循环回去

   A.rhead[i] = s;

  }

  else

  {

   s->right = q;

   p->right = s;

  }

  //调整j列上的位置

  p=NULL;

  q = A.chead[j];

  while(q&&(q->row<j))

  {

   p = q;

   q = q->down;

  }

  if(p == NULL)

  {//说明j列原来就没有一个元素

   s->down = A.chead[j];

   A.chead[j] = s;

  }

  else

  {

   s->down = q;

   p->down = s;

  }

 }

}