稀疏矩阵的快速转置.cpp

实现了循环便利一棵树

#define MaxSize 20
#include <stdio.h>
typedef struct { int i, j;  int e; } Triple;
typedef struct
{ Triple data[MaxSize+1];
  int mu, nu, tu;
} TSMatrix;

void main()
{  TSMatrix M,T;
   int a,b,c,p,x,y;
   a=b=c=x=y=0; p=1;
   M.mu=M.nu=M.tu=0;
   void FastTransposeSMatrix(TSMatrix M, TSMatrix &T);
   void print(TSMatrix M);
   printf("请输入要转置的矩阵的行数与列数(输入格式为：行数,列数)：\n");
   scanf("%d,%d",&x,&y);
   M.mu=x;M.nu=y;
   printf("请按照三元表顺序输入(输入格式为：行值,列值,数值，(0,0,0 结束输入))：\n");
   while(p<MaxSize)
   { scanf("%d,%d,%d",&a,&b,&c);
     if(c==0) break;
     M.data[p].i=a;
     M.data[p].j=b;
     M.data[p].e=c;
     M.tu+=1;
     p+=1;
   }//求出M的相关信息
   FastTransposeSMatrix(M,T);
   printf("原矩阵为：\n");
   print(M);
   printf("转置后为：\n");
   print(T);
}

void FastTransposeSMatrix(TSMatrix M, TSMatrix &T)
{  int t,col,p,q;
   int num[MaxSize],cpot[MaxSize];
   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];//求M中每一列含非零元个数
     cpot[1]=1;
	  //求第col列中第一个非零元在M.data中的序号
     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];
     }//for
   }//if
}

void print(TSMatrix M)
{  int p,q,s;
   for(s=1,p=1;p<=M.mu;p++)
   {  if(M.data[s].i==p)
      { for(q=1;q<=M.nu;q++)
		   if(M.data[s].j==q&&M.data[s].i==p)
	          printf("%d  ",M.data[s].e),s+=1;
	       else printf("0  ");
        printf("\n");
      }
      else  { for(q=0;q<M.nu;q++) printf("0  ");
              printf("\n");
			}
   }
}