二、行逻辑链接的顺序表
算法 5.3bool MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q)
{
// 采用行逻辑链接存储表示，求矩阵乘积Q=M N。
if (M.Num_cols != N.Num_rows) return FALSE;
// M的列数和N的行数不等，不能相乘
if (M.tu*N.tu != 0) { // M和N中均含有非零元对矩阵Q进行初始化;
for (arow=1; arow<=M. rows; ++arow)
{
处理M(即Q)的每一行
} // 求得 Q 中第crow( =arow)行的非零元
for (ccol=1; ccol<=Q.nu; ++ccol)// 压缩存储该行非零元
if (ctemp[ccol-1]) {
if (++Q.terms > MAXTERMS)
return FALSE;
Q.data[Q.terms] = (arow, ccol, ctemp[ccol]);
} // if
} // for arow
} // if
return TRUE;
} // MultSMatrix
算法5.3的时间复杂度为O
(M.rows×N.cols+M.terms×N.terms/N.rows)。
其中，N.terms/N.rows
表示N中每一行非零元个数的平均值。
若 M 是 m 行 n 列的稀疏矩阵，N 是 n 行 p 列的稀疏矩阵，则M中非零元的个数 M.terms =
×m×n，N中非零元的个数
N.terms =×n×p，此时算法5.3的时间复杂度就是O
(m×p×(1+n
))
，当 <0.05
和 <0.05
及 n<1000时，算法5.3的时间复杂度就相当于O
(m×p)，显然，这是一个相当理想的结果。如果事先能估算出所求乘积矩阵 Q 非是稀疏矩阵，也可设它的存储结构为二维数组，此时的矩阵相乘算法更为简单，读者可自行试之。
其中：
对矩阵Q进行初始化的操作如下：
Q.rows = M.rows;// Q的行数和M相同
Q.cols = N.cols;// Q的列数和N相同
Q.terms = 0; // Q的非零元个数初始化为零
求得Q中一行非零元的操作为：
ctemp[] = 0; //
当前行各元素累加器清零
Q.rpos[arow] = Q.terms+1;
for(p=M.rpos[arow];p<M.rpos[arow+1];++p)
{ // 处理 M 当前行中每一个非零元
brow=M.data[p].j; //
找到对应元在N中的行号
for(q=N.rpos[brow];q<N.rpos[brow+1];++q)
{
ccol = N.data[q].j; //
乘积元素在Q中列号
ctemp[ccol-1]+=M.data[p].e * N.data[q].e;
} // for q
} // for p
算法5.3中，累加器ctemp初始化的时间复杂度为 (M.rows N.cols)，求Q的所有非零元的时间复杂度为 (M.terms N.terms/N.rows)，对Q进行压缩存储的时间复杂度为
(M.rows N.cols)。