1. 稀疏矩阵基础概念与东华OJ题目解析稀疏矩阵是指矩阵中绝大多数元素为零的矩阵。在实际应用中很多科学计算和工程问题都会产生这类矩阵比如电路分析、热传导模拟、图像处理等领域。与常规矩阵不同稀疏矩阵的高效存储和运算需要特殊处理。东华OJ第73题要求我们实现稀疏矩阵的基本操作这是C数据结构课程中的经典题目。题目通常会给出一个大型矩阵比如1000×1000其中非零元素可能只有几十个要求我们实现压缩存储和基本运算。提示稀疏矩阵处理的核心思想是只存储非零元素这可以大幅节省内存空间。对于1000×1000的矩阵常规存储需要1,000,000个单元而稀疏存储可能只需要几十个。1.1 稀疏矩阵的存储方式对比常见的稀疏矩阵存储方式有三种三元组顺序表COO存储格式(行号, 列号, 值)优点简单直观添加元素方便缺点随机访问效率低压缩稀疏行CSR使用三个数组values存储非零元素值col_ind存储列索引row_ptr存储每行起始位置优点行访问效率高缺点构建复杂压缩稀疏列CSC类似CSR但是按列压缩优点列访问效率高缺点构建复杂对于东华OJ的基础题我们推荐使用三元组顺序表因为题目通常要求实现基本操作不涉及复杂运算代码实现简单适合初学者理解在数据量不大时性能足够2. 三元组顺序表的C实现2.1 数据结构设计首先我们需要定义三元组和稀疏矩阵的结构struct Triple { int row; // 行号 int col; // 列号 int value; // 元素值 }; class SparseMatrix { private: int rows; // 矩阵总行数 int cols; // 矩阵总列数 int numNonZeros; // 非零元素个数 Triple* elements; // 存储非零元素的三元组数组 public: // 构造函数和析构函数 SparseMatrix(int r, int c, int n); ~SparseMatrix(); // 基本操作 void inputMatrix(); void printMatrix(); SparseMatrix transpose(); SparseMatrix add(SparseMatrix other); };2.2 构造函数实现SparseMatrix::SparseMatrix(int r, int c, int n) : rows(r), cols(c), numNonZeros(n) { elements new Triple[numNonZeros]; } SparseMatrix::~SparseMatrix() { delete[] elements; }2.3 矩阵输入与输出输入函数需要读取非零元素并存储void SparseMatrix::inputMatrix() { for (int i 0; i numNonZeros; i) { cin elements[i].row elements[i].col elements[i].value; // 通常题目中行列号从1开始需要转换为从0开始 elements[i].row--; elements[i].col--; } }输出函数需要将矩阵以二维形式打印void SparseMatrix::printMatrix() { int index 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (index numNonZeros elements[index].row i elements[index].col j) { cout elements[index].value ; index; } else { cout 0 ; } } cout endl; } }注意在实际OJ提交中输出格式必须严格符合题目要求包括空格和换行。建议仔细阅读题目输出样例。3. 稀疏矩阵转置算法实现转置是稀疏矩阵的基本操作之一即将矩阵的行列互换。对于三元组存储我们需要特别注意效率问题。3.1 简单转置算法最直观的方法是遍历原矩阵先找所有列号为0的元素放入新矩阵然后找列号为1的元素依此类推SparseMatrix SparseMatrix::transpose() { SparseMatrix result(cols, rows, numNonZeros); int index 0; for (int c 0; c cols; c) { for (int i 0; i numNonZeros; i) { if (elements[i].col c) { result.elements[index].row elements[i].col; result.elements[index].col elements[i].row; result.elements[index].value elements[i].value; index; } } } return result; }这种方法时间复杂度为O(列数×非零元素数)当矩阵很大时效率不高。3.2 快速转置算法更高效的算法是快速转置时间复杂度为O(非零元素数列数)SparseMatrix SparseMatrix::transpose() { SparseMatrix result(cols, rows, numNonZeros); // 1. 统计每列的非零元素数 int* colCounts new int[cols](); for (int i 0; i numNonZeros; i) { colCounts[elements[i].col]; } // 2. 计算每列在转置矩阵中的起始位置 int* colStarts new int[cols](); for (int i 1; i cols; i) { colStarts[i] colStarts[i-1] colCounts[i-1]; } // 3. 放置元素 for (int i 0; i numNonZeros; i) { int col elements[i].col; int pos colStarts[col]; result.elements[pos].row elements[i].col; result.elements[pos].col elements[i].row; result.elements[pos].value elements[i].value; colStarts[col]; } delete[] colCounts; delete[] colStarts; return result; }这个算法虽然复杂一些但对于大型稀疏矩阵性能提升明显。在东华OJ中如果数据量不大简单转置通常就足够了。4. 稀疏矩阵加法实现矩阵加法要求两个矩阵维度相同对应元素相加。对于稀疏矩阵我们需要同时遍历两个矩阵的三元组表。SparseMatrix SparseMatrix::add(SparseMatrix other) { if (rows ! other.rows || cols ! other.cols) { throw Matrix dimensions mismatch; } // 估算结果矩阵的非零元素数实际可能更少 int maxNonZeros numNonZeros other.numNonZeros; Triple* temp new Triple[maxNonZeros]; int i 0, j 0, k 0; while (i numNonZeros j other.numNonZeros) { // 比较当前元素的位置 if (elements[i].row other.elements[j].row || (elements[i].row other.elements[j].row elements[i].col other.elements[j].col)) { temp[k] elements[i]; } else if (elements[i].row other.elements[j].row || (elements[i].row other.elements[j].row elements[i].col other.elements[j].col)) { temp[k] other.elements[j]; } else { // 相同位置元素相加 int sum elements[i].value other.elements[j].value; if (sum ! 0) { // 只存储非零和 temp[k].row elements[i].row; temp[k].col elements[i].col; temp[k].value sum; k; } i; j; } } // 处理剩余元素 while (i numNonZeros) temp[k] elements[i]; while (j other.numNonZeros) temp[k] other.elements[j]; // 创建结果矩阵 SparseMatrix result(rows, cols, k); for (int m 0; m k; m) { result.elements[m] temp[m]; } delete[] temp; return result; }实际编程中动态数组管理容易出错。建议初学者先在纸上画出两个矩阵的三元组表模拟合并过程再编写代码。5. 东华OJ题目实战技巧5.1 输入输出优化东华OJ对程序运行时间有限制对于大型稀疏矩阵建议使用更快的IO方法// 在main函数开头加入这两行 ios::sync_with_stdio(false); cin.tie(nullptr);5.2 边界条件处理常见边界条件包括空矩阵无非零元素全零矩阵只有一个元素的矩阵行或列数为1的矩阵5.3 调试技巧调试稀疏矩阵程序时可以先测试小矩阵如3×3打印三元组表内容验证转置和加法结果逐步增加矩阵规模5.4 内存管理动态内存分配容易出错注意new和delete配对使用在析构函数中释放内存考虑使用std::vector替代原生数组6. 性能优化与进阶思路6.1 更高效的存储结构当题目要求更高性能时可以考虑CSR/CSC格式使用STL容器如std::map存储元素分块存储策略6.2 并行计算对于超大型稀疏矩阵使用OpenMP实现并行转置考虑GPU加速CUDA6.3 应用扩展稀疏矩阵技术可以应用于图算法邻接矩阵表示线性方程组求解机器学习中的特征矩阵在实际开发中成熟的数值计算库如Eigen、Armadillo已经实现了优化的稀疏矩阵类但在学习阶段自己实现这些基础数据结构是非常有价值的。
