/* bo5-2.c 三元組稀疏矩陣的基本操作,包括算法5.1(9個) */
 Status CreateSMatrix(TSMatrix *M)
 { /* 創建稀疏矩陣M */
   int i,m,n;
   ElemType e;
   Status k;
   printf("請輸入矩陣的行數,列數,非零元素數：");
   scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);
   (*M).data[0].i=0; /* 為以下比較順序做準備 */
   for(i=1;i<=(*M).tu;i++)
   {
     do
     {
       printf("請按行序順序輸入第%d個非零元素所在的行(1～%d),列(1～%d),元素值：",i,(*M).mu,(*M).nu);
       scanf("%d,%d,%d",&m,&n,&e);
       k=0;
       if(m<1||m>(*M).mu||n<1||n>(*M).nu) /* 行或列超出范圍 */
         k=1;
       if(m<(*M).data[i-1].i||m==(*M).data[i-1].i&&n<=(*M).data[i-1].j) /* 行或列的順序有錯 */
         k=1;
     }while(k);
     (*M).data[i].i=m;
     (*M).data[i].j=n;
     (*M).data[i].e=e;
   }
   return OK;
 }

 void DestroySMatrix(TSMatrix *M)
 { /* 銷毀稀疏矩陣M */
   (*M).mu=0;
   (*M).nu=0;
   (*M).tu=0;
 }

 void PrintSMatrix(TSMatrix M)
 { /* 輸出稀疏矩陣M */
   int i;
   printf("%d行%d列%d個非零元素。\n",M.mu,M.nu,M.tu);
   printf("行  列  元素值\n");
   for(i=1;i<=M.tu;i++)
     printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);
 }

 Status CopySMatrix(TSMatrix M,TSMatrix *T)
 { /* 由稀疏矩陣M復制得到T */
   (*T)=M;
   return OK;
 }

 int comp(int c1,int c2) /* 另加 */
 { /* AddSMatrix函數要用到 */
   int i;
   if(c1<c2)
     i=1;
   else if(c1==c2)
     i=0;
   else
     i=-1;
   return i;
 }

 Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)
 { /* 求稀疏矩陣的和Q=M+N */
   Triple *Mp,*Me,*Np,*Ne,*Qh,*Qe;
   if(M.mu!=N.mu)
     return ERROR;
   if(M.nu!=N.nu)
     return ERROR;
   (*Q).mu=M.mu;
   (*Q).nu=M.nu;
   Mp=&M.data[1]; /* Mp的初值指向矩陣M的非零元素首地址 */
   Np=&N.data[1]; /* Np的初值指向矩陣N的非零元素首地址 */
   Me=&M.data[M.tu]; /* Me指向矩陣M的非零元素尾地址 */
   Ne=&N.data[N.tu]; /* Ne指向矩陣N的非零元素尾地址 */
   Qh=Qe=(*Q).data; /* Qh、Qe的初值指向矩陣Q的非零元素首地址的前一地址 */
   while(Mp<=Me&&Np<=Ne)
   {
     Qe++;
     switch(comp(Mp->i,Np->i))
     {
       case  1: *Qe=*Mp;
                Mp++;
                break;
       case  0: switch(comp(Mp->j,Np->j)) /* M、N矩陣當前非零元素的行相等,繼續比較列 */
                {
                  case  1: *Qe=*Mp;
                           Mp++;
                           break;
                  case  0: *Qe=*Mp;
                           Qe->e+=Np->e;
                           if(!Qe->e) /* 元素值為0，不存入壓縮矩陣 */
                             Qe--;
                           Mp++;
                           Np++;
                           break;
                  case -1: *Qe=*Np;
                           Np++;
                }
                break;
       case -1: *Qe=*Np;
                Np++;
     }
   }
   if(Mp>Me) /* 矩陣M的元素全部處理完畢 */
     while(Np<=Ne)
     {
       Qe++;
       *Qe=*Np;
       Np++;
     }
   if(Np>Ne) /* 矩陣N的元素全部處理完畢 */
     while(Mp<=Me)
     {
       Qe++;
       *Qe=*Mp;
       Mp++;
     }
   (*Q).tu=Qe-Qh; /* 矩陣Q的非零元素個數 */
   return OK;
 }

 Status SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)
 { /* 求稀疏矩陣的差Q=M-N */
   int i;
   for(i=1;i<=N.tu;i++)
     N.data[i].e*=-1;
   AddSMatrix(M,N,Q);
   return OK;
 }

 Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)
 { /* 求稀疏矩陣的乘積Q=M*N */
   int i,j,h=M.mu,l=N.nu,Qn=0;
   /* h,l分別為矩陣Q的行、列值,Qn為矩陣Q的非零元素個數，初值為0 */
   ElemType *Qe;
   if(M.nu!=N.mu)
     return ERROR;
   (*Q).mu=M.mu;
   (*Q).nu=N.nu;
   Qe=(ElemType *)malloc(h*l*sizeof(ElemType)); /* Qe為矩陣Q的臨時數組 */
   /* 矩陣Q的第i行j列的元素值存于*(Qe+(i-1)*l+j-1)中，初值為0 */
   for(i=0;i<h*l;i++)
     *(Qe+i)=0; /* 賦初值0 */
   for(i=1;i<=M.tu;i++) /* 矩陣元素相乘，結果累加到Qe */
     for(j=1;j<=N.tu;j++)
       if(M.data[i].j==N.data[j].i)
         *(Qe+(M.data[i].i-1)*l+N.data[j].j-1)+=M.data[i].e*N.data[j].e;
   for(i=1;i<=M.mu;i++)
     for(j=1;j<=N.nu;j++)
       if(*(Qe+(i-1)*l+j-1)!=0)
       {
         Qn++;
         (*Q).data[Qn].e=*(Qe+(i-1)*l+j-1);
         (*Q).data[Qn].i=i;
         (*Q).data[Qn].j=j;
       }
   free(Qe);
   (*Q).tu=Qn;
   return OK;
 }

 Status TransposeSMatrix(TSMatrix M,TSMatrix *T)
 { /* 求稀疏矩陣M的轉置矩陣T。算法5.1 */
   int p,q,col;
   (*T).mu=M.nu;
   (*T).nu=M.mu;
   (*T).tu=M.tu;
   if((*T).tu)
   {
     q=1;
     for(col=1;col<=M.nu;++col)
       for(p=1;p<=M.tu;++p)
         if(M.data[p].j==col)
         {
           (*T).data[q].i=M.data[p].j;
           (*T).data[q].j=M.data[p].i;
           (*T).data[q].e=M.data[p].e;
           ++q;
         }
   }
   return OK;
 }