对于一个稀疏矩阵，当需要频繁的随机存取任意一行的非零元时，则需要知道每一行的第一个非零元在三元组表中的位置。为此，可以将算法5.2中用来指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。这种“带行链接信息”的三元组表即为行逻辑链接的顺序表。其类型描述如下：
针对存储于行逻辑链接顺序表的稀疏矩阵，其矩阵相乘的算法与经典算法有所不同。因此，对于两个稀疏矩阵相乘(Q=M×N)的过程可以大致描述如下：
请使用行逻辑链接的顺序表实现两个稀疏矩阵的乘法。
2073: 算法5-3：行逻辑链接的矩阵乘法
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $4$ | 正确数量 | $4$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
Description
Input
输入的第一行是两个整数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个整数，用空格隔开，表示第二个稀疏矩阵的各个元素。
Output
输出两个矩阵的乘积。输出共有r1行，每行有c2个整数，每个整数后输出一个空格。请注意行尾输出换行。
Sample Input复制
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
Sample Output复制
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]中的一部分，需要将其累加从而得到最终的结果。
另外需要注意的是，两个稀疏矩阵相乘的乘积并不一定是稀疏矩阵。
总结：
采用行逻辑链接的顺序表通过使用非零元的行信息，使稀疏矩阵的存储和使用效能进一步提高。尤其是对于稀疏矩阵相乘, 这种算法省去了非常多无谓的计算。
推荐代码 查看2073 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$4 $ms] | 范晋豪@信息与计算科学142 | 152705 | 2017-11-16 15:10:14 |
| 内存最少[$948 $KB] | 范晋豪@信息与计算科学142 | 152704 | 2017-11-16 15:10:14 |
| 第一AC | 范晋豪@信息与计算科学142 | 152704 | 2017-11-16 15:10:14 |
| 第一挑战 | 范晋豪@信息与计算科学142 | 152704 | 2017-11-16 15:10:14 |
赛题来源/所属竞赛 N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|