#include <stdio.h>
#include <stdlib.h>
#define maxsize 10000     /*假设非零元个数的最大值为10000*/
typedef struct
{  
    int i,j;      /*该非零元的行下标和列下标*/
    int e;
}Triple;
typedef struct
{
    Triple data[maxsize+1];
    int mu,nu,tu;
}TSMatrix;
TSMatrix * create(TSMatrix *M)
{
      int i;
      int a,b,c;
      printf("分别输入矩阵的行数和列数以及非零元素的个数：\n");
      scanf("%d %d %d",&a,&b,&c);
      M->mu=a;
      M->nu=b;
      M->tu=c;
      printf("输入矩阵中的三元组:\n");

      for(i=1;i<=M->tu;i++)
      {
        scanf("%d",&M->data[i].i);
        scanf("%d",&M->data[i].j);
        scanf("%d",&M->data[i].e);
      }         
      return M;
}
TSMatrix * fasttrans(TSMatrix * M,TSMatrix * T)
{
    int col;
    int t,p,q;
    int num[100];
    int cpot[100];
    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++)
            ++num[M->data[t].j];    /*每一列的非零元的个数*/
        cpot[1]=1;
        for(col=2;col<=M->nu;col++)
            cpot[col]=cpot[col-1]+num[col-1];     /*每一列中的第一个非零元在转置矩阵中的位置*/
        for(p=1;p<=M->tu;++p)
        {
            col=M->data[p].j;
            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];
        }
    }
    return T;
}
    void main()
   {
          TSMatrix *M,*T;
          int m;
          M=(TSMatrix *)malloc(sizeof(TSMatrix));
          T=(TSMatrix *)malloc(sizeof(TSMatrix));
           M=create(M);
          printf("原来的三元组为: \n");
          for(m=1;m<=M->tu;m++)
          {
              printf("%d ",M->data[m].i);
              printf("%d ",M->data[m].j);
              printf("%d\n ",M->data[m].e);
          }      
              T=fasttrans(M,T);
              printf("转置后的三元组为：\n");
          for(m=1;m<=T->tu;m++)
            {
              printf("%d\n ",T->data[m].i);
              printf("%d\n",T->data[m].j);
              printf("%d\n ",T->data[m].e);
            }      
     }