Python 数据结构：稀疏矩阵（Sparse Matrix）

# /*
# Python 数据结构：稀疏矩阵（Sparse Matrix）
# --------------------------------------------------------
# 概念：
# 稀疏矩阵中大部分元素为 0，
# 直接存储完整矩阵会浪费空间，
# 因此通常只记录非零元素的位置与数值。
#
# 常见存储方式：
# 1) 三元组表（三元组：row, col, value）
# 2) 字典存储 {(行, 列): 值}
# 3) 使用 SciPy 等库的 CSR/CSC 格式（此处展示纯 Python 实现）
# */

# --------------------------------------------------------
# 示例：构造一个稀疏矩阵（普通二维列表）
matrix = [
    [0, 0, 3, 0],
    [22, 0, 0, 0],
    [0, 0, 0, 7],
    [0, 5, 0, 0]
]

print("原矩阵：")
for row in matrix:
    print(row)

# --------------------------------------------------------
# 方法一：三元组表示法（Triplet Form）
triplets = []

for i in range(len(matrix)):
    for j in range(len(matrix[0])):
        if matrix[i][j] != 0:
            triplets.append((i, j, matrix[i][j]))

print("\n三元组表示：", triplets)

# --------------------------------------------------------
# 方法二：使用字典存储非零元素
sparse_dict = {}

for i in range(len(matrix)):
    for j in range(len(matrix[0])):
        val = matrix[i][j]
        if val != 0:
            sparse_dict[(i, j)] = val

print("\n字典表示：", sparse_dict)

# --------------------------------------------------------
# 稀疏矩阵 → 普通矩阵（通过字典还原）
rows = len(matrix)
cols = len(matrix[0])

recover = [[0 for _ in range(cols)] for _ in range(rows)]

for (i, j), val in sparse_dict.items():
    recover[i][j] = val

print("\n字典还原矩阵：")
for row in recover:
    print(row)

# --------------------------------------------------------
# 示例：稀疏矩阵加法（以字典形式实现）
def sparse_add(A, B):
    """A、B 均为稀疏字典 {(i,j): value}"""
    result = A.copy()
    for key, val in B.items():
        result[key] = result.get(key, 0) + val
        if result[key] == 0:
            del result[key]
    return result

# 创建第二个稀疏矩阵示例
matrix2 = [
    [0, 0, 0, 0],
    [0, 9, 0, 0],
    [0, 0, 0, 7],
    [0, 5, 0, 0]
]

# 转成字典稀疏形式
sparse_dict2 = {}
for i in range(len(matrix2)):
    for j in range(len(matrix2[0])):
        if matrix2[i][j] != 0:
            sparse_dict2[(i, j)] = matrix2[i][j]

added = sparse_add(sparse_dict, sparse_dict2)
print("\n稀疏矩阵相加结果（字典格式）：", added)

# --------------------------------------------------------
# 要点总结：
# 1) 稀疏矩阵适合零值占比极高的数据；
# 2) 三元组与字典是最常用的纯 Python 存储方式；
# 3) 字典方式支持 O(1) 访问效率；
# 4) 稀疏矩阵加法可通过 key 合并实现；
# 5) 大规模稀疏矩阵通常使用专门库（如 SciPy）。
# */

# 原矩阵：
# [0, 0, 3, 0]
# [22, 0, 0, 0]
# [0, 0, 0, 7]
# [0, 5, 0, 0]
#
# 三元组表示：
# [(0, 2, 3), (1, 0, 22), (2, 3, 7), (3, 1, 5)]
#
# 字典表示：
# {(0, 2): 3, (1, 0): 22, (2, 3): 7, (3, 1): 5}
#
# 字典还原矩阵：
# [0, 0, 3, 0]
# [22, 0, 0, 0]
# [0, 0, 0, 7]
# [0, 5, 0, 0]
#
# 稀疏矩阵相加结果（字典格式）：
# {(0, 2): 3, (1, 0): 22, (2, 3): 14, (3, 1): 10, (1, 1): 9}