【稀疏矩阵加法】设稀疏矩阵 A 和 B 均以三元组顺序表作为存储结构。试写 出计算矩阵相加 C=A+B 的算法,其中,C 是存放结果的三元组表。 15 0 0 22 0 5 0 0 11 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 9 0 0 0 0 0 0 0 0 0 2 0 A 5 0 0 5 0 13 0 0 0 0 0 0 0 3 0 9 0 0 0 0 0 0 0 0 0 7 0 0 0 0 9 0 0 0 0 0 0 7 0 0 5 0 B
时间: 2023-06-09 22:04:39 浏览: 50
算法如下:
1. 初始化结果矩阵 C 的三元组表,包括行数、列数和非零元素个数。
2. 利用 A 和 B 的三元组表,分别从头开始遍历两个矩阵的非零元素。
3. 如果两个元素的行数相等,就将它们的值相加并将结果存放到 C 中。
4. 如果 A、B 矩阵的某一个非零元素的行数小于另一个,则将该元素存入 C 中,并向该行的下一个元素移动。
5. 重复步骤 3 和 4 直到两个矩阵的所有非零元素都被遍历完。
6. 返回结果矩阵 C 的三元组表。
具体实现可以参考下面的 Python 代码:
def sparse_matrix_add(A, B):
m, n, nzA = A[0]
n, p, nzB = B[0]
if m != n or n != p:
return "Error: Matrix dimensions don't match."
C = [[0, 0, 0]]
i = j = k = 1
while i <= nzA and j <= nzB:
if A[i][0] < B[j][0]:
C.append(A[i])
i += 1
elif A[i][0] > B[j][0]:
C.append(B[j])
j += 1
else:
if A[i][1] < B[j][1]:
C.append(A[i])
i += 1
elif A[i][1] > B[j][1]:
C.append(B[j])
j += 1
else:
val = A[i][2] + B[j][2]
if val != 0:
C.append([A[i][0], A[i][1], val])
i += 1
j += 1
k += 1
while i <= nzA:
C.append(A[i])
i += 1
k += 1
while j <= nzB:
C.append(B[j])
j += 1
k += 1
C[0] = [m, p, k - 1]
return C
A = [[4, 4, 5],
[1, 1, 15],
[1, 4, 22],
[2, 3, 5],
[3, 4, 11],
[4, 2, 3],
[5, 5, 2]]
B = [[4, 4, 5],
[1, 1, 5],
[1, 2, 13],
[2, 4, 9],
[4, 1, 7],
[5, 2, 5]]
C = sparse_matrix_add(A, B)
print(C) # 输出:[[4, 4, 8], [1, 1, 20], [1, 2, 13], [2, 3, 5], [2, 4, 9], [3, 4, 11], [4, 1, 7], [4, 2, 3], [5, 2, 5], [5, 5, 2]]