掌握多维数组的行主序和列主序地址计算,以及对称、三角、稀疏和三对角矩阵的压缩存储与下标映射。
# 一、多维数组的存储
多维数组在内存中仍是一段线性连续空间;二维下标只是逻辑视图。设二维数组 有 行、 列,元素大小为 字节,首元素 的地址为 。
# 1. 行主序与列主序
行主序先存完整的一行,再存下一行。第 行、第 列元素的线性下标为 :
C、C++ 通常采用行主序。列主序先存完整的一列,再存下一列,线性下标为 :
flowchart LR
subgraph 行主序
R0["A[0][0] A[0][1] A[0][2]"] --> R1["A[1][0] A[1][1] A[1][2]"]
end
subgraph 列主序
C0["A[0][0] A[1][0]"] --> C1["A[0][1] A[1][1]"] --> C2["A[0][2] A[1][2]"]
end若题目给出下标下界 ,行主序的线性下标应写为 。先统一下标基准,再代入公式,能避免绝大多数地址题错误。
例题 3.5:二维数组地址计算
设 int 类型占 4 字节,数组 A [3][4] 按行主序存储,A [0][0] 地址为 100。求 A [2][1] 地址。
【解】 线性下标为 ,故地址为
# 二、对称矩阵与三角矩阵
# 1. 对称矩阵
阶对称矩阵满足 ,只需保存主对角线及其下方或上方的一半元素,共
个元素。
以下使用零基下标,并按行优先压缩保存下三角区。设一维数组为 B,则
其中 是 B 的下标。第二种情况利用 转而查找下三角中的 。
# 2. 三角矩阵
上三角矩阵中主对角线及其上方元素有意义,下方元素往往均为同一个常量 ;下三角矩阵与之对称。压缩存储除保存有效三角区外,通常额外保留一个单元保存常量 。
对零基 阶上三角矩阵,按行优先存储上三角区时, 的下标为
若 ,则访问额外常量单元
压缩下标公式与下标起点、按行或按列存储、选择上三角还是下三角均有关。不要把某个公式脱离约定死记;先数清当前元素之前已经存入多少个有效元素。
# 三、稀疏矩阵
当 矩阵只有 个非零元,且 时,完整数组会浪费大量空间。稀疏矩阵可只保存非零元及其行、列位置。
# 1. 三元组表
三元组表常按行序优先保存 ,并记录矩阵行数、列数和非零元数。空间复杂度为 ,但按指定行列随机查询通常需要顺序扫描,最坏为 。
1 |
|
三元组表结构简单,适合顺序输出、转置和稀疏矩阵相加等按非零元扫描的任务。
# 2. 十字链表
若需要频繁按行和按列访问,可采用十字链表。每个非零结点同时属于一条行链和一条列链,结点包含行号、列号、值以及 right、down 两个链接;另有 rhead、chead 分别索引各行、各列的首结点。
flowchart LR
R1[rhead 1] --> X11["(1,1,3)"]
X11 --> X13["(1,3,5)"]
C1[chead 1] --> X11
C3[chead 3] --> X13
X11 -.down.-> X31["(3,1,2)"]
R3[rhead 3] --> X311 | typedef struct CrossNode { |
十字链表只保存非零元并支持按行、按列遍历;插入或删除结点时需同时维护对应行链和列链。
# 四、三对角矩阵
阶三对角矩阵仅主对角线、上对角线和下对角线可能非零,非零元总数为
若采用零基下标并逐行保存非零带状元素,则满足 的元素可映射为
例如第 0 行保存 ,第 1 行保存 ;最后一行只保存 。若 ,元素为零或题设给定的默认值,不需要存入压缩数组。
另一种等价实现是分别使用下对角线、主对角线、上对角线三个数组;它们的有效长度分别为 。
# 五、考场检查清单
- 地址题先确认行主序或列主序,再确认下标从 0 还是从 1 开始。
- 对称矩阵压缩只保存一半加主对角线,共 个元素。
- 三角矩阵的另一半若为常量,应额外保存该常量或按题设直接返回。
- 三元组表保存非零元,按位置查找一般不是 ;十字链表以行链和列链支持双向组织。
- 三对角矩阵非零元数量是 ,不是 。
