稀疏数组、广义表与矩阵压缩存储

在线性结构和字符串这些基础内容之后，数据结构学习很快就会碰到一个现实问题：并不是所有数据都适合“老老实实一个位置存一个值”这种最直白的方式。很多时候，原始数据虽然看起来规模很大，但真正有效的信息其实很少。如果还按完整数组或完整矩阵存，就会造成大量空间浪费。

这也是为什么教材里会专门引出稀疏数组、广义表和矩阵压缩存储。它们背后的共同思想其实很统一：

当数据分布具有明显结构特征时，可以利用这些特征改变存储方式，用更少的空间表示同样的信息。

所以这一篇的重点，不是把三个概念孤零零地背下来，而是看清它们都在解决同一类问题：如何在“逻辑结构不变”的前提下，用更经济的方式组织复杂数据。

一、为什么需要压缩存储

最朴素的存储方式通常是“位置全展开”。例如：

  • 一维数组按下标完整存；
  • 二维矩阵按行列完整展开；
  • 嵌套结构逐层按普通节点展开。

这种方式的优点是简单、访问直接，但缺点也很明显：

  • 如果大量位置都是默认值，就会浪费空间；
  • 如果结构本身是嵌套不规则的，普通线性存储不够灵活；
  • 如果只关心非零或非空部分，完整展开会让有效信息被大量“空白”稀释。

所以压缩存储的本质是：

  • 不存无意义的重复信息；
  • 或者把结构特征编码进存储方式里；
  • 让空间使用更贴近真实有效数据量。

二、什么是稀疏数组

稀疏数组通常是指：

在一个规模较大的数组或矩阵中，绝大多数元素都为 0 或默认值，真正非零的元素非常少。

例如一个 1000 × 1000 的棋盘，如果只有十几个位置上有棋子，那么完整存储 100 万个格子显然非常浪费。

这时就可以把重点转移到“记录非零元素”上，而不是把所有空位都存下来。

三、稀疏数组最常见的表示思路

1. 三元组表示法

这是最经典的方式。

对于每一个非零元素，只记录三项：

  • 行号；
  • 列号；
  • 元素值。

于是原本巨大的矩阵，就可以被压缩成一张“非零元素清单”。

这种方式的优点是：

  • 空间只和非零元素个数有关；
  • 结构直观；
  • 很适合稀疏程度很高的矩阵。
2. 行逻辑更强的变体

有时还会额外按行组织这些非零元素，方便按行访问或转置操作。

也就是说，三元组只是基础形式，围绕它还能发展出更适合不同操作需求的结构。

四、稀疏数组适合哪些场景

典型场景包括：

  • 棋盘和地图表示；
  • 图的邻接关系表示；
  • 科学计算中的大型稀疏矩阵；
  • 推荐系统和特征工程中的稀疏特征向量；
  • 搜索和机器学习中的高维稀疏表示。

这些问题的共同点都是：

  • 数据维度大；
  • 有效项少；
  • 直接完整存储不划算。

五、什么是广义表

广义表的概念相对更抽象一些。它可以理解成：

表中的元素既可以是原子，也可以是另一个表。

例如：

1
(a, b, (c, d), (e, (f, g)))

这里：

  • a、b 可以看成原子；
  • (c, d) 本身又是一个子表；
  • (e, (f, g)) 则是更深一层的嵌套表。

所以广义表的核心不在于“元素排成一列”，而在于它允许层级和嵌套结构出现。

六、广义表为什么重要

因为它提供了一种更灵活的结构表达方式。

普通线性表默认所有元素处于同一层；但现实数据中，经常会出现：

  • 目录树；
  • 表达式树；
  • 嵌套配置；
  • JSON / Lisp 这类层级数据；
  • 编译器中的语法结构。

广义表虽然在现代工程里未必以这个名字高频出现，但它背后的思想非常重要：

一个数据项本身可以继续包含结构，而不是只包含简单值。

从这个角度看，广义表其实是理解递归结构和树形结构的一块桥梁。

七、广义表的常见特征

1. 可以递归定义

广义表非常适合用递归方式描述，因为子表本身仍然是表。

2. 长度和深度是两个不同概念
  • 长度通常指最外层元素个数；
  • 深度则反映嵌套层数。
3. 存储实现往往更依赖链式结构

因为嵌套层次不规则，用纯顺序存储不够自然。

这也是为什么广义表在概念上很适合帮助理解“结构中的结构”。

八、什么是矩阵压缩存储

矩阵压缩存储可以看成是把“稀疏思想”进一步细化后的结果。

因为除了“非零元素少”这种稀疏情形，还有一些矩阵虽然不是普通意义上的稀疏矩阵，但它本身具有特殊结构。例如：

  • 对称矩阵；
  • 上三角矩阵；
  • 下三角矩阵；
  • 对角矩阵；
  • 带状矩阵。

这些矩阵里，有很多位置的值并不是随机分布，而是天然可以由结构规律推导出来。

此时如果仍按普通二维数组完整存储，就会重复保存大量冗余信息。

九、对称矩阵为什么适合压缩

以对称矩阵为例，满足：

1
a[i][j] = a[j][i]

这意味着：

  • 主对角线两侧的信息是镜像的；
  • 只保存上三角或下三角的一半数据就够了。

于是我们就可以：

  • 按行或按列把一半元素线性展开；
  • 通过下标映射公式恢复原矩阵位置。

本质上，这是一种用“结构规律”来减少空间占用的做法。

十、三角矩阵、对角矩阵和带状矩阵的思路

它们的共同点都在于：

  • 只有某些区域有意义；
  • 其他区域固定为 0 或固定值；
  • 可以只存有效区域。

例如：

  • 上三角矩阵只保存主对角线及其上方；
  • 对角矩阵只保存对角线元素；
  • 带状矩阵只保存主对角线附近的若干条带。

所以矩阵压缩存储的核心思想并不复杂：

不必忠实存下每一个逻辑位置，而是只存真正有信息量的部分。

十一、压缩存储的代价是什么

节省空间从来不是没有代价的。

1. 访问逻辑更复杂

普通二维数组可以直接 a[i][j] 访问，但压缩后通常需要先做下标映射或查找定位。

2. 更新操作可能更麻烦

如果数据结构经常变化，压缩结构的维护成本可能会上升。

3. 并不适合所有场景

只有在稀疏程度高、结构规律明显，或者空间特别敏感时，压缩存储才真正划算。

这说明数据结构设计永远是权衡：

  • 节省空间；
  • 增加访问复杂度；
  • 根据场景决定是否值得。

十二、这些内容和后面树、图有什么联系

这篇虽然看起来像是“几个离散的小知识点”，但它们其实在为后面很多内容做铺垫。

例如：

  • 广义表帮助理解递归嵌套结构，会自然过渡到树；
  • 稀疏矩阵和压缩表示，会帮助理解图的邻接矩阵与稀疏图存储；
  • 结构规律决定存储方式，这种思想会在后面的 B+ 树、Trie、位图、布隆过滤器中不断出现。

所以这一篇真正要学到的，不只是几个定义，而是一种更一般的存储意识：

数据怎么分布，决定了结构怎么设计。

十三、学习这部分时最容易踩的坑

1. 只记定义，不理解共同思想

这三个主题看似不同，但它们都在做“利用结构特征节省存储”的事。

2. 以为压缩存储一定更好

空间更省不代表整体更优，访问复杂度和实现复杂度也要考虑。

3. 不区分“逻辑结构”和“存储结构”

压缩后逻辑上还是那个矩阵或表，只是底层表示不同。

4. 忽略映射关系

很多压缩结构真正的难点不是“知道能压缩”，而是“知道如何从逻辑位置映射到物理位置”。

总结

稀疏数组、广义表和矩阵压缩存储的重要性，不只是因为它们出现在教材里，而是因为它们共同说明了一件很重要的事：数据结构设计不能只看逻辑形式，还必须看数据分布特征。真正值得先建立起来的，是这些核心认识：

  • 当数据规模大但有效信息少时，完整展开存储会造成明显浪费；
  • 稀疏数组通过只记录非零元素来压缩空间；
  • 广义表通过允许元素继续包含子表，表达更复杂的层级结构；
  • 特殊矩阵可以利用对称性、三角性和带状结构做压缩存储；
  • 压缩存储的本质，是用更复杂的定位逻辑换取更高的空间利用率；
  • 真正学会这一篇，不是会背几个名词，而是知道什么时候应该利用数据分布特征重新设计存储方式。

把这一篇理解透之后，后面再去学树、图和各种高级结构时，你会更容易意识到：很多优秀的数据结构，真正厉害的地方不只是“存得下”，而是“存得更有针对性”。

参考资源：