稀疏矩阵十字链表的储存形式（十字链表的创建与相加）

矩阵十字链表的储存形式（十字链表的创建与相加）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
    int i,j;
    int elem;
    struct node *right,*down;
}cnode,*clink;
typedef struct
{
    clink *rhead,*chead;  //这个的确是指针的指针，一维只要一维指针，二维需要指针的指针来定位
    int m,n,len;
}clist;
void createcrosslist(clist *xx,int p,int q,int t)
{
   int cnt;
   int x1,x2,x3;
   cnode* yy;
   clink zz;
   int iii;
   xx->m=p;
   xx->n=q;
   xx->len=t;
   if(!(xx->rhead=(clink *)malloc((p+2)*sizeof(clink))))//三重平面理解，之前的链表是二重平面，在函数里，因为->的出现，所以三重变四重，二重变三重
   exit(0);
   if(!(xx->chead=(clink *)malloc((q+2)*sizeof(clink))))
   exit(0);
   for(cnt=0;cnt<=p;cnt++)//这样既处理了可能有0行0列的问题
   {
       xx->rhead[cnt]=NULL;
   }
   for(cnt=0;cnt<=q;cnt++)
   {
      xx->chead[cnt]=NULL;
   }
   for(iii=0;iii<t;iii++)
   {
     scanf("%d%d%d",&x1,&x2,&x3);
     if(!(yy=(cnode *)malloc(sizeof(cnode))))//因为->操作，指针变量和非指针变量都是要让其变成指针的
     exit(0);
     yy->i=x1,yy->j=x2,yy->elem=x3;
     yy->right=NULL;yy->down=NULL;
     if(xx->rhead[x1]==NULL||xx->rhead[x1]->j>yy->j)    //创建的时候只要考虑是否为空和rhead->j与yy->j比
     {
         yy->right=xx->rhead[x1];
         xx->rhead[x1]=yy;  //插在头上。插头手法，get。 原理就是头指针前移。
     }
     else
     {                     //这步也是为了保护头结点。
          zz=xx->rhead[x1];//zz是被赋值的，所以不必在设为指针变量，这里指指针的指针，也就是要用点的话就指针化，转成用->
          while((zz->right!=NULL)&&(zz->right->j<x2))
          zz=zz->right;
          yy->right=zz->right;
          zz->right=yy;
     }
      if(xx->chead[x2]==NULL||xx->chead[x2]->i>yy->i)
      {
         yy->down=xx->chead[x2];
         xx->chead[x2]=yy;
      }
      else
      {
          zz=xx->chead[x2];
          while((zz->down!=NULL)&&(zz->down->i<x1))
          zz=zz->down;
          yy->down=zz->down;
          zz->down=yy;
      }
   }
   return;
}
clink isexist(clist* a,clink p)
{
    int x1,x2;
    clink q;
    x1=p->i;
    x2=p->j;
    q=a->rhead[x1];
    while(q)
    {
        if(x2==q->j)//这里当然是从第一个找
        return q;
        else
        q=q->right;
    }                                     //return  0就是没有找到
    return NULL;
}
void insert(clist* a,clink p)            //插入与删除都是要利用头结点的,只是这个头结点没有赋值而已
{
    int x1,x2;
    clink zz;
    clink q;
    x1=p->i;
    x2=p->j;
    q=a->rhead[x1];                     //不能该变头结点的数据
    zz=(clink)malloc(sizeof(cnode));
    zz->i=x1;
    zz->j=x2;
    zz->elem=p->elem;                  //插到第一个比他大的数前面，
    zz->right=NULL;                    ////没有没数据的头结点，所以还要考虑插头的情况
    zz->down=NULL;                     //头插一个数 get
    if(q==NULL||q->j>x2)               //这行为空的情况,空就写==空更不会出错
    {
         zz->right=a->rhead[x1];
         a->rhead[x1]=zz;              // 因为是头指针的移动，所以不能用p,如果用p的话,a->head存的地址并不会改变
    }
    else
    {
            while(q->right)
            {
               if(q->right->j>x2)
               {
                   zz->right=q->right;
                   q->right=zz;
                   break;
               }
                q=q->right;
            }
            if(q->right==NULL)                      //尾接一个数
             q->right=zz;
                              //这里直接，不用判断q->j与zz->elem的大小关系，因为到这步，只有zz->elem大于q->j的情况。
    }
    q=a->chead[x2];                //关键
    if(q==NULL||q->i>x1)
    {
        zz->down=a->chead[x2];
        a->chead[x2]=zz;
    }
    else
    {                                //如果只有一个元素，直接跳出while，这是头结点的一个弊端
        while(q->down)              //进入这个else，第一个一定是小于x1的
        {
               if(q->down->i>x1)
              {
                zz->down=q->down;
                q->down=zz;
                break;
              }
                q=q->down;
        }
              if(q->down==NULL)  //如果到最后没有比他大的数，则插到最后
              q->down=zz;
    }
    return;
}
void Delete(clist* a,clink p)
{
    int x1,x2;
    clink q;
    x1=p->i;
    x2=p->j;
    q=a->rhead[x1];  //用q保留头结点 ,
    if(q->j==x2)
    {
        a->rhead[x1]=a->rhead[x1]->right;//删头结点，get.
        free(q);
    }
    else      //是从第二个开始
    {
        while(q->right->j!=x2)
        {
            q=q->right;
        }
        q->right=q->right->right;
    }
}
void print(clist* a)
{
    int k;
    clink p;
    for(k=0;k<=a->m;k++)
    {
        p=a->rhead[k];
        while(p)
        {
            printf("%d %d %d\n",p->i,p->j,p->elem);
            p=p->right;
        }
    }
    return;
}
void addcrosslist(clist* a,clist* b)//利用链表的插入与删除
{
   int k;
   clink p;
   clink pp=NULL;
   for(k=0;k<=b->m;k++)  //b->m是cnt类的，所以是小于号
   {
      p=b->rhead[k];
      while(p)          //每行用指针逐个后移
      {
          pp=isexist(a,p);
          if(!pp)        //如果不存在。
          insert(a,p);
          else
          {
              pp->elem+=p->elem;
              if(!pp->elem)
              Delete(a,pp);
          }
          p=p->right;
      }
   }
   return;
}
int main()
{
    int p,q;
    clist a,b;
    scanf("%d%d",&p,&q);
    int t1,t2;
    scanf("%d%d",&t1,&t2);
    createcrosslist(&a,p,q,t1);
    createcrosslist(&b,p,q,t2);
    addcrosslist(&a,&b);
    print(&a);
    return 0;
}