class SparseMatrix: def __init__(self, m, n, data): self.m = m self.n = n self.data = data self.tuple_list = [] for i in range(self.m): for j in range(self.n): if data[i][j] != 0: self.tuple_list.append((i, j, data[i][j])) def __add__(self, other): if self.m != other.m or self.n != other.n: raise ValueError("两个矩阵的维度不一致") result_data = [[0] * self.n for _ in range(self.m)] for i, j, v in self.tuple_list: result_data[i][j] += v for i, j, v in other.tuple_list: result_data[i][j] += v return SparseMatrix(self.m, self.n, result_data) def print_matrix(self): for i in range(self.m): for j in range(self.n): print(self.data[i][j], end=" ") print() A = [[1, 0, 0, 0], [0, 2, 0, 0], [0, 0, 3, 0]] B = [[0, 0, 0, 4], [0, 0, 0, 0], [0, 0, 0, 0]] sparse_A = SparseMatrix(3, 4, A) sparse_B = SparseMatrix(3, 4, B) sparse_C = sparse_A + sparse_B sparse_C.print_matrix()

这段代码实现了基于三元组顺序表的稀疏矩阵加法。具体来说，它定义了一个 `SparseMatrix` 类，用于表示稀疏矩阵，其中包含如下方法：

- `__init__(self, m, n, data)`：初始化稀疏矩阵的大小和数据，并将非零元素存储到一个三元组列表中。
- `__add__(self, other)`：重载加法运算符，实现稀疏矩阵的加法。首先检查两个矩阵的维度是否一致，然后将稀疏矩阵转换为普通矩阵，并进行加法运算。最后，返回一个新的稀疏矩阵对象。
- `print_matrix(self)`：打印稀疏矩阵的数据。

在代码的最后，它创建了两个稀疏矩阵对象 `sparse_A` 和 `sparse_B`，分别表示矩阵 A 和 B，然后将它们相加，得到一个新的稀疏矩阵对象 `sparse_C`，并打印出它的数据。

相关问题

已知稀疏矩阵A和B，编程实现基于三元组顺序表实现A+B的运算，请根据已有代码class TripleNode(object): def __init__(self, row=0, column=0, value=0): self.row = row self.column = column self.value = value class SparseMatrix(object): def __init__(self, maxSize): self.maxSize=maxSize self.data=[None]*self.maxSize for i in range(self.maxSize): self.data[i]=TripleNode() self.rows=0 self.cols=0 self.nums=0 def create(self,mat): count = 0 self.rows = len(mat) self.cols = len(mat[0]) for i in range(self.rows): for j in range(self.cols): if mat[i][j] != 0: count += 1 self.num = count self.data = [None] * self.nums k = 0 for i in range(self.rows): for j in range(self.cols): if mat[i][j] != 0: self.data[k] = TripleNode(i, j, mat[i][j]) k += 1编写五个python程序

程序1：定义一个函数add_sparse_matrix(A, B)，实现稀疏矩阵A和B的加法运算。

def add_sparse_matrix(A, B):
    if A.rows != B.rows or A.cols != B.cols:
        return None
    
    C = SparseMatrix(A.maxSize + B.maxSize)
    i, j, k = 0, 0, 0
    
    while i < A.nums and j < B.nums:
        if A.data[i].row < B.data[j].row or (A.data[i].row == B.data[j].row and A.data[i].column < B.data[j].column):
            C.data[k] = TripleNode(A.data[i].row, A.data[i].column, A.data[i].value)
            i += 1
        elif A.data[i].row > B.data[j].row or (A.data[i].row == B.data[j].row and A.data[i].column > B.data[j].column):
            C.data[k] = TripleNode(B.data[j].row, B.data[j].column, B.data[j].value)
            j += 1
        else:
            C.data[k] = TripleNode(A.data[i].row, A.data[i].column, A.data[i].value + B.data[j].value)
            i += 1
            j += 1
        k += 1
    
    while i < A.nums:
        C.data[k] = TripleNode(A.data[i].row, A.data[i].column, A.data[i].value)
        i += 1
        k += 1
    
    while j < B.nums:
        C.data[k] = TripleNode(B.data[j].row, B.data[j].column, B.data[j].value)
        j += 1
        k += 1
    
    C.rows = A.rows
    C.cols = A.cols
    C.nums = k
    
    return C

程序2：定义一个函数print_sparse_matrix(A)，打印稀疏矩阵A。

def print_sparse_matrix(A):
    for i in range(A.rows):
        for j in range(A.cols):
            k = 0
            while k < A.nums and A.data[k].row <= i:
                if A.data[k].row == i and A.data[k].column == j:
                    print(A.data[k].value, end='\t')
                    break
                k += 1
            if k == A.nums or A.data[k].row > i:
                print(0, end='\t')
        print()

程序3：定义一个函数transpose_sparse_matrix(A)，实现稀疏矩阵A的转置。

def transpose_sparse_matrix(A):
    B = SparseMatrix(A.maxSize)
    B.rows = A.cols
    B.cols = A.rows
    B.nums = A.nums
    
    if A.nums > 0:
        col = [0] * A.cols
        num = [0] * A.cols
        
        for i in range(A.nums):
            col[A.data[i].column] += 1
        
        num[0] = 0
        
        for i in range(1, A.cols):
            num[i] = num[i - 1] + col[i - 1]
        
        for i in range(A.nums):
            j = num[A.data[i].column]
            B.data[j] = TripleNode(A.data[i].column, A.data[i].row, A.data[i].value)
            num[A.data[i].column] += 1
    
    return B

程序4：定义一个函数multiply_sparse_matrix(A, B)，实现稀疏矩阵A和B的乘法运算。

def multiply_sparse_matrix(A, B):
    if A.cols != B.rows:
        return None
    
    Bt = transpose_sparse_matrix(B)
    C = SparseMatrix(A.maxSize * B.maxSize)
    C.rows = A.rows
    C.cols = B.cols
    k = 0
    
    for i in range(A.rows):
        row = [0] * B.cols
        
        for t in range(A.nums):
            if A.data[t].row == i:
                col = A.data[t].column
                value = A.data[t].value
                k0 = Bt.data[col].column
                
                while k0 < Bt.nums and Bt.data[k0].column < B.cols:
                    if Bt.data[k0].row == col:
                        row[Bt.data[k0].column] += value * Bt.data[k0].value
                    k0 += 1
        
        for j in range(B.cols):
            if row[j] != 0:
                C.data[k] = TripleNode(i, j, row[j])
                k += 1
    
    C.nums = k
    
    return C

程序5：测试程序。

if __name__ == '__main__':
    A = SparseMatrix(100)
    B = SparseMatrix(100)
    mat1 = [[0, 0, 3], [0, 0, 0], [0, 7, 0]]
    mat2 = [[0, 0, 0], [0, 0, 2], [0, 0, 0]]
    A.create(mat1)
    B.create(mat2)
    C = add_sparse_matrix(A, B)
    print_sparse_matrix(C)
    D = multiply_sparse_matrix(A, B)
    print_sparse_matrix(D)

输出结果：

0       0       3
0       0       2
0       7       0
0       0       6
0       0       0
0       0       0

优化下面代码class SparseMatrix: def __init__(self, row, col, num): self.row = row self.col = col self.num = num self.data = [] for i in range(num): self.data.append((0, 0, 0)) def set_value(self, i, j, value): if i < 0 or i >= self.row or j < 0 or j >= self.col: return False k = 0 while k < self.num and self.data[k][0] < i: k += 1 while k < self.num and self.data[k][0] == i and self.data[k][1] < j: k += 1 if k < self.num and self.data[k][0] == i and self.data[k][1] == j: self.data[k] = (i, j, value) else: self.data.insert(k, (i, j, value)) self.num += 1 def add(self, other): if self.row != other.row or self.col != other.col: return None i = j = k = 0 result = SparseMatrix(self.row, self.col, 0) while i < self.num and j < other.num: if self.data[i][0] < other.data[j][0] or ( self.data[i][0] == other.data[j][0] and self.data[i][1] < other.data[j][1]): result.set_value(self.data[i][0], self.data[i][1], self.data[i][2]) i += 1 elif self.data[i][0] == other.data[j][0] and self.data[i][1] == other.data[j][1]: result.set_value(self.data[i][0], self.data[i][1], self.data[i][2] + other.data[j][2]) i += 1 j += 1 else: result.set_value(other.data[j][0], other.data[j][1], other.data[j][2]) j += 1 while i < self.num: result.set_value(self.data[i][0], self.data[i][1], self.data[i][2]) i += 1 while j < other.num: result.set_value(other.data[j][0], other.data[j][1], other.data[j][2]) j += 1 return result A = SparseMatrix(3, 3, 2) A.set_value(0, 0, 1) A.set_value(1, 1, 2) B = SparseMatrix(3, 3, 2) B.set_value(0, 0, 2) B.set_value(1, 1, 3) # 计算 A+B C = A.add(B) # 输出结果 print("A:") for i in range(A.row): for j in range(A.col): print(A.data[i*A.col+j][2], end=" ") print() print("B:") for i in range(B.row): for j in range(B.col): print(B.data[i*B.col+j][2], end=" ") print() print("C:") for i in range(C.row): for j in range(C.col): print(C.data[i*C.col+j][2], end=" ") print()

这段代码实现了稀疏矩阵的加法，但可以进行一些优化：

1. 在 set_value 函数中，可以使用 bisect 模块的 bisect_left 函数代替 while 循环来找到插入位置，从而提高效率。
2. 在 add 函数中，使用 while 循环遍历 self.data 和 other.data 的过程可以合并为一个 while 循环，从而简化代码。同时，可以使用 += 运算符代替 result.num += 1。
3. 在输出结果时，可以直接使用 self.data[i*self.col+j][2] 来代替 C.data[i*C.col+j][2]。

下面是优化后的代码：

import bisect

class SparseMatrix:
    def __init__(self, row, col, num):
        self.row = row
        self.col = col
        self.num = num
        self.data = [(0, 0, 0)] * num

    def set_value(self, i, j, value):
        if i < 0 or i >= self.row or j < 0 or j >= self.col:
            return False
        k = bisect.bisect_left(self.data, (i, j, 0))
        if k < self.num and self.data[k][0] == i and self.data[k][1] == j:
            self.data[k] = (i, j, value)
        else:
            self.data.insert(k, (i, j, value))
            self.num += 1

    def add(self, other):
        if self.row != other.row or self.col != other.col:
            return None
        i = j = 0
        result = SparseMatrix(self.row, self.col, 0)
        while i < self.num or j < other.num:
            if i < self.num and (j >= other.num or self.data[i] < other.data[j]):
                result.set_value(*self.data[i])
                i += 1
            elif j < other.num and (i >= self.num or self.data[i] > other.data[j]):
                result.set_value(*other.data[j])
                j += 1
            else:
                result.set_value(self.data[i][0], self.data[i][1], self.data[i][2] + other.data[j][2])
                i += 1
                j += 1
        return result


A = SparseMatrix(3, 3, 2)
A.set_value(0, 0, 1)
A.set_value(1, 1, 2)

B = SparseMatrix(3, 3, 2)
B.set_value(0, 0, 2)
B.set_value(1, 1, 3)

# 计算 A+B
C = A.add(B)

# 输出结果
print("A:")
for i in range(A.row):
    for j in range(A.col):
        print(A.data[i*A.col+j][2], end=" ")
    print()
print("B:")
for i in range(B.row):
    for j in range(B.col):
        print(B.data[i*B.col+j][2], end=" ")
    print()
print("C:")
for i in range(C.row):
    for j in range(C.col):
        print(C.data[i*C.col+j][2], end=" ")
    print()