十五、稀疏矩阵的乘法运算

文章目录

• 十五、稀疏矩阵的乘法运算
• • 题目描述
  • 解题思路
  • 上机代码

题目描述

数据压缩是提高传输、存储效率一种技术。教材第5章介绍了两种简单的压缩存储方法。

本实验要求实现两个稀疏矩阵相乘积的算法**。其中稀疏矩阵非零元素数量小于100.**

输入：

第1个稀疏矩阵的行数

• 列数
• 非零元个数(三个数都大于0)
• 三元组

第2个稀疏矩阵的行数

• 列数
• 非零元个数(三个数都大于0)
• 三元组

以行为主序输入稀疏矩阵三元组表

输出：

乘积矩阵的行数
列数
非零元个数(三个数都大于0)
三元组

测试输入期待的输出时间限制内存限制额外进程

测试用例 1	3 4 4 1 1 3 1 4 5 2 2 -1 3 1 2 4 2 4 1 2 2 2 1 1 3 1 -2 3 2 4	3 2 3 1,2,6 2,1,-1 3,2,4	1秒	256KB	0

解题思路

教材第 100 页指出，为了便于随机存取任意一行的非零元，需要知道每一行的第一个非零元在三元组表中的位置。因此，把指示 “行” 信息的辅助数组 cpot 固定在稀疏矩阵的存储结构中，称这种 “带行链接信息” 的三元组表为行逻辑链接的顺序表。

/* 行逻辑链接顺序表 */ typedef struct {Triple data[1000]; //非零元三元组表int rpos[1000]; //各行第一个非零元的位置表int mu, nu, tu; //矩阵的行数、列数和非零元个数 }RLSMatrix;

教材第 102 页给出了稀疏矩阵乘法的基本操作描述和算法流程实现。

上机代码

#include<cstdio> #include<stack> #include<cstring> #include<cstdlib> #include<iostream> using namespace std;//定义三元组和顺序表 typedef struct {int i, j;int e; }Triple; typedef struct {Triple data[1000];int rpos[1000];int mu, nu, tu; }RLSMatrix; int rpos[1000]; int num[1000];int main() {int arow = 0, brow = 0, tp = 0;int col = 0, ccol = 0;int p = 0, t = 0, q = 0;RLSMatrix M, N, Q;//输入M、N矩阵数据scanf("%d%d%d", &M.mu, &M.nu, &M.tu);for (int i = 1; i <= M.tu; i++)scanf("%d%d%d", &M.data[i].i, &M.data[i].j, &M.data[i].e);scanf("%d%d%d", &N.mu, &N.nu, &N.tu);for (int i = 1; i <= N.tu; i++)scanf("%d%d%d", &N.data[i].i, &N.data[i].j, &N.data[i].e);for (col = 1; col <= M.mu; col++)num[col] = 0;for (int i = 1; i <= M.tu; i++)num[M.data[i].i]++;M.rpos[1] = 1;for (col = 2; col <= M.mu; col++)M.rpos[col] = M.rpos[col - 1] + num[col - 1];for (col = 1; col <= N.mu; col++)num[col] = 0;for (int i = 1; i <= N.tu; i++)num[N.data[i].i]++;N.rpos[1] = 1;for (col = 2; col <= N.mu; col++)N.rpos[col] = N.rpos[col - 1] + num[col - 1];/* 计算矩阵乘积 */Q.mu = M.mu;Q.nu = N.nu;Q.tu = 0;if (M.tu*N.tu != 0) {for (arow = 1; arow <= M.mu; arow++) {memset(rpos, 0, sizeof(rpos));Q.rpos[arow] = Q.tu + 1;if (arow < M.mu)tp = M.rpos[arow + 1];elsetp = M.tu + 1;for (p = M.rpos[arow]; p < tp; p++) {brow = M.data[p].j;if (brow < N.mu)t = N.rpos[brow + 1];elset = N.tu + 1;for (q = N.rpos[brow]; q < t; q++) {ccol = N.data[q].j;rpos[ccol] += M.data[p].e*N.data[q].e;}}for (ccol = 1; ccol <= Q.nu; ccol++){if (rpos[ccol]) {Q.tu++;Q.data[Q.tu].i = arow;Q.data[Q.tu].j = ccol;Q.data[Q.tu].e = rpos[ccol];}}}}//输出乘积矩阵Qprintf("%d\n", Q.mu);printf("%d\n", Q.nu);printf("%d\n", Q.tu);for (int i = 1; i <= Q.tu; i++)printf("%d,%d,%d\n", Q.data[i].i, Q.data[i].j, Q.data[i].e);return 0; }

总结

以上是生活随笔为你收集整理的十五、稀疏矩阵的乘法运算的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。