Python生成十字链表

Python生成十字链表是一种用于表示稀疏矩阵的数据结构，它能有效地存储和操作只包含少数非零元素的大型矩阵。十字链表是一种特殊的链表，它通过两个方向的链接来组织非零元素：行链和列链。每个非零元素由一个节点表示，节点中包含该元素的值、指向同一行下一个非零元素的指针、指向同一列下一个非零元素的指针以及该元素所在的行和列索引。

具体来说，十字链表通常由以下几个部分组成：
1. 行头表（Row Header）：是一个数组，每个元素是一个指向该行第一个非零元素的指针。
2. 列头表（Column Header）：也是一个数组，每个元素是一个指向该列第一个非零元素的指针。
3. 节点（Node）：代表矩阵中的非零元素，每个节点包含以下信息：
- 行索引（Row Index）
- 列索引（Column Index）
- 指向下一行中下一个非零元素的指针（Right）
- 指向下一列中下一个非零元素的指针（Down）

通过这种方式，矩阵的每个非零元素都由其行和列的链接直接关联，而无需存储整个矩阵的所有零元素，从而节省了存储空间。

下面是使用Python创建十字链表的一个简单示例：

class CrossNode:
    def __init__(self, value, row, col):
        self.value = value
        self.row = row
        self.col = col
        self.right = None
        self.down = None

class CrossList:
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.row_head = [None] * rows
        self.col_head = [None] * cols

    def insert(self, row, col, value):
        if row >= self.rows or col >= self.cols:
            raise IndexError("Index out of bounds")
        new_node = CrossNode(value, row, col)
        # 插入到行链表
        new_node.down = self.row_head[row]
        self.row_head[row] = new_node
        # 插入到列链表
        if self.col_head[col] is None or self.col_head[col].row > row:
            new_node.right = self.col_head[col]
            self.col_head[col] = new_node
        else:
            temp = self.col_head[col]
            while temp.down and temp.down.row < row:
                temp = temp.down
            new_node.right = temp.down
            temp.down = new_node

# 示例使用
cross_list = CrossList(3, 3)
cross_list.insert(0, 0, 1) # 在第一行第一列插入元素1
cross_list.insert(1, 2, 2) # 在第二行第三列插入元素2
cross_list.insert(2, 1, 3) # 在第三行第二列插入元素3

在这个示例中，我们首先定义了`CrossNode`类来表示矩阵中的非零元素，然后定义了`CrossList`类来构建十字链表。通过`insert`方法可以将元素插入到矩阵中，同时保持行和列的链表有序。