#include<stdio.h>
#define MAX 40 /*非零元个数的最大值*/

typedef struct
{
 int i,j;/*非零元的行下标和列下标*/
 int e;/*该非零元的数值*/
}Triple;

typedef struct
{
 Triple data[MAX+1];/*非零元三元组表,data[0]未用*/
 int mu,nu,tu;/*矩阵的行数，列数，非零元的个数*/
 int rpos[MAX+1];/*各行第一个非零元的位置表*/
}Matrix;

/*稀疏矩阵的初始化函数*/
void InitMatrix(Matrix *W)
{ int i,p,num[MAX],rpos[MAX],r;
  printf("please input the number of row,col and fei ling yuan:\n");/*输入矩阵的行数，列数非零元的个数*/
  scanf("%d,%d,%d",&W-&gt;mu,&W-&gt;nu,&W-&gt;tu);
  printf("please input the data:\n");
  for(i=1;i<=W->tu;i++)/*输入矩阵的行号，列号和非零元的数值*/
    scanf("%d,%d,%d",&W-&gt;data[i].i,&W-&gt;data[i].j,&W-&gt;data[i].e);
/*求矩阵W各行第一个非零元在W.data中的位置*/
  for(r=1;r<=W->mu;r++)
     num[r]=0;/*初始化W每一行的非零元的个数为0*/
  for(p=1;p<=W->tu;p++)
     num[W-&gt;data[p].i]=num[W-&gt;data[p].i]+1;
   W-&gt;rpos[1]=1;
  for(r=2;r<=W->mu+1;r++)
     W-&gt;rpos[r]=W-&gt;rpos[r-1]+num[r-1];
}
/*将A转置为B的函数*/
void fasttrans(Matrix A,Matrix *B)
{
   int col,cpot[MAX],num[MAX],t,p,q;
  /*初始化矩阵B*/
   (*B).mu=A.nu;
   (*B).nu=A.mu;
   (*B).tu=A.tu;
   if(B-&gt;tu)
   {
      for(col=0;col<A.nu;++col)
        num[col]=0;/*初始化每一列非零元的个数*/
      for(t=1;t&lt;=A.tu;++t)
      ++num[A.data[t].j];/*计算每一列非零元的个数*/
      cpot[1]=1;
      for(col=2;col&lt;=A.nu;++col)
         cpot[col]=cpot[col-1]+num[col-1];/*计算矩阵A每一列第一个非零元在B.data中的位置*/
     /*实现对A中的每一个非零元进行转置*/
     for(p=1;p&lt;=A.tu;++p)
      {
  col=A.data[p].j;
  q=cpot[col];
  (*B).data[q].i=A.data[p].j;
  (*B).data[q].j=A.data[p].i;
  (*B).data[q].e=A.data[p].e;
  ++cpot[col];
      }
   }
}

/*用三元组表示的稀疏矩阵M和N相乘的函数*/
void MulMatrix(Matrix M,Matrix N,Matrix *Q)
{
   int t,p,q,tp,k,arow,brow,ccol,ctemp[MAX],num[MAX];
   if(M.nu!=N.mu)  printf("error");/*如果M矩阵的列数不等于N矩阵的行数输出错误信息*/
   /* 初始化Q的行数，列数和非零元的个数*/
   Q->mu=M.mu;
   Q-&gt;nu=N.nu;
   Q-&gt;tu=0;
   if(M.tu*N.tu!=0)/*如果Q是非零矩阵继续下面的运行*/
   {
      for(arow=1;arow<=M.mu;++arow)
      {
  for(k=1;k&lt;=M.mu;k++)
  ctemp[k]=0;/*将累加器清零*/
  Q->rpos[arow]=Q-&gt;tu+1;
  if(arow<M.mu) tp=M.rpos[arow+1];
  else {tp=M.tu+1;}
/*对当前行中每一个非零元找到对应元在N中的位置*/
  for(p=M.rpos[arow];p&lt;tp;++p)
  {
     brow=M.data[p].j;
     if(brow&lt;N.mu)  t=N.rpos[brow+1];
     else {t=N.tu+1;}
     for(q=N.rpos[brow];q&lt;t;++q)
     {
        ccol=N.data[q].j;/*乘积元在Q中的列号*/
        ctemp[ccol]+=M.data[p].e*N.data[q].e;
     }
  }/*求得Q中第arow行的非零元*/
  for(ccol=1;ccol&lt;=Q->nu;++ccol)
  if(ctemp[ccol])
  {  /*压缩存储该行的非零元*/
     if(++Q-&gt;tu&gt;MAX) printf("error");/*若Q中的非零元的个数超出最大范围输出错误的信息*/
     Q-&gt;data[Q-&gt;tu].i=arow;
     Q-&gt;data[Q-&gt;tu].j=ccol;
     Q-&gt;data[Q-&gt;tu].e=ctemp[ccol];
         }
      }
   }
/*求出Q中每一行非零元在Q.data中的位置*/
 for(t=1;t<=(*Q).tu;t++)
     ++num[(*Q).data[t].i];
   (*Q).rpos[1]=1;
   for(t=2;t&lt;=(*Q).mu;t++)
   (*Q).rpos[t]=(*Q).rpos[t-1]+num[t-1];
}

/* 矩阵的输出函数*/
void output(Matrix *P)
 {  int i,j,t,k=0;
      t=1;
    printf(" the array  is: \n");
    for(i=1;i&lt;=P->mu;i++)
     {for(j=1;j<=P->nu;j++)
      {  if(P-&gt;data[t].i==i&&P-&gt;data[t].j==j)
    { printf("%4d",P-&gt;data[t].e);t++;}
            else printf("%4d",k);
       }
      printf("\n");
    }
 }

void main( )
{ int i;
  Matrix A,B,C;/*定义Matrix类型的三个矩阵A，B，C*/
/*使用说明*/
  printf("1 mult array,A*B=C\n");
  printf("2 transpose array,A-&gt;B\n");
  printf("3 exit\n");
 while(1)
  { printf("please select item to operarting:");
    scanf("%d",&i);
    switch(i)/*用switch语句实现各种功能的转换*/
     { case 1: InitMatrix(&A);output(&A);InitMatrix(&B);output(&B);MulMatrix(A,B,&C);output(&C);break;
       case 2: InitMatrix(&A);output(&A);fasttrans(A,&B);output(&B);break;
       case 3: exit(0); break;
     }
  }
}