#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 12500
#define OK 1
typedef int ElemType;
typedef struct
{
int i,j;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int mu,nu,tu;   //矩阵行数，列数和非0元个数
}TSMatrix;
int cpot[MAXSIZE+1],num[MAXSIZE+1];
int TransposeSMatrix(TSMatrix M,TSMatrix &T)
{
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
  {
   int q=1;
   for(int col=1;col<=M.nu;++col)
          for(int 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;
                 }//if
  }//if
return OK;
}//TransposeSMatrix
int InPutM(TSMatrix &M)
{
printf("input nu mu tu(With a space interval)of a Matrix:\n");
scanf("%d %d %d",&M.nu,&M.mu,&M.tu);  //row,colume,and tu
printf("Please input the data of Matrix:\n");
for(int c=1;c<=M.tu;c++)
   {
    scanf("%d",&M.data[c].i);
       scanf("%d",&M.data[c].j);
       scanf("%d",&M.data[c].e);
   }//for
return 1;
}//InPut
int PrintM(TSMatrix T)
{
printf("Matrix after transpose is:\n");
for(int c=1;c<=T.tu;c++)
   {
    printf("%d %d %d\n",T.data[c].i,T.data[c].j,T.data[c].e);
   }//for
return 1;
}//InPut
int FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
  {
  for(int col=1;col<=M.mu;++col) num[col]=0;
  for(int t=1;t<=M.tu;++t) ++num[M.data[t].j]; //记述M.data[t].j列
                                          //非0元的个数
  cpot[1]=1;
  //求第col列中第一个非零元在b.data(T)中的序号
  for(int col=2;col<=M.mu;++col)
         cpot[col]=cpot[col-1]+num[col-1];
  for(int p=1;p<=M.tu;++p)
         {
            int col=M.data[p].j;
          int q=cpot[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;
         ++cpot[col];
      }//for
  }//if
return OK;
}//FastTransposeSMatrix
int main()
{
TSMatrix M,T;
InPutM(M);
//TransposeSMatrix(M,T);
FastTransposeSMatrix(M,T);
PrintM(T);
return OK;
}