C语言 稀疏矩阵

### 稀疏矩阵的表示 稀疏矩阵是指矩阵中大部分元素为零的情况，为了节省存储空间和提高运算效率，通常采用压缩存储的方式。在C语言中，常见的稀疏矩阵表示方法包括： 1. **三元组表示法**： - 使用三个数组分别存储非零元素的行索引、列索引和值。 - 例如：`int row[]`, `int col[]`, `int val[]`。 2. **压缩稀疏行（CRS, Compressed Row Storage）**： - CRS格式使用三个一维数组：`values` 存储非零元素的值，`col_indices` 存储对应的列索引，`row_ptr` 存储每一行第一个非零元素在 `values` 中的位置。 - 这种方式适合按行访问的操作，尤其适用于稀疏矩阵乘法[^1]。 3. **压缩稀疏列（CCS, Compressed Column Storage）**： - 类似于CRS，但按列进行压缩，适合按列访问的操作。 4. **十字链表（Orthogonal Linked List）**： - 每个非零元素由一个节点表示，节点包含行、列、值以及指向上下左右相邻节点的指针。 - 十字链表适合动态插入和删除非零元素的场景[^4]。 ### C语言中的实现方法 #### 三元组表示法示例 ```c #define MAX_NON_ZERO 100 // 最大非零元素数量 typedef struct { int row; int col; int val; } Triple; typedef struct { Triple data[MAX_NON_ZERO]; int rows; // 原始矩阵的行数 int cols; // 原始矩阵的列数 int count; // 非零元素的数量 } SparseMatrix; ``` #### CRS格式的实现 CRS格式的结构体定义如下： ```c typedef struct { int *values; // 非零元素的值 int *col_indices; // 对应的列索引 int *row_ptr; // 每一行起始位置的指针 int num_rows; // 矩阵的行数 int num_cols; // 矩阵的列数 int nnz; // 非零元素总数 } CRSMatrix; ``` 初始化CRS矩阵的函数可以如下所示： ```c void initialize_crs_matrix(CRSMatrix *matrix, int num_rows, int num_cols, int nnz) { matrix->num_rows = num_rows; matrix->num_cols = num_cols; matrix->nnz = nnz; matrix->values = (int *)malloc(nnz * sizeof(int)); matrix->col_indices = (int *)malloc(nnz * sizeof(int)); matrix->row_ptr = (int *)malloc((num_rows + 1) * sizeof(int)); } ``` 添加非零元素的辅助函数： ```c void append_crs_matrix(CRSMatrix *matrix, int row, int col, int value) { static int current_nnz = 0; if (value != 0) { matrix->values[current_nnz] = value; matrix->col_indices[current_nnz] = col; matrix->row_ptr[row + 1]++; current_nnz++; } } ``` #### 十字链表的实现 十字链表节点定义如下： ```c typedef struct Node { int row; int col; int val; struct Node *right; // 同一行内的下一个节点 struct Node *down; // 同一列内的下一个节点 } Node; ``` 十字链表的构建过程涉及逐行或逐列插入非零元素，并维护每个节点的 `right` 和 `down` 指针。 ### 性能与优化 - **时间复杂度分析**： - 三元组和CRS格式的稀疏矩阵加减法的时间复杂度为 O(n)，其中 n 是非零元素的数量。 - CRS格式的乘法操作通常需要三层嵌套循环，其最坏情况下的时间复杂度为 O(n^3)，但在实际应用中可以通过优化减少不必要的计算。 - **优化技巧**： - 利用哈希表或字典来加速查找特定位置的非零元素。 - 在进行矩阵乘法时，预处理矩阵 B 的列信息以加快点积计算。 - 对于大规模稀疏矩阵，考虑使用并行化或向量化技术提升性能。 ###