对于一个稀疏矩阵，当需要频繁的随机存取任意一行的非零元时，则需要知道每一行的第一个非零元在三元组表中的位置。为此，可以将算法5.2中用来指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。这种“带行链接信息”的三元组表即为行逻辑链接的顺序表。其类型描述如下：
针对存储于行逻辑链接顺序表的稀疏矩阵，其矩阵相乘的算法与经典算法有所不同。因此，对于两个稀疏矩阵相乘(Q=M×N)的过程可以大致描述如下：
请使用行逻辑链接的顺序表实现两个稀疏矩阵的乘法。
2147: 算法5-3：行逻辑链接的矩阵乘法
时间限制: 1 Sec 内存限制: 32 MB提交: 2 解决: 2
[提交] [状态] [讨论版] [命题人:]
题目描述
输入
输入的第一行是两个整数r1和c1（r1<200, c1<200, r1*c1 <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r1行，每行有c1个整数，用空格隔开，表示第一个稀疏矩阵的各个元素。
之后的一行有两个整数r2和c2（c1=r2<200, c2<200, r2*c2 <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r2行，每行有c2个整数，用空格隔开，表示第二个稀疏矩阵的各个元素。
输出
输出两个矩阵的乘积。输出共有r1行，每行有c2个整数，每个整数后输出一个空格。请注意行尾输出换行。
样例输入
4 5
0 0 0 69 78
0 0 5 0 0
0 0 0 0 0
0 91 2 0 82
5 6
0 18 0 0 0 0
0 0 67 0 0 0
0 0 0 0 0 41
0 0 47 62 0 0
0 0 0 0 0 35
样例输出
0 0 3243 4278 0 2730
0 0 0 0 0 205
0 0 0 0 0 0
0 0 6097 0 0 2952
提示
提示：
对于稀疏矩阵M和N，其相乘的基本操作是：对于M中每个元素M.data[p](p=1,2,...,M.tu)，找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，从而求得M.data[p]与M.data[q]的乘积。需要注意的是，这个乘积只是Q[i][j]中的一部分，需要将其累加从而得到最终的结果。
另外需要注意的是，两个稀疏矩阵相乘的乘积并不一定是稀疏矩阵。
总结：
采用行逻辑链接的顺序表通过使用非零元的行信息，使稀疏矩阵的存储和使用效能进一步提高。尤其是对于稀疏矩阵相乘, 这种算法省去了非常多无谓的计算。