数组的顺序存储说穿了就是把逻辑上的多维表格压成内存里的一根长条。数据结构里讲数组重点从来不是“怎么声明”而是“给定下标怎么在 O(1) 时间算出元素地址”。一维、二维、三维直到 n 维数组的元素地址计算考研大题、C语言指针题、嵌入式查表、LabVIEW 数组处理、Simulink 读数组底层都绕不开这个公式。很多人学的时候觉得一维很简单二维也能画个图到了三维、n维就靠背结果一换下标起点、一换行优先列优先立刻翻车。我把这类题拆成一句最土的话元素地址 起始地址 前面有多少个元素 × 每个元素占几字节。真正要练的是快速数清楚“前面到底有多少个元素”。下面从一维推到 n 维配图、配公式、配可运行代码再把我自己踩过的坑和考研题里最阴的易错点一起摊开。适合准备数据结构期末、考研 408、C语言进阶、嵌入式/工控数据处理的人也适合只记得“数组就是连续内存”但不会推地址的新手。1. 数组顺序存储到底在存什么1.1 连续内存与随机访问数组的顺序存储指的是逻辑上相邻的元素在物理内存里也相邻。假设一个元素占 L 个字节起始地址为 Base那么内存长这样地址: Base BaseL Base2L Base3L Base4L 下标: 0 1 2 3 4 元素: a[0] a[1] a[2] a[3] a[4]这种“连续铺开”的存法带来两个结果。第一随机访问很快给下标就能算地址不需要从头遍历第二插入、删除很贵因为要保持连续性平均要移动一堆元素。数组的地址计算之所以成立就是因为每个元素大小固定、排列顺序固定。你可以把它想成一排储物柜。每个柜子大小一样编号连续。知道第一个柜子的编号和柜子宽度就能立刻算出第 k 个柜子的位置。数组地址计算就是“柜子编号换算”没有任何神秘之处。1.2 地址公式本质数前置元素不管几维数组地址公式都遵守同一个骨架LOC(a[i]) 起始地址 前置元素个数 × 单个元素字节数一维数组里下标 i 前面有 i 个元素所以 LOC(a[i]) Base i × L。二维数组里如果按行优先存储a[i][j] 前面有“前 i 行全部元素”加上“本行前 j 个元素”所以前置个数是 i × 列数 j。三维数组也一样先数前面多少页再数前面多少行最后数本行前面多少列。所以别急着背公式。先问自己这个元素前面完整地跨过了几个维度块每个维度块里有多少个元素最后剩多少个零头把这个问题回答清楚公式自己就长出来了。1.3 行优先与列优先到底谁先谁后行优先也叫按行存储意思是先铺第一行再铺第二行直到最后一行。对于二维数组元素变化最快的是列下标 j列下标跑完一行的长度后行下标 i 才加一。C、C、Java、C#、Python 的列表嵌套在逻辑上都常按行优先理解Fortran、MATLAB、R、Julia 默认按列优先。列优先则相反先铺第一列再铺第二列列下标变化最慢行下标变化最快。用一句话记行优先是“一行一行扫”列优先是“一列一列扫”。考试题里只要出现“按行优先”“按列优先”就必须先确认存储顺序再代公式。很多人算错不是不会公式而是把行列优先搞反了。行优先存储 3×3 数组 a[0][0] a[0][1] a[0][2] | a[1][0] a[1][1] a[1][2] | a[2][0] a[2][1] a[2][2] 列优先存储 3×3 数组 a[0][0] a[1][0] a[2][0] | a[0][1] a[1][1] a[2][1] | a[0][2] a[1][2] a[2][2]图中竖线只是帮助分组真实内存里没有分隔所有元素仍然是一根连续长条。2. 一维数组地址计算所有多维公式的底座2.1 一维数组地址公式推导设一维数组 a起始地址为 Base每个元素占 L 字节下标从 0 开始。那么LOC(a[i]) Base i × L推导很简单a[0] 在 Basea[1] 在 Base La[2] 在 Base 2L所以第 i 个元素前面有 i 个元素每个 L 字节偏移量就是 i × L。举例Base 1000L 4求 a[3] 的地址。a[3] 前面有 a[0]、a[1]、a[2] 三个元素偏移 3 × 4 12 字节所以 LOC(a[3]) 1000 12 1012。内存图如下Base1000, L4 a[0] - 1000 a[1] - 1004 a[2] - 1008 a[3] - 1012 a[4] - 1016如果下标从 1 开始比如数组 a[1..n]起始地址 Base 对应 a[1]那么 a[i] 前面有 i - 1 个元素LOC(a[i]) Base (i - 1) × L这就是下标起点不同带来的唯一变化。公式本身没有变仍然是“前面有多少个元素”。2.2 下标从 0 与从 1 的差异考试里最容易被坑的地方就是下标起点。有的教材用 0 开头有的伪代码用 1 开头C语言真实数组一定从 0 开始。看到一个题先圈出两个信息起始地址对应哪个下标、题目要求下标从几开始。下标起点公式说明从 0 开始LOC(a[i]) Base i × LBase 是 a[0] 的地址从 1 开始LOC(a[i]) Base (i - 1) × LBase 是 a[1] 的地址如果题目说“数组 A[1..10]首地址为 1000每个元素 2 字节求 A[6] 地址”那就用从 1 开始的公式1000 (6 - 1) × 2 1010。如果你顺手写成 1000 6 × 2 1012就正好错一个元素。这个错误在考研选择题里非常常见。2.3 用 C 语言打印地址验证理论说完动手验证最稳。下面这段代码用%p打印地址用sizeof算元素大小再用指针差验证偏移。#include stdio.h int main(void) { int a[5] {10, 20, 30, 40, 50}; int L sizeof(int); printf(a[0] address %p\n, (void*)a[0]); printf(a[3] address %p\n, (void*)a[3]); printf(sizeof(int) %d\n, L); // 指针相减得到的是元素个数不是字节数 ptrdiff_t diff a[3] - a[0]; printf(a[3] - a[0] %td 个元素\n, diff); printf(字节偏移 %td\n, diff * L); return 0; }实测时你会发现a[3] - a[0]输出 3而字节偏移是 3 × 4 12。这里有个细节指针减法会自动除以元素大小所以直接打印指针差并不等于字节偏移。排查地址问题时如果你用%p看十六进制地址最好转换成十进制再算否则容易在 0x 前缀里绕晕。注意sizeof(int)在多数桌面平台是 4但在一些嵌入式平台可能是 2 或 8。地址计算题如果没有给元素大小通常会说明“每个元素占 d 个字节”没有说明就不能默认 4。3. 二维数组地址计算行优先、列优先与参数推导3.1 行优先存储公式设二维数组 A[m][n]m 行 n 列起始地址 Base每个元素 L 字节下标从 0 开始。行优先存储时内存顺序是a[0][0], a[0][1], ..., a[0][n-1], a[1][0], a[1][1], ..., a[1][n-1], ... a[m-1][0], ..., a[m-1][n-1]求 a[i][j] 的地址先数前面完整的 i 行每行 n 个元素共 i × n 个再数本行前面 j 个元素。所以前置元素个数为 i × n jLOC(a[i][j]) Base (i × n j) × L如果下标从 1 开始数组为 A[1..m][1..n]那么 a[i][j] 前面有 (i - 1) 行每行 n 个本行前面有 (j - 1) 个LOC(a[i][j]) Base ((i - 1) × n (j - 1)) × L3.2 列优先存储公式列优先存储时内存顺序变成先第一列再第二列a[0][0], a[1][0], ..., a[m-1][0], a[0][1], a[1][1], ..., a[m-1][1], ... a[0][n-1], ..., a[m-1][n-1]求 a[i][j]前面有完整的 j 列每列 m 个元素共 j × m 个本列前面有 i 个元素。所以LOC(a[i][j]) Base (j × m i) × L如果下标从 1 开始LOC(a[i][j]) Base ((j - 1) × m (i - 1)) × L注意列优先里先乘的是列下标 j再乘行数 m。很多人会写成 j × n i这是典型错误。列方向上一列有多长是行数 m不是列数 n。3.3 实例计算一个 3×4 数组两种存法对比设int a[3][4]Base 1000L 4下标从 0 开始。求 a[1][2] 的地址。行优先offset i × n j 1 × 4 2 6 地址 1000 6 × 4 1024列优先offset j × m i 2 × 3 1 7 地址 1000 7 × 4 1028对比表如下存储方式前置元素个数地址计算结果行优先1×42 61000 6×41024列优先2×31 71000 7×41028行优先内存展开图行优先: a[0][0] a[0][1] a[0][2] a[0][3] | a[1][0] a[1][1] a[1][2] a[1][3] | a[2][0] ... 1000 1004 1008 1012 1016 1020 1024 1028 1032 ^目标列优先内存展开图列优先: a[0][0] a[1][0] a[2][0] | a[0][1] a[1][1] a[2][1] | a[0][2] a[1][2] a[2][2] | ... 1000 1004 1008 1012 1016 1020 1024 1028 1032 ^目标同一个 a[1][2]行优先落在 1024列优先落在 1028。这就是为什么地址计算题必须明确存储顺序。3.4 二维数组传参为什么必须带列数热搜里有个很典型的问题“c语言传参传二维数组要有个数字”。这个数字就是列数。C语言里二维数组的数组名会退化成指向第一行的指针形参通常写成void func(int a[][4], int row) { // a[i][j] 等价于 *(*(a i) j) }编译器要把a[i][j]解释成*(*(a i) j)。其中a i要跳过 i 行每一行有多大必须是列数 × sizeof(int)。如果形参只写int a[][]编译器不知道一行多长就无法计算行跨度所以编译不过。正确写法还有int (*a)[4]本质上也是指向“含 4 个 int 的数组”的指针。我见过有人写成int **a去接二维数组结果访问崩溃。int **和二维数组名不是一回事前者是指针的指针后者是指向数组的指针。二维数组传参时列数不是可选项而是地址计算的核心参数。4. 三维数组地址计算从二维向上扩展4.1 三维数组的内存布局设三维数组 A[d1][d2][d3]你可以把它看成 d1 个“页”每页是一个 d2 行 d3 列的二维数组。行优先存储时先放第 0 页再放第 1 页每页内部按行优先铺开页0: a[0][0][0] a[0][0][1] ... a[0][0][d3-1] a[0][1][0] a[0][1][1] ... a[0][1][d3-1] ... 页1: a[1][0][0] a[1][0][1] ... a[1][0][d3-1] ...所以三维数组并没有多神秘它只是“页、行、列”三级结构。行优先时最后一维 k 变化最快然后 j 变化i 变化最慢。4.2 行优先公式推导求 a[i][j][k] 的前置元素个数前面完整的页有 i 页每页有 d2 × d3 个元素共 i × d2 × d3 个。本页前面完整的行有 j 行每行 d3 个元素共 j × d3 个。本行前面有 k 个元素。加起来行优先 offset i × d2 × d3 j × d3 k地址LOC(a[i][j][k]) Base (i × d2 × d3 j × d3 k) × L如果下标从 1 开始把 i、j、k 分别换成 i-1、j-1、k-1 代入即可。4.3 列优先公式推导列优先时变化最快的是第一维 i然后是第二维 j最后才是第三维 k。内存顺序相当于先固定 k 和 j把 i 跑完再换 j最后换 k。前置元素个数完整的 k 层有 k 层每层有 d1 × d2 个元素共 k × d1 × d2 个。本层前面完整的 j 列有 j 列每列 d1 个元素共 j × d1 个。本列前面有 i 个元素。所以列优先 offset k × d1 × d2 j × d1 i地址LOC(a[i][j][k]) Base (k × d1 × d2 j × d1 i) × L这个公式可以记成“越靠前的维度乘得越多”。列优先里 i 是最快维度所以它只乘 1j 要乘 d1k 要乘 d1 × d2。4.4 实例计算a[1][1][2] 到底在哪设int a[2][3][4]Base 2000L 4下标从 0 开始。求 a[1][1][2]。行优先offset i × d2 × d3 j × d3 k 1 × 3 × 4 1 × 4 2 12 4 2 18 地址 2000 18 × 4 2072列优先offset k × d1 × d2 j × d1 i 2 × 2 × 3 1 × 2 1 12 2 1 15 地址 2000 15 × 4 2060对比表存储方式公式代入前置个数地址行优先1×3×4 1×4 2182072列优先2×2×3 1×2 1152060这里再提醒一个坑不要用 a[1][2][3] 这种靠边的下标去验证公式。因为有些三维数组坐标在行优先和列优先下的偏移量会碰巧相等比如 1×3×4 2×4 3 23而 3×2×3 2×2 1 23。碰巧一样不代表公式对了换 a[1][1][2] 立刻现原形。5. n 维数组地址计算一个求和公式统一所有维度5.1 n 维行优先通式设 n 维数组 A[d1][d2]...[dn]下标从 0 开始起始地址 Base每个元素 L 字节。行优先存储时第一维变化最慢第 n 维变化最快。求 A[i1][i2]...[in] 的前置元素个数就是依次计算每个维度的贡献i1 每增加 1跨过后面的 d2 × d3 × ... × dn 个元素。i2 每增加 1跨过后面的 d3 × d4 × ... × dn 个元素。...i_{n-1} 每增加 1跨过 dn 个元素。in 每增加 1跨过 1 个元素。所以行优先偏移量offset i1 × (d2×d3×...×dn) i2 × (d3×d4×...×dn) ... i_{n-1} × dn in用求和符号写offset Σ_{k1}^{n} i_k × Π_{jk1}^{n} d_j其中当 k n 时后面的乘积约定为 1。地址就是LOC Base offset × L如果题目下标从 1 开始把每个 i_k 替换成 i_k - 1 再代入。5.2 n 维列优先通式列优先时第一维变化最快第 n 维变化最慢。每个维度的步长变成“前面所有维度的乘积”i1 每增加 1跨过 1 个元素。i2 每增加 1跨过 d1 个元素。i3 每增加 1跨过 d1 × d2 个元素。...in 每增加 1跨过 d1 × d2 × ... × d_{n-1} 个元素。所以列优先偏移量offset i1 i2 × d1 i3 × d1 × d2 ... in × (d1 × d2 × ... × d_{n-1})用求和符号写offset Σ_{k1}^{n} i_k × Π_{j1}^{k-1} d_j同样k 1 时前面的乘积约定为 1。地址还是LOC Base offset × L5.3 用前缀乘积与后缀乘积快速算手算 n 维地址时不要现场展开一长串乘法容易错。我习惯用“后缀乘积”算行优先用“前缀乘积”算列优先。对于维度 d1, d2, ..., dn行优先的后缀乘积suf[1] d2 × d3 × ... × dn suf[2] d3 × d4 × ... × dn ... suf[n-1] dn suf[n] 1然后offset i1×suf[1] i2×suf[2] ... in×suf[n]列优先的前缀乘积pre[1] 1 pre[2] d1 pre[3] d1 × d2 ... pre[n] d1 × d2 × ... × d_{n-1}然后offset i1×pre[1] i2×pre[2] ... in×pre[n]举个例子四维数组 A[2][3][4][5]下标从 0 开始求 A[1][1][2][3] 的行优先偏移。行优先后缀乘积suf[1] 3×4×5 60 suf[2] 4×5 20 suf[3] 5 suf[4] 1 offset 1×60 1×20 2×5 3×1 60 20 10 3 93列优先前缀乘积pre[1] 1 pre[2] 2 pre[3] 2×3 6 pre[4] 2×3×4 24 offset 1×1 1×2 2×6 3×24 1 2 12 72 87如果 Base 5000L 4那么行优先地址 5000 93×4 5372列优先地址 5000 87×4 5348。用前缀/后缀乘积比直接记公式更不容易漏项。5.4 代码实现通用地址计算手算会了最好再用代码写一遍通用函数。下面给出 Python 版本支持任意维度、行优先和列优先。def row_major_offset(indices, dims): 行优先第一维变化最慢最后一维变化最快 n len(dims) offset 0 for k in range(n): # 计算后缀乘积 dims[k1] * ... * dims[n-1] stride 1 for j in range(k 1, n): stride * dims[j] offset indices[k] * stride return offset def col_major_offset(indices, dims): 列优先第一维变化最快最后一维变化最慢 offset 0 for k in range(len(dims)): # 计算前缀乘积 dims[0] * ... * dims[k-1] stride 1 for j in range(0, k): stride * dims[j] offset indices[k] * stride return offset dims [2, 3, 4, 5] idx [1, 1, 2, 3] print(row_major_offset(idx, dims)) # 93 print(col_major_offset(idx, dims)) # 87C 语言版本更贴近考试和嵌入式场景#include stdio.h long long row_major_offset(const int idx[], const int dims[], int n) { long long offset 0; for (int k 0; k n; k) { long long stride 1; for (int j k 1; j n; j) { stride * dims[j]; } offset (long long)idx[k] * stride; } return offset; } long long col_major_offset(const int idx[], const int dims[], int n) { long long offset 0; for (int k 0; k n; k) { long long stride 1; for (int j 0; j k; j) { stride * dims[j]; } offset (long long)idx[k] * stride; } return offset; } int main(void) { int dims[] {2, 3, 4, 5}; int idx[] {1, 1, 2, 3}; int n 4; long long base 5000; int elem_size 4; long long off_row row_major_offset(idx, dims, n); long long off_col col_major_offset(idx, dims, n); printf(row offset %lld, addr %lld\n, off_row, base off_row * elem_size); printf(col offset %lld, addr %lld\n, off_col, base off_col * elem_size); return 0; }这段代码里用long long不是多此一举。高维数组的维度乘积可能非常大用int很容易溢出。比如 10 维每维长度 10总元素数就是 10^1032 位int根本装不下。做动态数组、稀疏矩阵映射、多维查表时地址计算溢出是很隐蔽的 bug查起来非常痛苦。6. 常见问题与排查技巧实录6.1 常见错误速查表现象可能原因快速排查行优先算成列优先把 i×nj 和 j×mi 搞反先画内存展开图看谁先变化下标从 1 开始却按 0 算少减了 1圈出题目起点统一替换成 i-1、j-1忘乘元素大小只算了元素个数地址 Base offset × L二维数组传参编译失败形参没写列数写成int a[][4]或int (*a)[4]三维列优先公式写错乘错维度长度列优先乘的是前面维度的乘积地址越界维度算错或下标超范围打印 offset 和总元素数对比高维数组偏移溢出用了 int改用 long long 或 size_tC语言int **接二维数组崩溃类型不匹配二维数组名不是二级指针6.2 考研与期末考试易错点考研数据结构里地址计算常和“行优先/列优先”“下标从 0/1 开始”“元素字节数”组合出题。典型题数组 A[1..8][1..10]按行优先存储首地址 1000每个元素 2 字节求 A[5][7] 地址。先看下标从 1 开始行优先公式offset (i - 1) × n (j - 1) (5 - 1) × 10 (7 - 1) 4 × 10 6 46 地址 1000 46 × 2 1092如果换成列优先offset (j - 1) × m (i - 1) (7 - 1) × 8 (5 - 1) 6 × 8 4 52 地址 1000 52 × 2 1104这类题我自己的做题顺序固定为四步第一步看存储顺序第二步看下标起点第三步看元素大小第四步套公式并检查 offset 是否小于总元素数。总元素数就是所有维度长度相乘。如果算出的 offset 大于等于总元素数必定错。这个检查花不了几秒但能救回很多粗心分。王道数据结构、数据结构期末复习里还会考“数组是一种随机存取结构”“数组的顺序存储需要连续空间”“多维数组可以看成线性表的推广”。这些概念题背后的支撑就是地址公式。理解公式概念就不会死记。6.3 实操排查心得我调试地址问题时最常用的一招是“小数组打印地址差”。不要一上来就搞 4 维、5 维先用int a[2][3]或int a[2][2][2]打印每个元素的地址看差值是不是 L。然后改变下标观察地址增长方向。行优先时a[0][1]和a[0][0]差 La[1][0]和a[0][0]差 n×L。列优先的库或语言里差值方向反过来。第二招是“画格子标地址”。拿一张纸画两行三列每个格子写元素名再在下面标地址。然后按行优先从左到右、从上到下编号再按列优先从上到下、从左到右编号。编号就是 offset。图画三次比背十个公式管用。第三招是“用通用函数反查”。写一个row_major_offset和一个col_major_offset把考试题的维度、下标、Base、L 都输进去看结果是否和手算一致。做 C语言动态数组时经常用一维malloc模拟二维int rows 3, cols 4; int *a (int*)malloc(rows * cols * sizeof(int)); #define A(i, j) a[(i) * cols (j)]这里的(i) * cols (j)就是二维行优先偏移。如果哪天把cols写成rows访问就会错位。这个 bug 在图像处理、矩阵运算、LabVIEW 与 Simulink 数据交互里都很常见因为外部数据经常按行优先传来而某些数学工具默认列优先。数组转字符串、数组去重、对象数组处理时如果底层索引换算错了表现可能是数据串行、图像花屏、查表结果整体偏移不一定是程序崩溃排查难度更高。我的建议很直接凡是遇到多维数组地址先确认存储顺序再确认下标起点最后用“前面有多少个元素”推一遍。公式可以忘这个思路不能丢。把一维、二维、三维各画一遍图n 维公式自然就是“后缀乘积”和“前缀乘积”两种写法。真正到了考场或者项目现场能救你的不是背下来的长公式而是你知道每一步在数什么。
一维到n维数组地址计算：行优先列优先与C语言验证
数组的顺序存储说穿了就是把逻辑上的多维表格压成内存里的一根长条。数据结构里讲数组重点从来不是“怎么声明”而是“给定下标怎么在 O(1) 时间算出元素地址”。一维、二维、三维直到 n 维数组的元素地址计算考研大题、C语言指针题、嵌入式查表、LabVIEW 数组处理、Simulink 读数组底层都绕不开这个公式。很多人学的时候觉得一维很简单二维也能画个图到了三维、n维就靠背结果一换下标起点、一换行优先列优先立刻翻车。我把这类题拆成一句最土的话元素地址 起始地址 前面有多少个元素 × 每个元素占几字节。真正要练的是快速数清楚“前面到底有多少个元素”。下面从一维推到 n 维配图、配公式、配可运行代码再把我自己踩过的坑和考研题里最阴的易错点一起摊开。适合准备数据结构期末、考研 408、C语言进阶、嵌入式/工控数据处理的人也适合只记得“数组就是连续内存”但不会推地址的新手。1. 数组顺序存储到底在存什么1.1 连续内存与随机访问数组的顺序存储指的是逻辑上相邻的元素在物理内存里也相邻。假设一个元素占 L 个字节起始地址为 Base那么内存长这样地址: Base BaseL Base2L Base3L Base4L 下标: 0 1 2 3 4 元素: a[0] a[1] a[2] a[3] a[4]这种“连续铺开”的存法带来两个结果。第一随机访问很快给下标就能算地址不需要从头遍历第二插入、删除很贵因为要保持连续性平均要移动一堆元素。数组的地址计算之所以成立就是因为每个元素大小固定、排列顺序固定。你可以把它想成一排储物柜。每个柜子大小一样编号连续。知道第一个柜子的编号和柜子宽度就能立刻算出第 k 个柜子的位置。数组地址计算就是“柜子编号换算”没有任何神秘之处。1.2 地址公式本质数前置元素不管几维数组地址公式都遵守同一个骨架LOC(a[i]) 起始地址 前置元素个数 × 单个元素字节数一维数组里下标 i 前面有 i 个元素所以 LOC(a[i]) Base i × L。二维数组里如果按行优先存储a[i][j] 前面有“前 i 行全部元素”加上“本行前 j 个元素”所以前置个数是 i × 列数 j。三维数组也一样先数前面多少页再数前面多少行最后数本行前面多少列。所以别急着背公式。先问自己这个元素前面完整地跨过了几个维度块每个维度块里有多少个元素最后剩多少个零头把这个问题回答清楚公式自己就长出来了。1.3 行优先与列优先到底谁先谁后行优先也叫按行存储意思是先铺第一行再铺第二行直到最后一行。对于二维数组元素变化最快的是列下标 j列下标跑完一行的长度后行下标 i 才加一。C、C、Java、C#、Python 的列表嵌套在逻辑上都常按行优先理解Fortran、MATLAB、R、Julia 默认按列优先。列优先则相反先铺第一列再铺第二列列下标变化最慢行下标变化最快。用一句话记行优先是“一行一行扫”列优先是“一列一列扫”。考试题里只要出现“按行优先”“按列优先”就必须先确认存储顺序再代公式。很多人算错不是不会公式而是把行列优先搞反了。行优先存储 3×3 数组 a[0][0] a[0][1] a[0][2] | a[1][0] a[1][1] a[1][2] | a[2][0] a[2][1] a[2][2] 列优先存储 3×3 数组 a[0][0] a[1][0] a[2][0] | a[0][1] a[1][1] a[2][1] | a[0][2] a[1][2] a[2][2]图中竖线只是帮助分组真实内存里没有分隔所有元素仍然是一根连续长条。2. 一维数组地址计算所有多维公式的底座2.1 一维数组地址公式推导设一维数组 a起始地址为 Base每个元素占 L 字节下标从 0 开始。那么LOC(a[i]) Base i × L推导很简单a[0] 在 Basea[1] 在 Base La[2] 在 Base 2L所以第 i 个元素前面有 i 个元素每个 L 字节偏移量就是 i × L。举例Base 1000L 4求 a[3] 的地址。a[3] 前面有 a[0]、a[1]、a[2] 三个元素偏移 3 × 4 12 字节所以 LOC(a[3]) 1000 12 1012。内存图如下Base1000, L4 a[0] - 1000 a[1] - 1004 a[2] - 1008 a[3] - 1012 a[4] - 1016如果下标从 1 开始比如数组 a[1..n]起始地址 Base 对应 a[1]那么 a[i] 前面有 i - 1 个元素LOC(a[i]) Base (i - 1) × L这就是下标起点不同带来的唯一变化。公式本身没有变仍然是“前面有多少个元素”。2.2 下标从 0 与从 1 的差异考试里最容易被坑的地方就是下标起点。有的教材用 0 开头有的伪代码用 1 开头C语言真实数组一定从 0 开始。看到一个题先圈出两个信息起始地址对应哪个下标、题目要求下标从几开始。下标起点公式说明从 0 开始LOC(a[i]) Base i × LBase 是 a[0] 的地址从 1 开始LOC(a[i]) Base (i - 1) × LBase 是 a[1] 的地址如果题目说“数组 A[1..10]首地址为 1000每个元素 2 字节求 A[6] 地址”那就用从 1 开始的公式1000 (6 - 1) × 2 1010。如果你顺手写成 1000 6 × 2 1012就正好错一个元素。这个错误在考研选择题里非常常见。2.3 用 C 语言打印地址验证理论说完动手验证最稳。下面这段代码用%p打印地址用sizeof算元素大小再用指针差验证偏移。#include stdio.h int main(void) { int a[5] {10, 20, 30, 40, 50}; int L sizeof(int); printf(a[0] address %p\n, (void*)a[0]); printf(a[3] address %p\n, (void*)a[3]); printf(sizeof(int) %d\n, L); // 指针相减得到的是元素个数不是字节数 ptrdiff_t diff a[3] - a[0]; printf(a[3] - a[0] %td 个元素\n, diff); printf(字节偏移 %td\n, diff * L); return 0; }实测时你会发现a[3] - a[0]输出 3而字节偏移是 3 × 4 12。这里有个细节指针减法会自动除以元素大小所以直接打印指针差并不等于字节偏移。排查地址问题时如果你用%p看十六进制地址最好转换成十进制再算否则容易在 0x 前缀里绕晕。注意sizeof(int)在多数桌面平台是 4但在一些嵌入式平台可能是 2 或 8。地址计算题如果没有给元素大小通常会说明“每个元素占 d 个字节”没有说明就不能默认 4。3. 二维数组地址计算行优先、列优先与参数推导3.1 行优先存储公式设二维数组 A[m][n]m 行 n 列起始地址 Base每个元素 L 字节下标从 0 开始。行优先存储时内存顺序是a[0][0], a[0][1], ..., a[0][n-1], a[1][0], a[1][1], ..., a[1][n-1], ... a[m-1][0], ..., a[m-1][n-1]求 a[i][j] 的地址先数前面完整的 i 行每行 n 个元素共 i × n 个再数本行前面 j 个元素。所以前置元素个数为 i × n jLOC(a[i][j]) Base (i × n j) × L如果下标从 1 开始数组为 A[1..m][1..n]那么 a[i][j] 前面有 (i - 1) 行每行 n 个本行前面有 (j - 1) 个LOC(a[i][j]) Base ((i - 1) × n (j - 1)) × L3.2 列优先存储公式列优先存储时内存顺序变成先第一列再第二列a[0][0], a[1][0], ..., a[m-1][0], a[0][1], a[1][1], ..., a[m-1][1], ... a[0][n-1], ..., a[m-1][n-1]求 a[i][j]前面有完整的 j 列每列 m 个元素共 j × m 个本列前面有 i 个元素。所以LOC(a[i][j]) Base (j × m i) × L如果下标从 1 开始LOC(a[i][j]) Base ((j - 1) × m (i - 1)) × L注意列优先里先乘的是列下标 j再乘行数 m。很多人会写成 j × n i这是典型错误。列方向上一列有多长是行数 m不是列数 n。3.3 实例计算一个 3×4 数组两种存法对比设int a[3][4]Base 1000L 4下标从 0 开始。求 a[1][2] 的地址。行优先offset i × n j 1 × 4 2 6 地址 1000 6 × 4 1024列优先offset j × m i 2 × 3 1 7 地址 1000 7 × 4 1028对比表如下存储方式前置元素个数地址计算结果行优先1×42 61000 6×41024列优先2×31 71000 7×41028行优先内存展开图行优先: a[0][0] a[0][1] a[0][2] a[0][3] | a[1][0] a[1][1] a[1][2] a[1][3] | a[2][0] ... 1000 1004 1008 1012 1016 1020 1024 1028 1032 ^目标列优先内存展开图列优先: a[0][0] a[1][0] a[2][0] | a[0][1] a[1][1] a[2][1] | a[0][2] a[1][2] a[2][2] | ... 1000 1004 1008 1012 1016 1020 1024 1028 1032 ^目标同一个 a[1][2]行优先落在 1024列优先落在 1028。这就是为什么地址计算题必须明确存储顺序。3.4 二维数组传参为什么必须带列数热搜里有个很典型的问题“c语言传参传二维数组要有个数字”。这个数字就是列数。C语言里二维数组的数组名会退化成指向第一行的指针形参通常写成void func(int a[][4], int row) { // a[i][j] 等价于 *(*(a i) j) }编译器要把a[i][j]解释成*(*(a i) j)。其中a i要跳过 i 行每一行有多大必须是列数 × sizeof(int)。如果形参只写int a[][]编译器不知道一行多长就无法计算行跨度所以编译不过。正确写法还有int (*a)[4]本质上也是指向“含 4 个 int 的数组”的指针。我见过有人写成int **a去接二维数组结果访问崩溃。int **和二维数组名不是一回事前者是指针的指针后者是指向数组的指针。二维数组传参时列数不是可选项而是地址计算的核心参数。4. 三维数组地址计算从二维向上扩展4.1 三维数组的内存布局设三维数组 A[d1][d2][d3]你可以把它看成 d1 个“页”每页是一个 d2 行 d3 列的二维数组。行优先存储时先放第 0 页再放第 1 页每页内部按行优先铺开页0: a[0][0][0] a[0][0][1] ... a[0][0][d3-1] a[0][1][0] a[0][1][1] ... a[0][1][d3-1] ... 页1: a[1][0][0] a[1][0][1] ... a[1][0][d3-1] ...所以三维数组并没有多神秘它只是“页、行、列”三级结构。行优先时最后一维 k 变化最快然后 j 变化i 变化最慢。4.2 行优先公式推导求 a[i][j][k] 的前置元素个数前面完整的页有 i 页每页有 d2 × d3 个元素共 i × d2 × d3 个。本页前面完整的行有 j 行每行 d3 个元素共 j × d3 个。本行前面有 k 个元素。加起来行优先 offset i × d2 × d3 j × d3 k地址LOC(a[i][j][k]) Base (i × d2 × d3 j × d3 k) × L如果下标从 1 开始把 i、j、k 分别换成 i-1、j-1、k-1 代入即可。4.3 列优先公式推导列优先时变化最快的是第一维 i然后是第二维 j最后才是第三维 k。内存顺序相当于先固定 k 和 j把 i 跑完再换 j最后换 k。前置元素个数完整的 k 层有 k 层每层有 d1 × d2 个元素共 k × d1 × d2 个。本层前面完整的 j 列有 j 列每列 d1 个元素共 j × d1 个。本列前面有 i 个元素。所以列优先 offset k × d1 × d2 j × d1 i地址LOC(a[i][j][k]) Base (k × d1 × d2 j × d1 i) × L这个公式可以记成“越靠前的维度乘得越多”。列优先里 i 是最快维度所以它只乘 1j 要乘 d1k 要乘 d1 × d2。4.4 实例计算a[1][1][2] 到底在哪设int a[2][3][4]Base 2000L 4下标从 0 开始。求 a[1][1][2]。行优先offset i × d2 × d3 j × d3 k 1 × 3 × 4 1 × 4 2 12 4 2 18 地址 2000 18 × 4 2072列优先offset k × d1 × d2 j × d1 i 2 × 2 × 3 1 × 2 1 12 2 1 15 地址 2000 15 × 4 2060对比表存储方式公式代入前置个数地址行优先1×3×4 1×4 2182072列优先2×2×3 1×2 1152060这里再提醒一个坑不要用 a[1][2][3] 这种靠边的下标去验证公式。因为有些三维数组坐标在行优先和列优先下的偏移量会碰巧相等比如 1×3×4 2×4 3 23而 3×2×3 2×2 1 23。碰巧一样不代表公式对了换 a[1][1][2] 立刻现原形。5. n 维数组地址计算一个求和公式统一所有维度5.1 n 维行优先通式设 n 维数组 A[d1][d2]...[dn]下标从 0 开始起始地址 Base每个元素 L 字节。行优先存储时第一维变化最慢第 n 维变化最快。求 A[i1][i2]...[in] 的前置元素个数就是依次计算每个维度的贡献i1 每增加 1跨过后面的 d2 × d3 × ... × dn 个元素。i2 每增加 1跨过后面的 d3 × d4 × ... × dn 个元素。...i_{n-1} 每增加 1跨过 dn 个元素。in 每增加 1跨过 1 个元素。所以行优先偏移量offset i1 × (d2×d3×...×dn) i2 × (d3×d4×...×dn) ... i_{n-1} × dn in用求和符号写offset Σ_{k1}^{n} i_k × Π_{jk1}^{n} d_j其中当 k n 时后面的乘积约定为 1。地址就是LOC Base offset × L如果题目下标从 1 开始把每个 i_k 替换成 i_k - 1 再代入。5.2 n 维列优先通式列优先时第一维变化最快第 n 维变化最慢。每个维度的步长变成“前面所有维度的乘积”i1 每增加 1跨过 1 个元素。i2 每增加 1跨过 d1 个元素。i3 每增加 1跨过 d1 × d2 个元素。...in 每增加 1跨过 d1 × d2 × ... × d_{n-1} 个元素。所以列优先偏移量offset i1 i2 × d1 i3 × d1 × d2 ... in × (d1 × d2 × ... × d_{n-1})用求和符号写offset Σ_{k1}^{n} i_k × Π_{j1}^{k-1} d_j同样k 1 时前面的乘积约定为 1。地址还是LOC Base offset × L5.3 用前缀乘积与后缀乘积快速算手算 n 维地址时不要现场展开一长串乘法容易错。我习惯用“后缀乘积”算行优先用“前缀乘积”算列优先。对于维度 d1, d2, ..., dn行优先的后缀乘积suf[1] d2 × d3 × ... × dn suf[2] d3 × d4 × ... × dn ... suf[n-1] dn suf[n] 1然后offset i1×suf[1] i2×suf[2] ... in×suf[n]列优先的前缀乘积pre[1] 1 pre[2] d1 pre[3] d1 × d2 ... pre[n] d1 × d2 × ... × d_{n-1}然后offset i1×pre[1] i2×pre[2] ... in×pre[n]举个例子四维数组 A[2][3][4][5]下标从 0 开始求 A[1][1][2][3] 的行优先偏移。行优先后缀乘积suf[1] 3×4×5 60 suf[2] 4×5 20 suf[3] 5 suf[4] 1 offset 1×60 1×20 2×5 3×1 60 20 10 3 93列优先前缀乘积pre[1] 1 pre[2] 2 pre[3] 2×3 6 pre[4] 2×3×4 24 offset 1×1 1×2 2×6 3×24 1 2 12 72 87如果 Base 5000L 4那么行优先地址 5000 93×4 5372列优先地址 5000 87×4 5348。用前缀/后缀乘积比直接记公式更不容易漏项。5.4 代码实现通用地址计算手算会了最好再用代码写一遍通用函数。下面给出 Python 版本支持任意维度、行优先和列优先。def row_major_offset(indices, dims): 行优先第一维变化最慢最后一维变化最快 n len(dims) offset 0 for k in range(n): # 计算后缀乘积 dims[k1] * ... * dims[n-1] stride 1 for j in range(k 1, n): stride * dims[j] offset indices[k] * stride return offset def col_major_offset(indices, dims): 列优先第一维变化最快最后一维变化最慢 offset 0 for k in range(len(dims)): # 计算前缀乘积 dims[0] * ... * dims[k-1] stride 1 for j in range(0, k): stride * dims[j] offset indices[k] * stride return offset dims [2, 3, 4, 5] idx [1, 1, 2, 3] print(row_major_offset(idx, dims)) # 93 print(col_major_offset(idx, dims)) # 87C 语言版本更贴近考试和嵌入式场景#include stdio.h long long row_major_offset(const int idx[], const int dims[], int n) { long long offset 0; for (int k 0; k n; k) { long long stride 1; for (int j k 1; j n; j) { stride * dims[j]; } offset (long long)idx[k] * stride; } return offset; } long long col_major_offset(const int idx[], const int dims[], int n) { long long offset 0; for (int k 0; k n; k) { long long stride 1; for (int j 0; j k; j) { stride * dims[j]; } offset (long long)idx[k] * stride; } return offset; } int main(void) { int dims[] {2, 3, 4, 5}; int idx[] {1, 1, 2, 3}; int n 4; long long base 5000; int elem_size 4; long long off_row row_major_offset(idx, dims, n); long long off_col col_major_offset(idx, dims, n); printf(row offset %lld, addr %lld\n, off_row, base off_row * elem_size); printf(col offset %lld, addr %lld\n, off_col, base off_col * elem_size); return 0; }这段代码里用long long不是多此一举。高维数组的维度乘积可能非常大用int很容易溢出。比如 10 维每维长度 10总元素数就是 10^1032 位int根本装不下。做动态数组、稀疏矩阵映射、多维查表时地址计算溢出是很隐蔽的 bug查起来非常痛苦。6. 常见问题与排查技巧实录6.1 常见错误速查表现象可能原因快速排查行优先算成列优先把 i×nj 和 j×mi 搞反先画内存展开图看谁先变化下标从 1 开始却按 0 算少减了 1圈出题目起点统一替换成 i-1、j-1忘乘元素大小只算了元素个数地址 Base offset × L二维数组传参编译失败形参没写列数写成int a[][4]或int (*a)[4]三维列优先公式写错乘错维度长度列优先乘的是前面维度的乘积地址越界维度算错或下标超范围打印 offset 和总元素数对比高维数组偏移溢出用了 int改用 long long 或 size_tC语言int **接二维数组崩溃类型不匹配二维数组名不是二级指针6.2 考研与期末考试易错点考研数据结构里地址计算常和“行优先/列优先”“下标从 0/1 开始”“元素字节数”组合出题。典型题数组 A[1..8][1..10]按行优先存储首地址 1000每个元素 2 字节求 A[5][7] 地址。先看下标从 1 开始行优先公式offset (i - 1) × n (j - 1) (5 - 1) × 10 (7 - 1) 4 × 10 6 46 地址 1000 46 × 2 1092如果换成列优先offset (j - 1) × m (i - 1) (7 - 1) × 8 (5 - 1) 6 × 8 4 52 地址 1000 52 × 2 1104这类题我自己的做题顺序固定为四步第一步看存储顺序第二步看下标起点第三步看元素大小第四步套公式并检查 offset 是否小于总元素数。总元素数就是所有维度长度相乘。如果算出的 offset 大于等于总元素数必定错。这个检查花不了几秒但能救回很多粗心分。王道数据结构、数据结构期末复习里还会考“数组是一种随机存取结构”“数组的顺序存储需要连续空间”“多维数组可以看成线性表的推广”。这些概念题背后的支撑就是地址公式。理解公式概念就不会死记。6.3 实操排查心得我调试地址问题时最常用的一招是“小数组打印地址差”。不要一上来就搞 4 维、5 维先用int a[2][3]或int a[2][2][2]打印每个元素的地址看差值是不是 L。然后改变下标观察地址增长方向。行优先时a[0][1]和a[0][0]差 La[1][0]和a[0][0]差 n×L。列优先的库或语言里差值方向反过来。第二招是“画格子标地址”。拿一张纸画两行三列每个格子写元素名再在下面标地址。然后按行优先从左到右、从上到下编号再按列优先从上到下、从左到右编号。编号就是 offset。图画三次比背十个公式管用。第三招是“用通用函数反查”。写一个row_major_offset和一个col_major_offset把考试题的维度、下标、Base、L 都输进去看结果是否和手算一致。做 C语言动态数组时经常用一维malloc模拟二维int rows 3, cols 4; int *a (int*)malloc(rows * cols * sizeof(int)); #define A(i, j) a[(i) * cols (j)]这里的(i) * cols (j)就是二维行优先偏移。如果哪天把cols写成rows访问就会错位。这个 bug 在图像处理、矩阵运算、LabVIEW 与 Simulink 数据交互里都很常见因为外部数据经常按行优先传来而某些数学工具默认列优先。数组转字符串、数组去重、对象数组处理时如果底层索引换算错了表现可能是数据串行、图像花屏、查表结果整体偏移不一定是程序崩溃排查难度更高。我的建议很直接凡是遇到多维数组地址先确认存储顺序再确认下标起点最后用“前面有多少个元素”推一遍。公式可以忘这个思路不能丢。把一维、二维、三维各画一遍图n 维公式自然就是“后缀乘积”和“前缀乘积”两种写法。真正到了考场或者项目现场能救你的不是背下来的长公式而是你知道每一步在数什么。
