典型应用

数组与矩阵的压缩存储并不是纯理论:从图像处理到大规模方程组求解,数据的存储布局往往决定了程序能跑多快。本页把前面讲过的顺序存储、地址计算与压缩存储公式放回真实场景,说明什么时候用普通二维数组就够用、什么时候值得为特殊矩阵付出额外的下标换算代价。

数组的典型应用

  • 数据存储:把同类型的数据放进一段连续内存,靠「基址 + 下标 × 元素长度」直接定位元素,是几乎所有程序的基础结构。
  • 查找与排序:二分查找依赖数组的有序性与随机访问能力;插入排序、归并排序、快排等经典排序算法也都建立在数组之上。
  • 矩阵运算:图像处理、线性代数、状态空间计算都要做矩阵乘法,数组的连续存储直接决定了访存模式与缓存命中率。

稀疏矩阵的典型应用

  • 图的邻接矩阵:稀疏图用邻接矩阵存储时绝大多数位置是 0,改用三元组或十字链表只存非零元素,可以把存储量从 O(n2)O(n^2) 降到与非零个数成正比。
  • 科学计算:偏微分方程的数值解、有限元法产生的矩阵往往只有主对角线附近非零,压缩存储是标准做法。
  • 大规模方程组求解:稀疏矩阵分解(LU、Cholesky)能利用零元素结构跳过无谓运算,是求解器性能的关键。

选型上的取舍

场景推荐做法原因
元素密度高、需要频繁按下标访问普通二维数组地址计算简单,访问是 O(1)O(1)
结构特殊(对称、三角、三对角)按压缩公式存储存储量可减半甚至更多,代价是下标要换算
非零元素很少三元组 / 十字链表存储量与实际信息量成正比,但随机访问变慢

常见误区

压缩存储省的是空间,付出的是「按下标定位元素」不再是一次乘加,而可能变成一次查表甚至一次遍历。因此只有在矩阵结构确实特殊、且访问以整块遍历为主的场景下,压缩存储才划算;如果代码里频繁地对压缩后的矩阵按下标随机访问,往往得不偿失。

回到本章的公式:对称矩阵的下标换算是 k=i(i+1)2+jk = \frac{i(i+1)}{2} + j(i≥ji \ge j),三对角矩阵是 k=2i+jk = 2i + j,稀疏矩阵三元组则是 (行,列,值)(行, 列, 值) 三个数的组合。把这三个式子记牢,加上上面这张选型表,就能在具体题目里判断该用哪种存储方式。

发现内容有问题?

告诉我们哪里需要改进。