十字链表稀疏矩阵python

十字链表稀疏矩阵是一种数据结构，用于高效地表示非稠密的二维数组，即大部分元素值为0的矩阵。它通过将行和列的索引连接起来形成十字链表的形式来节省空间。在Python中，可以使用自定义的Node类和双向链表来构建这种数据结构。

每个节点包含两个指针，一个指向当前行的下一个元素，另一个指向当前列的下一个元素。如果某个位置的元素值为0，对应的节点会直接链接到另一个0位置，而非创建新的节点。这使得对非零元素的访问更快，而对全零行或列的处理更简单。

以下是简化的Python实现思路：

class Node:
    def __init__(self, value=0, row=-1, col=-1):
        self.value = value
        self.row = row
        self.col = col
        self.next_row = None
        self.next_col = None

class SparseMatrix:
    def __init__(self):
        self.rows = -1
        self.cols = -1
        self.data = {}

    def insert(self, row, col, value):
        if (row, col) not in self.data:
            new_node = Node(value, row, col)
            if row >= self.rows:
                self.extend_rows(row + 1)
            if col >= self.cols:
                self.extend_cols(col + 1)
            self.data[(row, col)] = new_node
            new_node.next_row = self.data.get((row + 1, col), None)
            new_node.next_col = self.data.get((row, col + 1), None)

    # 其他方法如获取值、遍历等...

    def extend_rows(self, num):
        for _ in range(num):
            self.data[self.rows] = None
            self.rows += 1

    def extend_cols(self, num):
        for _ in range(num):
            for i in range(self.rows):
                self.data[i, self.cols] = None
            self.cols += 1

# 使用示例
sparse = SparseMatrix()
sparse.insert(0, 0, 5)  # 等同于 matrix[0][0]