#include"stdio.h"typedef struct{int i,j;int v;}Triple;typedef struct{Triple date[1000];int mu,nu,tu;//hang、lie}TSMatrix;void Trans(TSMatrix &T,TSMatrix &M){
   //将来会对M的值进行修改，而不会对T的值进行修改，所以M需要传递地址M.mu=T.nu;M.nu=T.mu;M.tu=T.tu;int l=1;for(int q=1;q

 

分析：在矩阵的转置中，是将T矩阵的列转为M矩阵的行，在M矩阵中，是以行顺序进行存储，所以，在转置时以T矩阵的列顺序遍历，找出每个T.date[p].j==q，p即在T矩阵中的位置。

改算法的时间复杂度是nu*tu，一般矩阵转置的算法复杂的为mu*nu，所以该算法仅适于tu<<mu*nu(别问我为什么不是tu<mu，我不知道，书上就是这样写的，欢迎指点)

快速转置：

#include"stdio.h"

#define MAX 1000

typedef struct{

int i,j;

int v;

}Triple;

typedef struct{

Triple date[MAX];

int mu,nu,tu;//hang、lie

}TSMatrix;

void Trans(TSMatrix &T,TSMatrix &M,int col){//将来会对M的值进行修改，而不会对T的值进行修改，所以M需要传递地址

//int num[col];　　//error C2057: expected constant expression 在定义num[col]时报错，查得col是个变量，一直要到运行期才被分配内存，才会有值，所以编译期的时候它还没有值，故而编译时会出错。

//int cpot[col];//所以设置宏，但是这明显不是最好的办法，如果有更好的方法请大家指点

int q=0;

int num[MAX];

int cpot[MAX];

M.mu=T.nu;

M.nu=T.mu;

M.tu=T.tu;

if(M.tu){

for(int col=1;col<T.mu+1;++col) num[col]=0;

for(int t=1;t<M.tu+1;++t) ++num[T.date[t].j];

cpot[1]=1;

for(int co=2;co<T.mu+1;++co) cpot[co]=cpot[co-1]+num[co-1];

for(int p=1;p<T.tu+1;++p){

col=T.date[p].j;

q=cpot[col];

M.date[q].i=T.date[p].j;

M.date[q].j=T.date[p].i;

M.date[q].v=T.date[p].v;

++cpot[col];

}

}

printf("转置后\n");

printf("i j v\n");

for(int k=1;k<M.tu+1;k++){

printf("%d %d %d\n",M.date[k].i,M.date[k].j,M.date[k].v);

}

}

int main(){

TSMatrix T,M;

T.date[1].i=1;T.date[1].j=2;T.date[1].v=12;T.date[2].i=1;T.date[2].j=3;T.date[2].v=9;T.date[3].i=3;T.date[3].j=1;T.date[3].v=-3;T.date[4].i=3;T.date[4].j=6;T.date[4].v=14;T.date[5].i=4;T.date[5].j=3;T.date[5].v=24;T.date[6].i=5;T.date[6].j=2;T.date[6].v=18;T.date[7].i=6;T.date[7].j=1;T.date[7].v=15;T.date[8].i=6;T.date[8].j=4;T.date[8].v=-7;

T.tu=8;

T.nu=6;

T.mu=6;

printf("转置前\n");

printf("i j v\n");

//printf("%d",T.tu);

for(int k=1;k<T.tu+1;k++){

printf("%d %d %d\n",T.date[k].i,T.date[k].j,T.date[k].v);

}

Trans(T,M,T.nu);

return 0;

}

分析：在转置中有亮点关键1、cpot[1]=1;cpot[co]=cpot[co-1]+num[co-1];这个表示的是各个行列中两个数组的关系，2、++cpot[col];窃以为这个才是整个代码的灵魂，cpot[col]表示col列第一个非零元在M矩阵中的位置，++cpot[col]则表示如果该列不止一个非零元，那++cpot[col]表示该列下个非零元的位置，如果没有下个非零元，则++cpot[col]不再使用。

该算法的时间复杂度是mu*nu