两个十字链表相加

#define OVERFLOW -1

//------------稀疏矩阵的十字链表存储表示--------------
typedef struct OLNode{
 int i,j;  //该非零元的行和列下标
 int e;   //非零元
 struct OLNode * right, * down; // right指向该非零元所在行的右边的非零元，down指向下面的非零元
}OLNode, * OLink;
typedef struct {
 OLink * rhead, * chead; //rhead指向一个一维数组，里面存放每个行链表的头结点；chead指向一个一维数组，里面存放每个列链表的头结点
 int mu,nu,tu;  //稀疏矩阵的行数，列数，非零元个数
}CrossList;

#include "iostream"
#include "cstdio"
#include "cstdlib"

void CreateSMatrix_OL( CrossList &M )
{  //创建稀疏矩阵M;用十字链表存储
 printf("----------请依次输入稀疏矩阵M的  行数、列数、非零元个数 （空格隔开）---------\n");
 scanf("%d%d%d",&M.mu, &M.nu, &M.tu ); //输入M的行数、列数、非零元个数
 if( !(M.rhead = (OLink *)malloc( (M.mu+1) * sizeof(OLink) )))    exit(OVERFLOW); //给rhead分配一个一维数组，失败则退出程序
 if( !(M.chead = (OLink *)malloc( (M.nu+1) * sizeof(OLink) )))    exit(OVERFLOW); //给chead分配一个一维数组，失败则退出程序
 
 int x;
 for(x =1 ; x <= M.mu; x++) M.rhead[x] = NULL; //初始化rhead指向的一维数组个元素都为空，即每个行链表都为空
 for(x =1 ; x <= M.nu; x++) M.chead[x] = NULL;

 int i,j,e;
 OLNode * p,* q;
 int cnt_e;//用来统计非零元个数
 printf("--------下面输入%d行，每行三个数： 行标   列标  元素的值（空格隔开）--------\n",M.mu);
 for(cnt_e = 1; cnt_e <= M.tu ; cnt_e++){
  scanf("%d%d%d",&i,&j,&e);
  if( !(p = (OLNode *)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元
  p->i = i; p->j = j;  p->e = e;

  if( M.rhead[i] == NULL || M.rhead[i]->j > j) { p->right = M.rhead[i]; M.rhead[i] = p;}
  else{ //寻找新非零元在航标中的插入位置
   for( q = M.rhead[i] ; (q->right)&&(q->right->j < j); q = q->right )  ; //循环到合适位置，这是个空循环
   p->right = q->right; q->right = p; //完成行插入
   
  }//else

  if( M.chead[j] == NULL || M.chead[j]->i > i) { p->down = M.chead[j]; M.chead[j] = p;}
  else{ //寻找新非零元在列标中的插入位置
   for( q = M.chead[j] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环
   p->down = q->down; q->down = p; //完成列插入
  }//else
 }//for
 return;
 }
void PrintSMatrix_OL( CrossList M )
{
 OLNode * pr;
 int cnt_r,cnt_c;//控制行和列
 printf("---------------------------- 稀疏矩阵 ------------------------\n");
 for( cnt_r =1; cnt_r <= M.mu; cnt_r++ ){  //控制行
  pr = M.rhead[cnt_r]; //pr指向每一行的链表
  for( cnt_c = 1; cnt_c<= M.nu ;cnt_c++){ //控制咧
   if( NULL == pr )  printf("= ",0); //该行是空行
   else {//不是空行
    if(cnt_c == pr->j ) { printf("= ",pr->e); pr = pr->right;}
    else printf("= ",0);
   }//else
   //pr = M.rhead[cnt_r];
  }//for
  printf("\n");
 }//for
 return;
}

void AddSMatrix_OL(CrossList M1,CrossList M2,CrossList &M)
{
 //创建空稀疏矩阵M
 M.mu = M1.mu;  M.nu = M1.nu;   M.tu = 0;
 if( !(M.rhead = (OLink *)malloc( (M.mu+1) * sizeof(OLink) )))    exit(OVERFLOW); //给rhead分配一个一维数组，失败则退出程序
 if( !(M.chead = (OLink *)malloc( (M.nu+1) * sizeof(OLink) )))    exit(OVERFLOW); //给chead分配一个一维数组，失败则退出程序
 int x;
 for( x =1 ; x <= M.mu; x++) M.rhead[x] = NULL; //初始化rhead指向的一维数组个元素都为空，即每个行链表都为空
 for( x =1 ; x <= M.nu; x++) M.chead[x] = NULL;

 //相加
 int i,j,e,cnt_r;
 OLNode * p1,*p2,*p,*q;
 for( cnt_r=1; cnt_r<=M.mu; cnt_r++) // 按行的顺序相加
     {
         p1=M1.rhead[cnt_r];    // p1指向矩阵M1的第i行的第1个结点
         p2=M2.rhead[cnt_r];    // p2指向矩阵N2的第i行的第1个结点
         while(p1&&p2)    // p1和p2均不空
         {
             if(p1->j < p2->j) // 矩阵M当前结点的列小于矩阵N当前结点的列
             {
                if( !(p = (OLNode *)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元
                 i = p1->i;   j = p1->j;   e = p1->e;
                 p->i = i;        p->j = j;        p->e= e;// 给结点赋值
    
     //p结点插入M
                if( M.rhead[i] == NULL || M.rhead[i]->j > j) { p->right = M.rhead[i]; M.rhead[i] = p;}
    else{ //寻找新非零元在航标中的插入位置
     for( q = M.rhead[i] ; (q->right)&&(q->right->j < j); q = q->right )  ; //循环到合适位置，这是个空循环
     p->right = q->right; q->right = p; //完成行插入
     
    }//else
    if( M.chead[j] == NULL || M.chead[j]->i > i) { p->down = M.chead[j]; M.chead[j] = p;}
    else{ //寻找新非零元在列标中的插入位置
     for( q = M.chead[j] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环
     p->down = q->down; q->down = p; //完成列插入
    }//else

    M.tu++;    // 非零元素数加1
    p1 = p1->right;

             }
             else if(p1->j > p2->j )// 矩阵M当前结点的列大于矩阵N当前结点的列
             {
                 if( !(p = (OLNode *)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元
                 i = p2->i;   j = p2->j;   e = p2->e;
                 p->i = i;        p->j = j;        p->e= e;// 给结点赋值

                if( M.rhead[i] == NULL || M.rhead[i]->j > j) { p->right = M.rhead[i]; M.rhead[i] = p;}
    else{ //寻找新非零元在航标中的插入位置
     for( q = M.rhead[i] ; (q->right)&&(q->right->j < j); q = q->right )  ; //循环到合适位置，这是个空循环
     p->right = q->right; q->right = p; //完成行插入
    }//else
    if( M.chead[j] == NULL || M.chead[j]->i > i) { p->down = M.chead[j]; M.chead[j] = p;}
    else{ //寻找新非零元在列标中的插入位置
     for( q = M.chead[j] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环
     p->down = q->down; q->down = p; //完成列插入
    }//else

    M.tu++;    // 非零元素数加1
                p2=p2->right; // p2指针向右移
             }
          
             else if(p1->e + p2->e)  // 矩阵M、N当前结点的列相等且两元素之和不为0
             {
                 if( !(p = (OLNode *)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元
                 i = p1->i;   j = p1->j;   e = p1->e +p2->e;
                 p->i = i;        p->j = j;        p->e= e;// 给结点赋值

                if( M.rhead[i] == NULL || M.rhead[i]->j > j) { p->right = M.rhead[i]; M.rhead[i] = p;}
    else{ //寻找新非零元在航标中的插入位置
     for( q = M.rhead[i] ; (q->right)&&(q->right->j < j); q = q->right )  ; //循环到合适位置，这是个空循环
     p->right = q->right; q->right = p; //完成行插入 
    }//else
    if( M.chead[j] == NULL || M.chead[j]->i > i) { p->down = M.chead[j]; M.chead[j] = p;}
    else{ //寻找新非零元在列标中的插入位置
     for( q = M.chead[j] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环
     p->down = q->down; q->down = p; //完成列插入
    }//else

                 p1 = p1->right; // p1指针向右移
                 p2 = p2->right; // p2指针向右移
     M.tu++; // 非零元素数加1
             }
             else  {// 矩阵M、N当前结点的列相等且两元素之和为0
                 p1=p1->right; // p1指针向右移
                 p2=p2->right; // p2指针向右移
             }

         }//while
   
   while(p1) // 将矩阵M该行的剩余元素插入矩阵Q
         {
             if( !(p = (OLNode *)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元
            
             i = p1->i;   j = p1->j;   e = p1->e ;
             p->i = i;        p->j = j;        p->e= e;// 给结点赋值

             if( M.rhead[i] == NULL || M.rhead[i]->j > j) { p->right = M.rhead[i]; M.rhead[i] = p;}
      else{ //寻找新非零元在航标中的插入位置
    for( q = M.rhead[i] ; (q->right)&&(q->right->j < j); q = q->right )  ; //循环到合适位置，这是个空循环
     p->right = q->right; q->right = p; //完成行插入 
   }//else
   if( M.chead[j] == NULL || M.chead[j]->i > i) { p->down = M.chead[j]; M.chead[j] = p;}
   else{ //寻找新非零元在列标中的插入位置
    for( q = M.chead[j] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环
     p->down = q->down; q->down = p; //完成列插入
   }//else
             p1 = p1->right; // p1指针向右移
   M.tu++; // 非零元素数加1
         }
         while(p2) // 将矩阵N该行的剩余元素插入矩阵Q
         {
             if( !(p = (OLNode *)malloc(sizeof(OLNode) )))  exit(OVERFLOW); //分配一个临时结点，存放新接受的非零元
             i = p2->i;  j = p2->j;      e = p2->e;
             p->i = i;         p->j = j;          p->e= e;// 给结点赋值

             if( M.rhead[i] == NULL || M.rhead[i]->j > j) { p->right = M.rhead[i]; M.rhead[i] = p;}
   else{ //寻找新非零元在航标中的插入位置
    for( q = M.rhead[i] ; (q->right)&&(q->right->j < j); q = q->right )  ; //循环到合适位置，这是个空循环
     p->right = q->right; q->right = p; //完成行插入 
   }//else
   if( M.chead[j] == NULL || M.chead[j]->i > i) { p->down = M.chead[j]; M.chead[j] = p;}
   else{ //寻找新非零元在列标中的插入位置
    for( q = M.chead[j] ; (q->down)&&(q->down->i < i); q = q->down ) ;  //循环到合适位置，这是个空循环
     p->down = q->down; q->down = p; //完成列插入
   }//else
             p2=p2->right; // p1指针向右移
    M.tu++; // 非零元素数加1      
         } //while
     }//for
 
 return;
}
int main ()
{
 //freopen("Debug\\input.txt", "r", stdin);
// freopen("Debug\\output.txt", "w", stdout);

 CrossList M1,M2,M; //定义一个稀疏矩阵M
 CreateSMatrix_OL(M1); //创建稀疏矩阵M;用十字链表存储
 PrintSMatrix_OL(M1);

 CreateSMatrix_OL(M2); //创建稀疏矩阵M;用十字链表存储
 PrintSMatrix_OL(M2);

 AddSMatrix_OL(M1,M2,M); // 稀疏矩阵M1,M2相加结果为M
 PrintSMatrix_OL(M);
 
 system("pause");
 return 0;
}