python实现十字链表

十字链表是一种用于表示稀疏矩阵的数据结构，可以用于高效地存储和操作矩阵。下面是 Python 实现十字链表的示例代码：

class Node:
    def __init__(self, row, col, val):
        self.row = row
        self.col = col
        self.val = val
        self.right = None
        self.down = None

class CrossList:
    def __init__(self, mat):
        self.r, self.c = len(mat), len(mat[0])
        self.row_heads = [None] * self.r
        self.col_heads = [None] * self.c
        for i in range(self.r):
            for j in range(self.c):
                if mat[i][j] != 0:
                    node = Node(i, j, mat[i][j])
                    if not self.row_heads[i]:
                        self.row_heads[i] = node
                    else:
                        cur = self.row_heads[i]
                        while cur.right:
                            cur = cur.right
                        cur.right = node
                    if not self.col_heads[j]:
                        self.col_heads[j] = node
                    else:
                        cur = self.col_heads[j]
                        while cur.down:
                            cur = cur.down
                        cur.down = node

    def print_matrix(self):
        for i in range(self.r):
            cur = self.row_heads[i]
            for j in range(self.c):
                if cur and cur.col == j:
                    print(cur.val, end=' ')
                    cur = cur.right
                else:
                    print(0, end=' ')
            print()

    def add(self, i, j, val):
        node = Node(i, j, val)
        if not self.row_heads[i]:
            self.row_heads[i] = node
        else:
            cur = self.row_heads[i]
            while cur.right and cur.right.col < j:
                cur = cur.right
            node.right = cur.right
            cur.right = node
        if not self.col_heads[j]:
            self.col_heads[j] = node
        else:
            cur = self.col_heads[j]
            while cur.down and cur.down.row < i:
                cur = cur.down
            node.down = cur.down
            cur.down = node

    def delete(self, i, j):
        if not self.row_heads[i] or not self.col_heads[j]:
            return
        if self.row_heads[i].col == j:
            self.row_heads[i] = self.row_heads[i].right
        else:
            cur = self.row_heads[i]
            while cur.right and cur.right.col != j:
                cur = cur.right
            if cur.right:
                cur.right = cur.right.right
        if self.col_heads[j].row == i:
            self.col_heads[j] = self.col_heads[j].down
        else:
            cur = self.col_heads[j]
            while cur.down and cur.down.row != i:
                cur = cur.down
            if cur.down:
                cur.down = cur.down.down

这里定义了一个 `Node` 类来表示十字链表中的节点，包括行号、列号、值以及指向右侧和下方的指针。然后定义了一个 `CrossList` 类来表示整个十字链表，包括行头和列头指针数组。在初始化时，遍历输入矩阵中非零元素，创建相应的节点，并将其插入到行链表和列链表中。同时，`print_matrix` 方法可以输出原始矩阵，方便验证。`add` 方法可以添加一个新节点，`delete` 方法可以删除一个节点。