C++稀疏矩阵实现（从零开始掌握稀疏矩阵的压缩存储与高效操作）

什么是稀疏矩阵？

稀疏矩阵是指矩阵中非零元素的个数远小于总元素个数的矩阵。例如一个 1000×1000 的矩阵，若只有 500 个非零元素，那么它就是稀疏矩阵。

为什么需要压缩存储？

假设一个 10000×10000 的矩阵，使用普通二维数组需要约 400MB 内存（每个 int 占 4 字节）。但如果只有 1000 个非零元素，压缩后只需存储这 1000 个值及其位置，内存占用可降至几 KB！这就是稀疏矩阵压缩存储的核心价值。

常用表示方法：三元组（Triplet）

最简单的稀疏矩阵表示法是三元组表示法：每个非零元素用 (行号, 列号, 值) 表示。我们将所有非零元素按行优先顺序存储在一个结构体数组中。

C++ 实现步骤

1. 定义三元组结构体
2. 创建稀疏矩阵类
3. 实现从普通矩阵转为稀疏矩阵的方法
4. 提供基本操作（如打印、转置等）

完整代码示例

#include <iostream>#include <vector>using namespace std;// 三元组结构体struct Triplet {    int row;      // 行索引    int col;      // 列索引    int value;    // 非零值        Triplet(int r, int c, int v) : row(r), col(c), value(v) {}};class SparseMatrix {private:    vector<Triplet> data;   // 存储非零元素    int rows, cols, nnz;    // 行数、列数、非零元素个数public:    // 构造函数    SparseMatrix(int r, int c) : rows(r), cols(c), nnz(0) {}    // 从普通二维数组构建稀疏矩阵    void fromDense(const vector<vector<int>>& dense) {        data.clear();        for (int i = 0; i < rows; ++i) {            for (int j = 0; j < cols; ++j) {                if (dense[i][j] != 0) {                    data.emplace_back(i, j, dense[i][j]);                    nnz++;                }            }        }    }    // 打印稀疏矩阵（三元组形式）    void print() const {        cout << "行\t列\t值\n";        cout << "----------------\n";        for (const auto& t : data) {            cout << t.row << "\t" << t.col << "\t" << t.value << "\n";        }    }    // 获取矩阵维度    int getRows() const { return rows; }    int getCols() const { return cols; }    int getNNZ() const { return nnz; }};// 示例使用int main() {    // 创建一个 4x5 的普通矩阵    vector<vector<int>> dense = {        {0, 0, 3, 0, 4},        {0, 0, 0, 0, 0},        {1, 0, 0, 0, 2},        {0, 0, 0, 5, 0}    };    SparseMatrix sm(4, 5);    sm.fromDense(dense);    cout << "稀疏矩阵的三元组表示：\n";    sm.print();    cout << "\n矩阵大小: " << sm.getRows() << "x" << sm.getCols()         << ", 非零元素个数: " << sm.getNNZ() << endl;    return 0;}

代码说明

上述代码展示了如何用 C++ 实现一个基础的稀疏矩阵类：

• Triplet 结构体保存每个非零元素的位置和值。
• SparseMatrix 类使用 vector<Triplet> 动态存储数据，避免固定大小限制。
• fromDense() 方法遍历普通矩阵，提取非零元素。
• 打印函数以表格形式输出三元组，便于理解。

进阶方向

掌握了基础的C++三元组表示法后，你可以进一步学习：

• CSR（Compressed Sparse Row）格式：更适合矩阵-向量乘法等高效矩阵运算。
• 稀疏矩阵的加法、乘法实现。
• 使用 Eigen、SuiteSparse 等专业库处理大规模稀疏问题。

总结

通过本教程，你已经学会了如何用 C++ 实现稀疏矩阵的基本压缩存储。这不仅节省了内存，还为后续的高效矩阵运算打下基础。记住，C++稀疏矩阵实现是高性能计算的重要基石，值得深入掌握！