算法5.5.txt

数据结构课件

MLink AddMat (Ha,Hb)
 MLink Ha,Hb;
{  Mnode  *p,*q,*pa,*pb,*ca,*cb,*qa;
   if (Ha->row!=Hb->row || Ha->col!=Hb->col) return NULL;
   ca=Ha->v_next.next; /*ca初始指向A矩阵中第一行表头结点*/
   cb=Hb->v_next.next; /*cb初始指向B矩阵中第一行表头结点*/
   do { pa=ca->right;  /*pa指向A矩阵当前行中第一个结点*/
       qa=ca;  /*qa是pa的前驱*/
             pb=cb->right;  /*pb指向B矩阵当前行中第一个结点*/
       while (pb->col!=0)  /*当前行没有处理完*/
        {
          if  (pa->col < pb->col && pa->col !=0 ) /*第三种情况*/
            { qa=pa;
              pa=pa->right;
            }
          else
            if (pa->col > pb->col || pa->col ==0 ) /*第四种情况*/
              {p=malloc(sizeof(MNode));
               p->row=pb->row; p->col=pb->col; p->v=pb->v;
               p->right=pa;qa->right=p; /* 新结点插入*pa的前面*/
                  pa=p;
                      /*新结点还要插到列链表的合适位置，先找位置，再插入*/
               q=Find_JH(Ha,p->col); /*从列链表的头结点找起*/
               while(q->down->row!=0 && q->down->row<p->row)
                  q=q->down; 
               p->down=q->down; /*插在*q的后面*/
               q->down=p;
               pb=pb->right;
              } /* if */
            else /*第一、二种情况*/
              {x= pa->v_next.v+ pb->v_next.v;
               if (x==0)  /*第二种情况*/
                { qa->right=pa->right;  ./*从行链中删除*/
                     /*还要从列链中删除，找*pa的列前驱结点*/
q= Find_JH (Ha,pa->col); /*从列链表的头结点找起*/
                  while ( q->down->row < pa->row  )
                     q=q->down; 
                  q->down=pa->down;
                  free (pa);
                  pa=qa;
                 } /*if (x==0)*/
                else  /*第一种情况*/
{ pa->v_next.v=x;
                       qa=pa;
                      } 
               pa=pa->right;
               pb=pb->right;
             }
         } /*while*/
       ca=ca->v_next.next;  /*ca指向A中下一行的表头结点*/
       cb=cb->v_next.next;  /*cb指向B中下一行的表头结点*/
     } while (ca->row==0)  /*当还有未处理完的行则继续*/
    return  Ha;
} 
算法5.5   十字链表表示的稀疏矩阵相加



为了保持算法的层次，在上面的算法，用到了一个函数findjH。
函数Mlink  Find_JH(MLink  H,  int j)的功能是：返回十字链表 H 中第j列链表的
头结点指针