對稀疏矩陣的十字連結清單的表示形式,進行插入一個非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;

  }

 }

}