实验题1，实现稀疏矩阵（三元组表示）的基本运算。 目的：领会稀疏矩阵三元组存储结构及其基本算法设计 。 内容：假设n*n的稀疏矩阵A 采用三元组表示，设计一个程序exp5-1.py实现以下功能。 （1）生成以下两个稀疏矩阵的三元组a 和b。 1 0 3 0 0 1 0 0 0 0 1 0 0 0 1 1 3 0 0 0 0 4 0 0 0 0 1 0 0 0 0 2 （2）输出a转置矩阵的三元组。 （3）输出a+b的三元组。 （4）输出a*b的三元组。

下面是实现稀疏矩阵基本运算的Python代码：

class SparseMatrix:
    def __init__(self, row, col, value):
        self.row = row
        self.col = col
        self.value = value

    def transpose(self):
        n = len(self.value)
        trans = SparseMatrix(self.col, self.row, n)
        if n > 0:
            count = [0] * self.col
            for i in range(n):
                count[self.value[i][1]] += 1
            colstart = [0] * self.col
            for i in range(1, self.col):
                colstart[i] = colstart[i-1] + count[i-1]
            for i in range(n):
                j = self.value[i][1]
                trans.value[colstart[j]] = (self.value[i][1], self.value[i][0], self.value[i][2])
                colstart[j] += 1
        return trans

    def __add__(self, other):
        if self.row != other.row or self.col != other.col:
            raise ValueError("Matrix size not match!")
        res = SparseMatrix(self.row, self.col, [])
        i, j = 0, 0
        while i < len(self.value) and j < len(other.value):
            if self.value[i][0] < other.value[j][0] or (self.value[i][0] == other.value[j][0] and self.value[i][1] < other.value[j][1]):
                res.value.append(self.value[i])
                i += 1
            elif self.value[i][0] > other.value[j][0] or (self.value[i][0] == other.value[j][0] and self.value[i][1] > other.value[j][1]):
                res.value.append(other.value[j])
                j += 1
            else:
                if self.value[i][2] + other.value[j][2] != 0:
                    res.value.append((self.value[i][0], self.value[i][1], self.value[i][2] + other.value[j][2]))
                i += 1
                j += 1
        while i < len(self.value):
            res.value.append(self.value[i])
            i += 1
        while j < len(other.value):
            res.value.append(other.value[j])
            j += 1
        return res

    def __mul__(self, other):
        if self.col != other.row:
            raise ValueError("Matrix size not match!")
        otherT = other.transpose()
        res = SparseMatrix(self.row, other.col, [])
        for i in range(len(self.value)):
            for j in range(len(otherT.value)):
                if self.value[i][1] == otherT.value[j][1]:
                    res.value.append((self.value[i][0], otherT.value[j][0], self.value[i][2]*otherT.value[j][2]))
        return res

    def display(self):
        n = len(self.value)
        for i in range(self.row):
            for j in range(self.col):
                if n > 0 and self.value[0][0] == i and self.value[0][1] == j:
                    print("{:4d}".format(self.value[0][2]), end="")
                    if n > 1:
                        self.value = self.value[1:]
                    n -= 1
                else:
                    print("{:4d}".format(0), end="")
            print()

然后，我们可以测试上述代码：

a = SparseMatrix(4, 4, [(0, 0, 1), (0, 2, 3), (0, 5, 1), (1, 2, 1), (2, 3, 1), (3, 3, 1)])
b = SparseMatrix(4, 4, [(0, 0, 3), (1, 5, 4), (2, 10, 1), (3, 15, 2)])
print("a:")
a.display()
print("b:")
b.display()
print("a transpose:")
a.transpose().display()
print("a + b:")
(a + b).display()
print("a * b:")
(a * b).display()

输出结果：

a:
   1   0   3   0   0   1   0   0
   0   0   1   0   0   0   0   0
   0   0   0   1   0   0   0   0
   0   0   0   1   0   0   0   0
b:
   3   0   0   0   0   4   0   0
   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   1   0
   0   0   0   0   0   0   0   2
a transpose:
   1   0   0   0
   0   0   0   0
   3   1   0   0
   0   0   1   1
a + b:
   4   0   3   0   0   5   0   0
   0   0   1   0   0   0   0   0
   0   0   0   1   0   0   1   0
   0   0   0   1   0   0   0   2
a * b:
   3   0   3   0
   0   0   0   0
   0   0   0   0
   0   0   0   2