13.2.1 数组与矩阵知识点概述

数组与矩阵的考试重点不是定义，而是地址计算和压缩存储。只要题目出现二维数组、行优先、列优先、上三角、下三角、对称矩阵，第一反应就应该是“下标映射”。

本模块要解决的问题

问题	对应知识
二维数组元素地址怎么算	行优先/列优先存储公式
为什么数组能随机访问	每个元素长度固定，地址可计算
矩阵为什么能压缩	特殊矩阵存在大量重复或零元素
压缩后如何定位元素	二维下标映射到一维下标

数组与矩阵的关系

矩阵可以看作特殊的二维数组。二维数组的行数和列数可以不同；矩阵通常强调行列构成数学意义上的表格，常见方阵行列数相等。

flowchart LR
  A["一维数组"] --> B["二维数组"]
  B --> C["矩阵"]
  C --> D["对称矩阵"]
  C --> E["三角矩阵"]
  C --> F["稀疏矩阵"]

考题中的三个细节

细节	为什么重要
下标起点	从 0 开始和从 1 开始，公式差一个偏移量
存储顺序	行优先和列优先的偏移量不同
每个元素长度	偏移元素个数要乘以元素存储长度

例如数组 A[m][n]，每个元素占 L 个存储单元，首地址为 a。若下标从 0 开始，则：

行优先：

$$Loc(A[i][j])=a+(i\times n+j)\times L$$

列优先：

$$Loc(A[i][j])=a+(j\times m+i)\times L$$

压缩存储的动机

矩阵如果直接按二维数组存储，会把所有元素都保存下来。但某些矩阵有规律：

矩阵类型	规律	压缩思路
对称矩阵	$a_{ij}=a_{ji}$	只存上三角或下三角
上三角矩阵	主对角线以下为 0 或常数	只存主对角线及其上方
下三角矩阵	主对角线以上为 0 或常数	只存主对角线及其下方
稀疏矩阵	非零元素很少	存三元组 (行, 列, 值)

压缩存储不是为了改变矩阵含义，而是利用规律减少无效空间。

本节例题

单选

计算二维数组元素地址时，必须优先确认的是：

A下标起点、行列规模、存储顺序、元素长度B只需要知道元素值C只需要知道矩阵是否为方阵D只需要知道数组名

自查清单

1. 能否写出下标从 0 开始时的行优先地址公式？
2. 能否解释行优先和列优先为什么不同？
3. 能否说明特殊矩阵为什么可以压缩存储？