}
TSMatrix FastMultSMatrix_1(TSMatrix A,TSMatrix B)//三元组顺序表快速矩阵乘法之一
{
TSMatrixC;
intArpos[N] = {0}, Brpos[N] = {0};//分别存储矩阵A，B的每一行的第一个非零元素在三元组中的位置
intctemp[N] = {0};//存储正在处理的该行中每一列的乘积值，是一个累积的和值，作为矩阵C在该位置处元素的值
intarow, brow, ccol;
inti, p, q;
intta, tb;
C.mu= A.mu;
C.nu= B.nu;
C.tu= 0;
if(A.tu * B.tu != 0)//若C是非零矩阵
{
RPos(A,Arpos); //确定矩阵A的每一行的第一个非零元素在三元组顺序表中的位置
RPos(B,Brpos); //确定矩阵B的每一行的第一个非零元素在三元组顺序表中的位置
for(arow=1; arow<=A.mu; arow++)//对A进行逐行处理 ，即对C进行逐行处理
{
for(i=0; i
ctemp[i]= 0;
if(arow < A.mu) //处理A中第arow行的每一个非零元素，ta指示下一行第一个非零元素的位置
ta= Arpos[arow];
else //最后一行的下一行第一个非零元素的位置 当然是 A.tu
ta= A.tu;
for(p=Arpos[arow-1]; p
brow= A.data[p].y; //标出该元素的列号，在B中找到与它对应的行号
if(brow < B.mu)
tb= Brpos[brow];
else
tb= B.tu;
for(q=Brpos[brow-1]; q
{
ccol= B.data[q].y - 1;
ctemp[ccol]+= A.data[p].e * B.data[q].e;
}
}
for(ccol=0; ccol
{
if(ctemp[ccol] != 0)//压缩存储该行非零元
{
if(C.tu == MAXSIZE)
{
printf("三元组溢出！\n" );
exit(1);
}
C.data[C.tu].x= arow; //C的行数等于A的行数
C.data[C.tu].y=ccol + 1; //C的列数等于B的列数
C.data[C.tu++].e= ctemp[ccol]; //C的元素值等于A的行数ctemp[ccol]的累积值
}
}
}
}
returnC;
}
分析上述算法的时间复杂度有如下结果：确定矩阵的每一行的第一个非零元素在三元组顺序表中的位置的时间复杂度为O（A.tu+A.mu+B.tu+B.mu+），累加器ctemp初始化的时间复杂度为O（A.mu*B.nu），C的所有非零元素的时间复杂度为O（A.tu*B.tu/B.mu），进行压缩存储的时间复杂度为O（A.mu*B.tu），因此总的时间复杂度为O（A.mu*B.nu + A.tu*B.tu/B.mu）。当矩阵为稀疏矩阵时，这种算法的时间复杂度接近O（A.mu*B.nu），比经典算法要快。
还有一种快速矩阵乘法，它是先将矩阵B转置，这样矩阵A与B的列数就相同了，矩阵B的行数即矩阵C的列数。此种算法不需要设置数组ctemp[N]，只需直接计算该行对应列的元素乘积的总和即可得到矩阵C的值。此算法时间复杂度为O（A.mu*B.nu *MAX(ta,tb)），其中MAX(ta,tb)表示A矩阵和B的转置矩阵中每行非零元素个数的最大值。
算法通俗易懂，代码也很简洁。代码如下：
TSMatrix FastMultSMatrix_2(TSMatrix A,TSMatrix B)//三元组顺序表快速矩阵乘法之二
{
TSMatrixC;
intArpos[N] = {0}, Brpos[N] = {0};//分别存储矩阵A，B的每一行的第一个非零元素在三元组中的位置
intarow, brow, ccol;
inti, p, q, ta, tb;
C.mu= A.mu;
C.nu= B.nu;
C.tu= 0;
if(A.tu * B.tu != 0)//若C是非零矩阵
{
B= FastTransposeSMatrix(B); //求矩阵B的转置矩阵
RPos(A,Arpos); //确定矩阵A的每一行的第一个非零元素在三元组顺序表中的位置
RPos(B,Brpos); //确定矩阵B的每一行的第一个非零元素在三元组顺序表中的位置
for(arow=1; arow<=A.mu; arow++)//对A进行逐行处理 ，即对C进行逐行处理
{
ta= (arow < A.mu) ? Arpos[arow] : A.tu;
for(brow=1; brow<=B.mu; brow++)
{
C.data[C.tu].e= 0;
p= Arpos[arow-1];
tb= (brow < B.mu) ? Brpos[brow] : B.tu;
q= Brpos[brow-1];
while(p < ta && q < tb)
{
if(A.data[p].y < B.data[q].y)
p++;
elseif (A.data[p].y > B.data[q].y)
q++;
else
C.data[C.tu].e+= A.data[p++].e * B.data[q++].e; //C的元素值等于该行对应列的元素乘积的总和
}
if(C.data[C.tu].e != 0)
{
C.data[C.tu].x= arow;
C.data[C.tu++].y= brow;
}
}
}
}
returnC;
}