什么是稀疏矩阵?稀疏矩阵有哪些常见的存储方式?

稀疏矩阵是指矩阵中绝大部分元素为0的矩阵，其中非零元素的个数远远小于矩阵的元素总数。例如，一个大型图像中的大部分像素都是背景色，只有少量像素是色彩的，那么这个图像的像素矩阵就可以被称为稀疏矩阵。

稀疏矩阵的存储方式通常有以下几种：

1. 顺序表存储法：把稀疏矩阵中的所有元素按行序依次存储在一个一维数组中，同时记录每个非零元素的行列坐标和值。

2. 链表存储法：采用链表存储非零元素，每个结点包含该元素的行列坐标和值，同时记录每行的头结点位置。

3. 压缩列存储法：把稀疏矩阵中每列的非零元素压缩在一起存储，同时记录每个非零元素的行坐标和值。

4. 压缩行存储法：把稀疏矩阵中每行的非零元素压缩在一起存储，同时记录每个非零元素的列坐标和值。

5. 对角线存储法：仅存储矩阵的主对角线和两侧的次对角线，其它元素都为0。

6. 块状压缩存储法：将稀疏矩阵划分为若干个大小相等的块，对每个块进行压缩存储。

不同的存储方式适用于不同的稀疏矩阵，选择合适的存储方式可以减少存储空间和提高计算效率。

相关问题

如何在 MATLAB 中创建和操作稀疏矩阵？

在MATLAB中，稀疏矩阵是非常常用的数据类型，尤其当数据中大部分元素为零时，它可以节省存储空间并提高运算效率。你可以使用`sparse`函数来创建稀疏矩阵。以下是一些基本的操作：

1. 创建稀疏矩阵：

% 使用三元组表示（行、列、值）
sparse_matrix = sparse(row_indices, col_indices, values);

这里的`row_indices`、`col_indices`是整数向量，对应非零元素的位置，`values`则是相应位置的值。

2. 初始化特定大小的全零或全一稀疏矩阵：
- 全零：`sparse(N)` 或 `sparse(0:N-1)`
- 全一：`sparse(N) + ones(1,N)`

3. 操作稀疏矩阵：
- 访问元素：`matrix(i,j)`，对于非零元素
- 修改元素：`matrix(i,j) = new_value`
- 添加和减去稀疏矩阵：使用点运算符(`.*` 或 `./`) 和 `-`
- 矩阵乘法（如果接受稀疏矩阵）：`A * B`

4. 查看稀疏度：

density = nnz(matrix) / numel(matrix)

`nnz`返回非零元素的数量，`numel`返回总元素数量。

5. 输出为更易读的形式（显示零的压缩形式）：

disp(sparse_matrix) % 默认行为
sparse_matrix = full(sparse_matrix) % 将其转回稠密矩阵查看

% 或者使用 prettify 函数来自定义输出样式
sparsity_pattern = sparsity_pattern(sparse_matrix);
disp(prettify(sparsity_pattern));

`full`会把稀疏矩阵转换成稠密矩阵。

稀疏矩阵有哪些存储方式？

稀疏矩阵是一种大部分元素为0的矩阵，为了节省存储空间，常采用特殊的存储方式，常见的稀疏矩阵存储方式有三种：
1. 压缩稀疏行（CSR）：将矩阵的每一行压缩成一个一维数组，再将每行的数组和一些辅助信息（如非零元素个数、每行第一个非零元素在数组中的位置等）存储起来。
2. 压缩稀疏列（CSC）：与CSR类似，将矩阵的每一列压缩成一个一维数组，再将每列的数组和辅助信息存储起来。
3. 链式前向星（LIL）：将每个非零元素看作一个结构体，结构体包含该元素的值、所在的行和列以及其在行和列中的下一个非零元素的地址。然后将所有非零元素按照行顺序排列成一个链表，并用一个指针数组存储每一行的链表头。