稀疏矩阵十字链表Python

稀疏矩阵是指矩阵中大部分元素为0的矩阵。为了节省存储空间和提高运算效率，可以使用稀疏矩阵的存储方式——十字链表。十字链表是一种特殊的链表结构，它由行链表和列链表组成，每个节点同时属于行链表和列链表。在十字链表中，行链表和列链表的头节点分别为行头节点和列头节点，它们的数据域分别存储行号和列号。数据节点的数据域存储矩阵中的非零元素值，指针域分别指向同一行和同一列的下一个非零元素节点。

以下是Python实现稀疏矩阵十字链表的基本步骤：
1. 定义节点类，包括数据域和指针域。
2. 定义行头节点和列头节点。
3. 读入矩阵，创建数据节点，并将其插入到行链表和列链表中。
4. 实现矩阵的加法、减法和乘法等运算。

具体实现细节可以参考下面的代码示例：

class MatNode:
    def __init__(self, data=0, row=0, col=0):
        self.data = data
        self.row = row
        self.col = col
        self.right = None
        self.down = None

class SparseMatrix:
    def __init__(self, mat=[]):
        self.rows = len(mat)
        self.cols = len(mat[0])
        self.rheads = [MatNode() for i in range(self.rows)]
        self.cheads = [MatNode() for i in range(self.cols)]
        for i in range(self.rows):
            for j in range(self.cols):
                if mat[i][j] != 0:
                    node = MatNode(mat[i][j], i, j)
                    self.insert(node)

    def insert(self, node):
        row, col = node.row, node.col
        rhead, chead = self.rheads[row], self.cheads[col]
        p, q = rhead, chead
        while p.right and p.right.col < col:
            p = p.right
        while q.down and q.down.row < row:
            q = q.down
        node.right = p.right
        node.down = q.down
        p.right = q.down = node

    def add(self, other):
        if self.rows != other.rows or self.cols != other.cols:
            return None
        res = SparseMatrix()
        for i in range(self.rows):
            p, q = self.rheads[i], other.rheads[i]
            while p.right and q.right:
                if p.right.col < q.right.col:
                    res.insert(MatNode(p.right.data, i, p.right.col))
                    p = p.right
                elif p.right.col > q.right.col:
                    res.insert(MatNode(q.right.data, i, q.right.col))
                    q = q.right
                else:
                    res.insert(MatNode(p.right.data + q.right.data, i, p.right.col))
                    p, q = p.right, q.right
            while p.right:
                res.insert(MatNode(p.right.data, i, p.right.col))
                p = p.right
            while q.right:
                res.insert(MatNode(q.right.data, i, q.right.col))
                q = q.right
        return res

    def sub(self, other):
        if self.rows != other.rows or self.cols != other.cols:
            return None
        res = SparseMatrix()
        for i in range(self.rows):
            p, q = self.rheads[i], other.rheads[i]
            while p.right and q.right:
                if p.right.col < q.right.col:
                    res.insert(MatNode(p.right.data, i, p.right.col))
                    p = p.right
                elif p.right.col > q.right.col:
                    res.insert(MatNode(-q.right.data, i, q.right.col))
                    q = q.right
                else:
                    res.insert(MatNode(p.right.data - q.right.data, i, p.right.col))
                    p, q = p.right, q.right
            while p.right:
                res.insert(MatNode(p.right.data, i, p.right.col))
                p = p.right
            while q.right:
                res.insert(MatNode(-q.right.data, i, q.right.col))
                q = q.right
        return res

    def mul(self, other):
        if self.cols != other.rows:
            return None
        res = SparseMatrix([[0] * other.cols for i in range(self.rows)])
        for i in range(self.rows):
            p = self.rheads[i].right
            while p:
                j = p.col
                q = other.cheads[j].down
                while q:
                    k = q.row
                    res[i][k] += p.data * q.data
                    q = q.down
                p = p.right
        return res

    def display(self):
        for i in range(self.rows):
            p = self.rheads[i].right
            for j in range(self.cols):
                if p and p.col == j:
                    print(p.data, end=' ')
                    p = p.right
                else:
                    print(0, end=' ')
            print()

# 测试代码
mat1 = [[1, 0, 0], [0, 2, 0], [0, 0, 3]]
mat2 = [[4, 0, 0], [0, 5, 0], [0, 0, 6]]
smat1 = SparseMatrix(mat1)
smat2 = SparseMatrix(mat2)
smat3 = smat1.add(smat2)
smat4 = smat1.sub(smat2)
smat5 = smat1.mul(smat2)
smat1.display()
smat2.display()
smat3.display()
smat4.display()
smat5.display()