数据结构习题及答案

				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				     {
				      if(A.data[pa].i>B.data[pb].i)
				         {pb++;A.tu++;}
				      else if(A.data[pa].i				      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				        {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				            {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;
				}