5.22.c

部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)严蔚敏版的课后习题答案.专门提供给在anyview上运行,全部为通告代码

5.22④  假设系数矩阵A和B均以三元组表作为存储结构。
试写出满足以下条件的矩阵相加的算法：假设三元组表A
的空间足够大，将矩阵B加到矩阵A上，不增加A、B之外
的附加空间，你的算法能否达到O(m+n)的时间复杂度?其
中m和n分别为A、B矩阵中非零元的数目。

要求实现以下函数：
Status AddTSM(TSMatrix &A,TSMatrix B);
/* 将三元组矩阵B加到A上: A=A+B */

稀疏矩阵的三元组顺序表类型TSMatrix的定义：
typedef struct {
  int    i,j; // 行下标,列下标
  ElemType e; // 非零元素值
}Triple;
 
typedef struct  {
  Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用
  int mu,nu,tu; // 矩阵的行数、列数和非零元个数
}TSMatrix;
Status AddTSM(TSMatrix &A,TSMatrix B)
/* 将三元组矩阵B加到A上: A=A+B */
{
  int pa,pb,pc,add,k;
  k=A.tu;
  if(A.mu!=B.mu||A.nu!=B.nu) return ERROR;
  for(pa=1,pb=1;pa<=k&&pb<=B.tu;)
     {
      if(A.data[pa].i>B.data[pb].i)
         {pb++;A.tu++;}
      else if(A.data[pa].i<B.data[pb].i) pa++;
      else
        {
         if(A.data[pa].j==B.data[pb].j)
            {add=A.data[pa].e+B.data[pb].e;
             if(!add){pa++;pb++;A.tu--;}
             else{pa++;pb++;}
              }
         else if(A.data[pa].j>B.data[pb].j){pb++;A.tu++;}
         else pa++;
         }
      }
  if(B.tu>=pb) A.tu+=(B.tu-pb+1);               //到此以前都是计算非零元素个数
  for(pa=k,pb=B.tu,pc=A.tu;pa>=1&&pb>=1;)       //从最后的非零元素反向比较计算，生成新的三元组表
    {
     if(A.data[pa].i>B.data[pb].i)
        {A.data[pc]=A.data[pa];
         pc--;pa--;}
     else if(A.data[pa].i<B.data[pb].i)
        {A.data[pc]=B.data[pb];
         pc--;pb--;}
     else{
         if(A.data[pa].j>B.data[pb].j)
            {A.data[pc]=A.data[pa];
             pc--;pa--;}
         else if(A.data[pa].j<B.data[pb].j)
            {A.data[pc]=B.data[pb];
             pc--;pb--;}
         else{    
             add=A.data[pa].e+B.data[pb].e;
             if(add){A.data[pc].e=add;
                     A.data[pc].i=A.data[pa].i;
                     A.data[pc].j=A.data[pa].j;
                     pc--;pa--;pb--;}
             else{pa--;pb--;}
             }
         }
     }
  while(pa>=1){A.data[pc]=A.data[pa];
               pc--;pa--;}
  while(pb>=1){A.data[pc]=B.data[pb];
               pc--;pb--;}
  return OK;
}