Python十字链表详解（稀疏矩阵高效存储与操作实战教程）

如图所示，每个非零元素包含：行号、列号、值，以及指向同行下一个元素的指针（right）和同列下一个元素的指针（down）。这种设计极大节省了内存，并支持高效的行列遍历。

为什么使用十字链表？

• ✅ 节省内存：只存储非零元素
• ✅ 快速访问：可按行或按列快速遍历
• ✅ 动态扩展：插入/删除非零元素方便
• ✅ 适用于稀疏矩阵存储场景，如科学计算、图算法等

Python实现步骤

我们将分三步实现：定义节点类 → 构建十字链表 → 插入与打印功能。

1. 定义节点类

每个节点保存行(row)、列(col)、值(val)，以及 right 和 down 指针：

class Node:    def __init__(self, row, col, val):        self.row = row        self.col = col        self.val = val        self.right = None  # 指向同行右侧节点        self.down = None   # 指向同列下方节点

2. 构建十字链表主类

我们创建一个 OrthogonalList 类，包含行头指针数组和列头指针数组：

class OrthogonalList:    def __init__(self, rows, cols):        self.rows = rows        self.cols = cols        # 创建行头节点（dummy nodes）        self.row_heads = [Node(i, -1, 0) for i in range(rows)]        # 创建列头节点（dummy nodes）        self.col_heads = [Node(-1, j, 0) for j in range(cols)]

3. 实现插入非零元素

插入时需在对应行和列中找到合适位置（按列号/行号升序），并更新 right 和 down 指针：

def insert(self, row, col, val):    if val == 0:        return  # 不存储零值    if not (0 <= row < self.rows and 0 <= col < self.cols):        raise ValueError("索引越界")        new_node = Node(row, col, val)        # 在行中插入（按列号升序）    prev = self.row_heads[row]    while prev.right and prev.right.col < col:        prev = prev.right    new_node.right = prev.right    prev.right = new_node        # 在列中插入（按行号升序）    prev = self.col_heads[col]    while prev.down and prev.down.row < row:        prev = prev.down    new_node.down = prev.down    prev.down = new_node

4. 打印矩阵（验证结果）

def display(self):    matrix = [[0] * self.cols for _ in range(self.rows)]    for i in range(self.rows):        current = self.row_heads[i].right        while current:            matrix[current.row][current.col] = current.val            current = current.right        for row in matrix:        print(" ".join(f"{x:3}" for x in row))

完整示例与测试

下面是一个完整的使用示例，展示如何构建并打印一个 4x4 的稀疏矩阵：

# 创建 4x4 十字链表ol = OrthogonalList(4, 4)# 插入非零元素ol.insert(0, 1, 5)ol.insert(1, 2, 8)ol.insert(2, 0, 3)ol.insert(3, 3, 9)# 打印结果ol.display()# 输出：#   0   5   0   0#   0   0   8   0#   3   0   0   0#   0   0   0   9

总结

通过本教程，你已经掌握了Python十字链表的基本原理与实现方法。这种结构是稀疏矩阵存储的经典方案，特别适合内存敏感的场景。掌握它不仅能提升你的数据结构实现能力，还能为后续学习图论、数值计算等打下基础。

记住，真正的理解来自于动手实践。尝试修改代码，添加删除元素、矩阵加法等功能，深化对链表操作教程的理解吧！