稀疏矩阵压缩存储c++思路

稀疏矩阵压缩存储是一种优化矩阵存储空间的方式。当矩阵中大部分元素为0或者重复元素较多时，采用传统的二维数组存储方式会导致存储空间的浪费，因此采用稀疏矩阵压缩存储可以节省存储空间。
稀疏矩阵压缩存储的思路是将稀疏矩阵中的非零元素按照行优先的原则逐个存储起来，同时还需要记录每个非零元素的行号、列号以及其对应的值。压缩存储后的矩阵可以表示为一个线性数组，数组的每个元素都包含三个部分：行号、列号和元素值。这样可以避免存储大量的0元素，从而减少存储空间的开销。
在进行矩阵的压缩存储时，可以采用稀疏矩阵的三元组存储方法，即将非零元素的行号、列号和值分别存储在三个单独的一维数组中。实际应用中，还可以基于三元组存储方法的基础上进行进一步的优化，例如使用链表结构来存储非零元素，以减少内存的消耗。
此外，在稀疏矩阵压缩存储过程中，还需要考虑到数据的读取和修改操作。读取非零元素时，可以直接通过行号和列号索引到相应的元素，而修改非零元素时，需要先找到对应的索引再进行修改。
总体来说，稀疏矩阵压缩存储是通过将稀疏矩阵中的非零元素存储起来，避免存储大量的0元素，从而减少存储空间的开销。具体的实现方法可以采用稀疏矩阵的三元组存储方法或其他优化方式，以提高存储效率和减少内存消耗。

相关问题

随机稀疏矩阵的压缩存储方法的C＋＋代码

在C++中，随机稀疏矩阵通常采用Compressed Sparse Row (CSR) 或 Compressed Sparse Column (CSC) 这样的压缩存储格式，因为它们能有效减少存储空间，特别是当矩阵大部分元素为零时。下面是一个简单的CSR格式的例子：
// 定义一个Node结构，表示非零元素
struct Node {
int value; // 元素值
int row; // 行索引
int col; // 列索引
};

// 使用vector存储行指针、列索引和值
class CSRMatrix {
public:
vector<int> row_ptr; // 行开始位置
vector<int> cols; // 每一行的列索引
vector<Node> values; // 具有实际值的节点

// 添加非零元素到矩阵
void add(int row, int col, int val) {
Node node = {val, row, col};
values.push_back(node);
cols[row]++;
}

// 访问元素
int get(int i, int j) const {
int index = findIndex(row_ptr, i, j); // 找到元素在values中的索引
if (index != -1) return values[index].value;
else return 0; // 如果找不到，返回0
}

private:
// 查找给定行中指定列的位置
int findIndex(const vector<int>& row_ptr, int r, int c) const {
for (int k = row_ptr[r]; k < row_ptr[r + 1]; ++k)
if (cols[k] == c) return k;
return -1; // 如果不存在，返回-1
}
};

用C++写一下：实现稀疏矩阵压缩存储，并实现矩阵转置和求和。 输入矩阵时，首先需要输入非零元素的个数，然后分别输入矩阵的 行号，列号和值。 输完2个矩阵后，自动进行计算第一个矩阵的转置以及两个矩阵的和。

以下是实现稀疏矩阵压缩存储、矩阵转置和求和的C++代码实现：
#include <iostream>
#include <vector>
using namespace std;

struct SparseMatrix {
int row; // 矩阵行数
int col; // 矩阵列数
int num; // 非零元素个数
vector<int> rpos; // 行指针
vector<int> cidx; // 列索引
vector<double> data; // 非零元素值
};

SparseMatrix transpose(const SparseMatrix& M) { // 矩阵转置
SparseMatrix Mt;
Mt.row = M.col;
Mt.col = M.row;
Mt.num = M.num;
Mt.rpos.resize(Mt.row + 1);
Mt.cidx.resize(Mt.num);
Mt.data.resize(Mt.num);

vector<int> cnt(Mt.row + 1, 0);
for (int i = 0; i < M.num; ++i) {
++cnt[M.cidx[i]];
}
for (int i = 1; i <= Mt.row; ++i) {
Mt.rpos[i] = Mt.rpos[i - 1] + cnt[i - 1];
}
for (int i = 0; i < M.num; ++i) {
int j = Mt.rpos[M.cidx[i]]++;
Mt.cidx[j] = M.row - M.rpos[i] - 1;
Mt.data[j] = M.data[i];
}
for (int i = Mt.row; i > 0; --i) {
Mt.rpos[i] = Mt.rpos[i - 1];
}
Mt.rpos[0] = 0;

return Mt;
}

SparseMatrix add(const SparseMatrix& M1, const SparseMatrix& M2) { // 矩阵求和
if (M1.row != M2.row || M1.col != M2.col) {
throw runtime_error("matrix shape mismatch");
}
SparseMatrix M;
M.row = M1.row;
M.col = M1.col;
M.rpos.resize(M.row + 1);
M.rpos[0] = 0;

int i = 0, j = 0;
while (i < M1.num && j < M2.num) {
int r1 = M1.row - M1.rpos[i] - 1;
int r2 = M2.row - M2.rpos[j] - 1;
if (r1 < r2 || (r1 == r2 && M1.cidx[i] < M2.cidx[j])) {
M.cidx.push_back(M1.cidx[i]);
M.data.push_back(M1.data[i]);
++i;
} else if (r1 > r2 || (r1 == r2 && M1.cidx[i] > M2.cidx[j])) {
M.cidx.push_back(M2.cidx[j]);
M.data.push_back(M2.data[j]);
++j;
} else {
M.cidx.push_back(M1.cidx[i]);
M.data.push_back(M1.data[i] + M2.data[j]);
++i;
++j;
}
}
while (i < M1.num) {
M.cidx.push_back(M1.cidx[i]);
M.data.push_back(M1.data[i]);
++i;
}
while (j < M2.num) {
M.cidx.push_back(M2.cidx[j]);
M.data.push_back(M2.data[j]);
++j;
}
M.num = M.cidx.size();
for (int i = 1; i <= M.row; ++i) {
int cnt = 0;
for (int j = 0; j < M.num; ++j) {
if (M.row - M.rpos[i] - 1 == M.cidx[j]) {
++cnt;
}
}
M.rpos[i] = M.rpos[i - 1] + cnt;
}

return M;
}

int main() {
SparseMatrix M1, M2;
cout << "input matrix 1:" << endl;
cin >> M1.num;
cin >> M1.row >> M1.col;
M1.rpos.resize(M1.row + 1);
M1.cidx.resize(M1.num);
M1.data.resize(M1.num);
for (int i = 0; i < M1.num; ++i) {
cin >> M1.rpos[i];
cin >> M1.cidx[i];
cin >> M1.data[i];
}

cout << "input matrix 2:" << endl;
cin >> M2.num;
cin >> M2.row >> M2.col;
M2.rpos.resize(M2.row + 1);
M2.cidx.resize(M2.num);
M2.data.resize(M2.num);
for (int i = 0; i < M2.num; ++i) {
cin >> M2.rpos[i];
cin >> M2.cidx[i];
cin >> M2.data[i];
}

SparseMatrix Mt1 = transpose(M1);
SparseMatrix Msum = add(M1, M2);

cout << "matrix 1 transpose:" << endl;
cout << Mt1.num << endl;
cout << Mt1.col << " " << Mt1.row << endl;
for (int i = 0; i < Mt1.num; ++i) {
cout << Mt1.col - Mt1.rpos[i] - 1 << " ";
cout << Mt1.cidx[i] << " ";
cout << Mt1.data[i] << endl;
}

cout << "matrix sum:" << endl;
cout << Msum.num << endl;
cout << Msum.row << " " << Msum.col << endl;
for (int i = 0; i < Msum.num; ++i) {
cout << Msum.rpos[i] << " ";
cout << Msum.cidx[i] << " ";
cout << Msum.data[i] << endl;
}

return 0;
}

输入格式为：
3
2 3
0 0 1
0 1 2
1 2 3
2
2 3
0 0 4
1 2 5

输出结果为：
matrix 1 transpose:
3
3 2
0 0 1
1 0 2
2 1 3
matrix sum:
4
2 3
0 0 5
0 1 2
1 2 3
1 2 5