已知一个稀疏矩阵A[5000][5000] ,它的元素只有0或者1。请编写程序,
时间: 2023-05-23 14:01:40 浏览: 123
使用稀疏矩阵压缩存储方式将A矩阵压缩,并输出压缩后的矩阵。
答案:压缩稀疏矩阵可以使用压缩存储方式,具体方法是将矩阵中所有非零元素的行列坐标及其对应的值作为一个三元组进行存储。在每个三元组中,第一个元素表示非零元素所在的行,第二个元素表示非零元素所在的列,第三个元素表示非零元素的值。
以下是代码示例,用于将A矩阵压缩成稀疏矩阵:
#include <iostream>
#include <vector>
using namespace std;
struct Triple { //三元组结构体
int row, col, val;
};
void compress(Triple A[], int m, int n, int B[]) { //压缩稀疏矩阵的函数
int k = 0;
B[0] = m, B[1] = n, B[2] = 0; //稀疏矩阵第一行存储矩阵的维度及非零元素个数
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (A[k].row == i && A[k].col == j) {
B[k + 3] = A[k].val; //存储非零元素的值
k++;
}
}
}
}
int main() {
int A[5000][5000];
//填充矩阵A
...
vector<Triple> triples; //用vector存储三元组,方便后续压缩
for (int i = 0; i < 5000; i++) {
for (int j = 0; j < 5000; j++) {
if (A[i][j] != 0) {
Triple triple = {i, j, A[i][j]};
triples.push_back(triple); //将非零元素存入三元组
}
}
}
Triple A_sparse[triples.size()];
for (int i = 0; i < triples.size(); i++) {
A_sparse[i] = triples[i]; //将vector中的三元组转存进数组
}
int A_compressed[triples.size() + 3];
compress(A_sparse, 5000, 5000, A_compressed);
//输出稀疏矩阵
for (int i = 0; i < triples.size() + 3; i++) {
cout << A_compressed[i] << " ";
}
cout << endl;
return 0;
}
特别注意:由于CSDN此前有过AI问答机器人发布,因此可能存在误导用户的可能性,此AI并非官方CSDN AI,仅为作者开发的角色扮演AI。
阅读全文