数据结构 5.10 三元组顺序表

void FastTransposeSMatrix(TSMatrix M TSMatrix &T)

{

//采用三元组顺序表存储表示求稀疏矩阵M的转置矩阵T

Trows = Mcols;

Tcols = Mrows;

Tterms = Mterms;

if (Tterms) {

for (col=; col<=M cols; ++col)

num[col] = ;

for (t=; t<=M terms; ++t)

++num[Mdata[t]j];//求M中每一列所含非零元的个数

rpos[] = ;

for (col=; col<=M cols; ++col)

rpos[col] = rpos[col] + num[col];

//求T中每一行的第一个非零元在Tdata中的序号

for (p=; p<=Mterms; ++p) {//转置矩阵元素

col = Mdata[p]j; q = rpos[col];

Tdata[q]i =Mdata[p]j;

Tdata[q]j =Mdata[p]i;

Tdata[q]e =Mdata[p]e;

++rpos[col];

}//for

}//if

}//FastTransposeSMatrix

上述算法的时间复杂度为O (Mcols+Mterms)