十字链表法：压缩存储稀疏矩阵的强大工具

在计算机科学中，稀疏矩阵是一个大多数元素为零的矩阵，对于这类矩阵，我们通常不使用常规的二维数组来表示，因为这样会浪费大量的存储空间。相反，我们会使用压缩存储的方法，其中十字链表法是一种常用的方法。

一、十字链表法简介

十字链表法是一种特殊的链式存储结构，用于表示稀疏矩阵。在这种结构中，矩阵中的每一行和每一列都有一个链表，用于存储该行或该列的非零元素。此外，每个非零元素还有一个指针，指向其所在行和列的链表中的下一个元素。这种结构结合了数组和链表的优点，既可以在常数时间内访问任意元素，又可以有效地压缩存储空间。

二、十字链表法实现

在十字链表法中，我们使用两个数组来存储行链表和列链表的头节点。假设我们有一个 m x n 的稀疏矩阵，我们可以使用一个长度为 m 的数组 rhead 来存储每一行的头节点，使用一个长度为 n 的数组 chead 来存储每一列的头节点。

每个非零元素在链表中都有一个节点，节点包含三个部分：值、行指针和列指针。行指针指向同一行中的下一个元素，列指针指向同一列中的下一个元素。这种结构使得我们可以轻松地访问任意位置的元素，同时也可以方便地添加或删除元素。

三、十字链表法的优点

1. 节省空间：由于只存储非零元素，因此可以大幅度减少存储空间的使用。
2. 高效的访问：可以通过行指针和列指针直接访问任意位置的元素，时间复杂度为 O(1)。
3. 便于添加和删除操作：可以在链表中方便地添加或删除元素，而不会影响其他元素的位置。

四、如何使用十字链表法表示稀疏矩阵

1. 初始化：创建一个空的行链表数组和一个空的列链表数组。
2. 填充数据：遍历稀疏矩阵中的每个元素，如果元素非零，则在行链表和列链表中找到其位置，并添加一个新节点。新节点的值设为该元素的值，行指针设为当前行中的最后一个节点，列指针设为当前列中的最后一个节点。
3. 访问元素：通过行指针和列指针可以直接访问任意位置的元素。
4. 添加或删除元素：在需要添加或删除元素时，只需要找到要操作的位置，然后在相应的行链表或列链表中添加或删除节点即可。

五、示例代码（Python）

以下是一个简单的示例代码，展示了如何使用十字链表法表示一个 3x3 的稀疏矩阵：

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