/* bo5-3.c 行邏輯鏈接稀疏矩陣(存儲結構由c5-3.h定義)的基本操作(8個) */
 Status CreateSMatrix(RLSMatrix *M)
 { /* 創建稀疏矩陣M */
   int i;
   Triple T;
   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",&T.i,&T.j,&T.e);
       k=0;
       if(T.i<1||T.i>(*M).mu||T.j<1||T.j>(*M).nu) /* 行、列超出范圍 */
         k=1;
       if(T.i<(*M).data[i-1].i||T.i==(*M).data[i-1].i&&T.j<=(*M).data[i-1].j) /* 沒有按順序輸入非零元素 */
         k=1;
     }while(k); /* 當輸入有誤,重新輸入 */
     (*M).data[i]=T;
   }
   for(i=1;i<=(*M).tu;i++) /* 計算rpos[] */
     if((*M).data[i].i>(*M).data[i-1].i)
       for(T.i=0;T.i<(*M).data[i].i-(*M).data[i-1].i;T.i++)
         (*M).rpos[(*M).data[i].i-T.i]=i;
   for(i=(*M).data[(*M).tu].i+1;i<=(*M).mu;i++) /* 給最后沒有非零元素的幾行賦值 */
     (*M).rpos[i]=(*M).tu+1;
   return OK;
 }

 void DestroySMatrix(RLSMatrix *M)
 { /* 銷毀稀疏矩陣M(使M為0行0列0個非零元素的矩陣) */
   (*M).mu=0;
   (*M).nu=0;
   (*M).tu=0;
 }

 void PrintSMatrix(RLSMatrix 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);
   for(i=1;i<=M.mu;i++)
     printf("第%d行的第一個非零元素是本矩陣第%d個元素\n",i,M.rpos[i]);
 }

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

 Status AddSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
 { /* 求稀疏矩陣的和Q=M+N */
   int k,p,q;
   if(M.mu!=N.mu||M.nu!=N.nu)
     return ERROR;
   (*Q).mu=M.mu;
   (*Q).nu=M.nu;
   (*Q).tu=0;
   M.rpos[M.mu+1]=M.tu+1; /* 為方便后面的while循環臨時設置 */
   N.rpos[N.mu+1]=N.tu+1;
   for(k=1;k<=M.mu;++k) /* 對于每一行，k指示行號 */
   {
     (*Q).rpos[k]=(*Q).tu+1;
     p=M.rpos[k]; /* p指示M矩陣第k行當前元素的序號 */
     q=N.rpos[k]; /* q指示N矩陣第k行當前元素的序號 */
     while(p<M.rpos[k+1]&&q<N.rpos[k+1])
     { /* M,N矩陣均有第k行元素未處理 */
       if(M.data[p].j==N.data[q].j) /* M矩陣當前元素和N矩陣當前元素的列相同 */
       {
         (*Q).data[(*Q).tu+1].e=M.data[p].e+N.data[q].e;
         if((*Q).data[(*Q).tu+1].e!=0)
         {
           ++(*Q).tu;
           (*Q).data[(*Q).tu].i=k;
           (*Q).data[(*Q).tu].j=M.data[p].j;
         }
         ++p;
         ++q;
       }
       else if(M.data[p].j<N.data[q].j)
       { /* M矩陣當前元素的列<N矩陣當前元素的列 */
         ++(*Q).tu;
         (*Q).data[(*Q).tu].e=M.data[p].e;
         (*Q).data[(*Q).tu].i=k;
         (*Q).data[(*Q).tu].j=M.data[p].j;
         ++p;
       }
       else /* M矩陣當前元素的列>N矩陣當前元素的列 */
       {
         ++(*Q).tu;
         (*Q).data[(*Q).tu].e=N.data[q].e;
         (*Q).data[(*Q).tu].i=k;
         (*Q).data[(*Q).tu].j=N.data[q].j;
         ++q;
       }
     }
     while(p<M.rpos[k+1]) /* M矩陣還有k行的元素未處理 */
     {
       ++(*Q).tu;
       (*Q).data[(*Q).tu].e=M.data[p].e;
       (*Q).data[(*Q).tu].i=k;
       (*Q).data[(*Q).tu].j=M.data[p].j;
       ++p;
     }
     while(q<N.rpos[k+1]) /* N矩陣還有k行的元素未處理 */
     {
       ++(*Q).tu;
       (*Q).data[(*Q).tu].e=N.data[q].e;
       (*Q).data[(*Q).tu].i=k;
       (*Q).data[(*Q).tu].j=N.data[q].j;
       ++q;
     }
   }
   return OK;
 }

 Status SubtSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
 { /* 求稀疏矩陣的差Q=M-N */
   int i;
   if(M.mu!=N.mu||M.nu!=N.nu)
     return ERROR;
   for(i=1;i<=N.tu;++i) /* 對于N的每一元素,其值乘以-1 */
     N.data[i].e*=-1;
   AddSMatrix(M,N,Q); /* Q=M+(-N) */
   return OK;
 }

 Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
 { /* 求稀疏矩陣乘積Q=M＊N。算法5.3 */
   int arow,brow,p,q,ccol,ctemp[MAXRC+1];
   if(M.nu!=N.mu) /* 矩陣M的列數應和矩陣N的行數相等 */
     return ERROR;
   (*Q).mu=M.mu; /* Q初始化 */
   (*Q).nu=N.nu;
   (*Q).tu=0;
   M.rpos[M.mu+1]=M.tu+1; /* 為方便后面的while循環臨時設置 */
   N.rpos[N.mu+1]=N.tu+1;
   if(M.tu*N.tu!=0) /* M和N都是非零矩陣 */
   {
     for(arow=1;arow<=M.mu;++arow)
     { /* 從M的第一行開始，到最后一行，arow是M的當前行 */
       for(ccol=1;ccol<=(*Q).nu;++ccol)
         ctemp[ccol]=0; /* Q的當前行的各列元素累加器清零 */
       (*Q).rpos[arow]=(*Q).tu+1; /* Q當前行的第1個元素位于上1行最后1個元素之后 */
       for(p=M.rpos[arow];p<M.rpos[arow+1];++p)
       { /* 對M當前行中每一個非零元 */
         brow=M.data[p].j; /* 找到對應元在N中的行號(M當前元的列號) */
         for(q=N.rpos[brow];q<N.rpos[brow+1];++q)
	 {
           ccol=N.data[q].j; /* 乘積元素在Q中列號 */
           ctemp[ccol]+=M.data[p].e*N.data[q].e;
         }
       } /* 求得Q中第arow行的非零元 */
       for(ccol=1;ccol<=(*Q).nu;++ccol) /* 壓縮存儲該行非零元 */
         if(ctemp[ccol])
         {
           if(++(*Q).tu>MAXSIZE)
             return ERROR;
           (*Q).data[(*Q).tu].i=arow;
           (*Q).data[(*Q).tu].j=ccol;
           (*Q).data[(*Q).tu].e=ctemp[ccol];
         }
     }
   }
   return OK;
 }

 Status TransposeSMatrix(RLSMatrix M,RLSMatrix *T)
 { /* 求稀疏矩陣M的轉置矩陣T */
   int p,q,t,col,*num;
   num=(int *)malloc((M.nu+1)*sizeof(int));
   (*T).mu=M.nu;
   (*T).nu=M.mu;
   (*T).tu=M.tu;
   if((*T).tu)
   {
     for(col=1;col<=M.nu;++col)
       num[col]=0;  /* 設初值 */
     for(t=1;t<=M.tu;++t) /* 求M中每一列非零元個數 */
       ++num[M.data[t].j];
     (*T).rpos[1]=1;
     for(col=2;col<=M.nu;++col) /* 求M中第col中第一個非零元在(*T).data中的序號 */
       (*T).rpos[col]=(*T).rpos[col-1]+num[col-1];
     for(col=1;col<=M.nu;++col)
       num[col]=(*T).rpos[col];
     for(p=1;p<=M.tu;++p)
     {
       col=M.data[p].j;
       q=num[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;
       ++num[col];
     }
   }
   free(num);
   return OK;
 }