学步园

//对稀疏矩阵的十字链表的表示形式,进行插入一个非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;
  }
 }
}