稀疏矩阵是指矩阵中非零元素的数量远小于零元素数量的矩阵，在科学计算、图论、机器学习等领域非常常见。如果直接采用二维数组存储稀疏矩阵，会浪费大量内存空间，因此需要在C++中使用专门的存储结构来处理稀疏矩阵。
稀疏矩阵的常用存储结构
1. 三元组顺序表
三元组顺序表是最直观的稀疏矩阵存储方式，每个非零元素用三个属性表示：行号、列号、元素值。我们可以定义一个结构体存储单个非零元素，再用数组或vector存储所有非零元素。
首先定义三元组结构体：
#include <iostream>
#include <vector>
using namespace std;
// 三元组结构体，存储非零元素的行、列、值
struct Triple {
int row; // 行号，从0开始计数
int col; // 列号，从0开始计数
int value; // 非零元素的值
Triple(int r, int c, int v) : row(r), col(c), value(v) {}
};
接下来实现三元组顺序表的稀疏矩阵类，包含初始化和打印功能：
class SparseMatrixTriple {
private:
int rows; // 矩阵总行数
int cols; // 矩阵总列数
vector<Triple> triples; // 存储所有非零元素的三元组
public:
SparseMatrixTriple(int r, int c) : rows(r), cols(c) {}
// 向矩阵中添加非零元素
void addElement(int row, int col, int value) {
if (row >= rows || col >= cols) {
cout << "行号或列号超出矩阵范围" << endl;
return;
}
triples.push_back(Triple(row, col, value));
}
// 打印稀疏矩阵的三元组存储内容
void printTriples() {
cout << "矩阵行数: " << rows << ", 列数: " << cols << endl;
cout << "非零元素列表（行,列,值）:" << endl;
for (auto &t : triples) {
cout << "(" << t.row << "," << t.col << "," << t.value << ")" << endl;
}
}
};
使用示例：
int main() {
// 创建一个3行4列的稀疏矩阵
SparseMatrixTriple mat(3, 4);
// 添加非零元素，其余位置默认为0
mat.addElement(0, 1, 5);
mat.addElement(1, 2, 3);
mat.addElement(2, 0, 7);
mat.printTriples();
return 0;
}
2. 行压缩存储CSR格式
CSR（Compressed Sparse Row）格式是稀疏矩阵运算中常用的高效存储方式，它用三个数组表示矩阵：values数组存储所有非零元素的值，col_indices数组存储每个非零元素对应的列号，row_ptr数组存储每一行第一个非零元素在values数组中的起始索引，最后一行后面补充一个总非零元素数量的索引。
CSR格式的稀疏矩阵类实现如下：
class SparseMatrixCSR {
private:
int rows; // 矩阵总行数
int cols; // 矩阵总列数
vector<int> values; // 非零元素值数组
vector<int> col_indices; // 非零元素列号数组
vector<int> row_ptr; // 行指针数组，长度为rows+1
public:
SparseMatrixCSR(int r, int c) : rows(r), cols(c) {
row_ptr.resize(rows + 1, 0);
}
// 从三元组列表构建CSR格式，要求三元组按行优先、同行业号递增的顺序传入
void buildFromTriples(const vector<Triple>& triples) {
if (triples.empty()) return;
int current_row = 0;
row_ptr[0] = 0;
for (size_t i = 0; i < triples.size(); i++) {
const Triple& t = triples[i];
// 如果切换到新的一行，更新行指针
while (current_row < t.row) {
current_row++;
row_ptr[current_row] = i;
}
values.push_back(t.value);
col_indices.push_back(t.col);
}
// 最后一行之后的指针指向总非零元素数量
row_ptr[rows] = triples.size();
}
// 打印CSR存储的三个数组内容
void printCSR() {
cout << "values数组: ";
for (int v : values) cout << v << " ";
cout << endl;
cout << "col_indices数组: ";
for (int c : col_indices) cout << c << " ";
cout << endl;
cout << "row_ptr数组: ";
for (int r : row_ptr) cout << r << " ";
cout << endl;
}
};
使用示例：
int main() {
SparseMatrixCSR csrMat(3, 4);
vector<Triple> triples;
// 按行优先顺序添加三元组
triples.push_back(Triple(0, 1, 5));
triples.push_back(Triple(1, 2, 3));
triples.push_back(Triple(2, 0, 7));
csrMat.buildFromTriples(triples);
csrMat.printCSR();
return 0;
}
稀疏矩阵的基础运算实现
三元组矩阵的加法
两个稀疏矩阵相加，需要遍历两个矩阵的三元组，按行号和列号匹配元素，相同位置的元素值相加，不同位置的元素直接加入结果矩阵。如果相加后结果为0，则不加入结果矩阵。
// 三元组稀疏矩阵加法，返回新的三元组稀疏矩阵
SparseMatrixTriple addTripleMatrix(const SparseMatrixTriple& a, const SparseMatrixTriple& b) {
// 假设两个矩阵行数列数相同
SparseMatrixTriple result(a.rows, a.cols);
int i = 0, j = 0;
while (i < a.triples.size() && j < b.triples.size()) {
const Triple& ta = a.triples[i];
const Triple& tb = b.triples[j];
if (ta.row == tb.row && ta.col == tb.col) {
int sum = ta.value + tb.value;
if (sum != 0) {
result.addElement(ta.row, ta.col, sum);
}
i++;
j++;
} else if (ta.row < tb.row || (ta.row == tb.row && ta.col < tb.col)) {
result.addElement(ta.row, ta.col, ta.value);
i++;
} else {
result.addElement(tb.row, tb.col, tb.value);
j++;
}
}
// 添加剩余元素
while (i < a.triples.size()) {
const Triple& ta = a.triples[i];
result.addElement(ta.row, ta.col, ta.value);
i++;
}
while (j < b.triples.size()) {
const Triple& tb = b.triples[j];
result.addElement(tb.row, tb.col, tb.value);
j++;
}
return result;
}
CSR矩阵的向量乘法
CSR格式非常适合做矩阵和向量的乘法，对于每一行，通过row_ptr找到该行所有非零元素的起始和结束位置，遍历这些非零元素，用元素值乘以向量对应列位置的值，累加得到结果向量的该行值。
// CSR稀疏矩阵乘以向量，返回结果向量
vector<int> csrMultiplyVector(const SparseMatrixCSR& mat, const vector<int>& vec) {
vector<int> result(mat.rows, 0);
for (int i = 0; i < mat.rows; i++) {
// 第i行的非零元素在values数组中的范围是[row_ptr[i], row_ptr[i+1])
int start = mat.row_ptr[i];
int end = mat.row_ptr[i+1];
for (int k = start; k < end; k++) {
int col = mat.col_indices[k];
result[i] += mat.values[k] * vec[col];
}
}
return result;
}
存储方式的选择建议
三元组顺序表实现简单，适合矩阵规模小、需要频繁插入删除非零元素的场景，但做矩阵运算时效率较低。
CSR格式的空间利用率更高，矩阵运算尤其是矩阵乘向量、矩阵乘矩阵的效率远高于三元组顺序表，适合大规模稀疏矩阵的运算场景，是很多科学计算库的首选存储格式。
如果矩阵非零元素按列分布更集中，也可以选择CSC（列压缩存储）格式，思路和CSR类似，只是按列组织数据。