数据结构稀疏矩阵代码
时间: 2024-08-27 07:00:25 浏览: 25
稀疏矩阵是一种数据结构,用于高效存储和处理那些非零元素相对较少的大规模矩阵。由于大部分矩阵在实际应用中往往有很多元素值为0,传统的二维数组会浪费大量空间。稀疏矩阵通常通过特殊的压缩表示方法来节省存储空间。
在Python中,一种常见的稀疏矩阵库是`scipy.sparse`模块,它提供多种稀疏矩阵类型,比如:
- `coo_matrix`(坐标列表型):基于行和列索引以及非零值创建稀疏矩阵。
- `csr_matrix`(压缩稀疏行):每个行是一个连续的数组,适用于密集在某些行的矩阵。
- `csc_matrix`(压缩稀疏列):每个列是一个连续的数组,适合于密集在某些列的矩阵。
下面是一个简单的例子,展示如何使用`scipy.sparse.csr_matrix`创建和操作稀疏矩阵:
```python
from scipy.sparse import csr_matrix
# 创建一个3x4的全零矩阵
sparse_matrix = csr_matrix((0, (0, 0), (0, 1)), shape=(3, 4))
# 添加非零元素
sparse_matrix[1, 2] = 5
sparse_matrix[2, 3] = 10
# 输出稀疏矩阵的非零元素及其位置
print(sparse_matrix.toarray()) # 输出压缩后的矩阵
```
相关问题
数据结构稀疏矩阵转置代码
以下是稀疏矩阵转置的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define SMAX 1000
typedef int datatype;
typedef struct {
int i, j; // 储存非零元素的行和列信息
datatype v; // 非零元素的值
} SPNode; // 数组里的元素
typedef struct {
int mu, nu, tu; // 矩阵的行、列和非零元素的个数
SPNode data[SMAX + 1]; // 三元组数组,第0位不用
} SPMatrix;
// 稀疏矩阵转置
void transposeSPMatrix(SPMatrix M, SPMatrix *T) {
int col, t, p;
T->mu = M.nu;
T->nu = M.mu;
T->tu = M.tu;
if (T->tu) {
t = 1;
for (col = 1; col <= M.nu; col++) {
for (p = 1; p <= M.tu; p++) {
if (M.data[p].j == col) {
T->data[t].i = M.data[p].j;
T->data[t].j = M.data[p].i;
T->data[t].v = M.data[p].v;
t++;
}
}
}
}
}
int main() {
SPMatrix M = {3, 4, 5, {{1, 2, 3}, {1, 3, 4}, {2, 1, 5}, {3, 1, 6}, {3, 4, 8}}};
SPMatrix T;
transposeSPMatrix(M, &T);
printf("原矩阵:\n");
for (int i = 1; i <= M.tu; i++) {
printf("%d %d %d\n", M.data[i].i, M.data[i].j, M.data[i].v);
}
printf("转置矩阵:\n");
for (int i = 1; i <= T.tu; i++) {
printf("%d %d %d\n", T.data[i].i, T.data[i].j, T.data[i].v);
}
return 0;
}
```
数据结构稀疏矩阵乘法
稀疏矩阵乘法是指两个稀疏矩阵相乘的操作。稀疏矩阵是指大部分元素为0的矩阵。在进行稀疏矩阵乘法时,我们可以利用矩阵的稀疏性质,减少计算量,提高效率。
具体来说,我们可以使用三元组表示法来存储稀疏矩阵。三元组表示法是指将非零元素的行、列和值分别存储在三个数组中。在进行稀疏矩阵乘法时,我们可以先将两个稀疏矩阵转换为三元组表示法,然后按照一定的规则进行乘法运算,最后再将结果转换回稀疏矩阵的形式。
具体的规则如下:
设A和B是两个稀疏矩阵,它们的三元组表示法分别为(Ar, Ac, Av)和(Br, Bc, Bv)。C是它们的乘积,C的三元组表示法为(Cr, Cc, Cv)。
1. 对于A中每个非零元素(Ar[i], Ac[i], Av[i]),在B中查找列号为Ac[i]的所有非零元素(Br[j], Bc[j], Bv[j]),并将它们的乘积累加到C中的对应位置上。
2. 如果C中已经存在(Cr[k], Cc[k])这个位置,那么将Cv[k]加上上一步计算得到的值。
3. 如果C中不存在(Cr[k], Cc[k])这个位置,那么将(Cr[k], Cc[k], Cv[k])加入C的三元组表示法中。
下面是一个简单的稀疏矩阵乘法的实现代码:
```python
def sparse_matrix_multiply(A, B):
Ar, Ac, Av = A
Br, Bc, Bv = B
m, n, p = len(Ar), len(Bc), len(Br)
Cr, Cc, Cv = [], [], []
i, j = 0, 0
while i < m and j < p:
if Ac[i] < Br[j]:
i += 1
elif Ac[i] > Br[j]:
j += 1
else:
k, l = i, j
sum = 0
while k < m and Ac[k] == Ac[i] and l < p and Br[l] == Br[j]:
if Ar[k] == Br[l]:
sum += Av[k] * Bv[l]
k += 1
l += 1
elif Ar[k] < Br[l]:
k += 1
else:
l += 1
if sum != 0:
Cr.append(Ar[i])
Cc.append(Bc[j])
Cv.append(sum)
i += 1
j += 1
return Cr, Cc, Cv
```