问题 1754 --算法5-3:行逻辑链接的矩阵乘法

1754: 算法5-3:行逻辑链接的矩阵乘法

时间限制: 1 Sec  内存限制: 32 MB
提交: 152  解决: 63
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][108kb]

题目描述

对于一个稀疏矩阵,当需要频繁的随机存取任意一行的非零元时,则需要知道每一行的第一个非零元在三元组表中的位置。为此,可以将算法5.2中用来指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。这种“带行链接信息”的三元组表即为行逻辑链接的顺序表。其类型描述如下:
针对存储于行逻辑链接顺序表的稀疏矩阵,其矩阵相乘的算法与经典算法有所不同。因此,对于两个稀疏矩阵相乘(Q=M×N)的过程可以大致描述如下:
请使用行逻辑链接的顺序表实现两个稀疏矩阵的乘法。

输入

输入的第一行是两个整数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]中的一部分,需要将其累加从而得到最终的结果。

另外需要注意的是,两个稀疏矩阵相乘的乘积并不一定是稀疏矩阵。

总结:

采用行逻辑链接的顺序表通过使用非零元的行信息,使稀疏矩阵的存储和使用效能进一步提高。尤其是对于稀疏矩阵相乘, 这种算法省去了非常多无谓的计算。

来源

[提交][状态]