数据结构：多维数组在内存中的映射（Address Mapping of Multi-dimensional Arrays）
目录
行主映射（Row-Major Mapping）
列主映射（Column-Major Mapping）
三维数组的性映射公式
行主映射推导
列主映射推导
在内存中，数据只能线性存储（一维地址线），但二维数组是逻辑上的“表格”结构。
所以，编译器必须把二维数组的元素映射到内存中的线性地址。
行主映射（Row-Major Mapping）
行主映射是指：
当我们用一维线性内存来存储二维数组时，优先存储每一整行的所有元素，然后再存下一行，依此类推。
即：
-
一整行的所有元素排在一起
-
然后是下一行...
✅ 举个例子：
声明一个二维数组：
int A[3][4] = {{ 1, 2, 3, 4},{ 5, 6, 7, 8},{ 9, 10, 11, 12}
};
逻辑上我们看成是一个矩阵：
行号\列号 0 1 2 3+---------------------0 | 1 2 3 41 | 5 6 7 82 | 9 10 11 12
内存中的存储顺序（线性展开）
在 行主映射中，这个二维数组在内存中会被展开为：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
也就是按行展开，每行从左到右，一行接一行。
内存结构图示
逻辑结构：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] A[2][1] A[2][2] A[2][3]线性内存中排列顺序（行主映射）：+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 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] | A[2][1] | A[2][2] | A[2][3] |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
地址计算公式（行主映射）
给定二维数组：
int A[M][N]; // M 行 N 列
要访问 A[i][j] 的内存地址，编译器用的公式是：
地址(A[i][j]) = Base + (i × N + j) × sizeof(int)
| 符号 | 含义 |
|---|---|
Base | A[0][0] 的起始地址 |
i | 行号 |
j | 列号 |
N | 每行的元素个数（列数） |
🔍 示例推导：
int A[3][4];
A[2][1] = ?;
-
假设 A[0][0] 存在地址
0x1000 -
每个
int是 4 字节 -
第 2 行第 1 列 → 第几个元素？
(i × N + j) = (2 × 4 + 1) = 9
地址为：
0x1000 + 9 × 4 = 0x1000 + 36 = 0x1024
为什么使用行主映射？
✅ 优点：
| 优点 | 说明 |
|---|---|
| 地址计算简单 | 直接使用公式 (i × 列数 + j) 乘字节大小即可 |
| 兼容指针访问 | 可以使用 *(A + i × 列数 + j) |
| 性能优越 | 按行遍历时，访问顺序匹配内存布局，CPU 缓存命中率高 |
| 易于实现 | C/C++ 的数组在底层就是一块连续的内存 |
在 C 和 C++ 中，所有多维数组都采用行主顺序映射。
所以访问 A[i][j] 时，编译器知道：
→ A[i][j] 是第 i × 列数 + j 个元素，从起始地址向后偏移。
int A[3][4] = { ... };
for (int i = 0; i < 3; ++i)for (int j = 0; j < 4; ++j)sum += A[i][j]; // 顺序正好匹配内存布局，访问高效
列主映射（Column-Major Mapping）
在列主映射中，二维数组在内存中按照：
先存整列，再存下一列的方式线性排列。
也就是说：
-
优先将第 1 列的所有元素依次存入内存
-
然后是第 2 列的所有元素
-
接着是第 3 列，以此类推
我们定义一个二维数组：
int A[3][4] = {{ 1, 2, 3, 4},{ 5, 6, 7, 8},{ 9, 10, 11, 12}
};
按列主映射，内存线性排列顺序为：
A[0][0], A[1][0], A[2][0], // 第0列
A[0][1], A[1][1], A[2][1], // 第1列
A[0][2], A[1][2], A[2][2], // 第2列
A[0][3], A[1][3], A[2][3] // 第3列
也就是内存中的顺序为：
1, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8, 12
内存结构图示（直观图解）
逻辑矩阵：
+---------+---------+---------+---------+
| 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] | A[2][1] | A[2][2] | A[2][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] ]
[ A[0][3] ][ A[1][3] ][ A[2][3] ]
地址计算公式（列主映射）
对于一个二维数组：
int A[M][N]; // M 行 N 列
若采用列主映射，访问 A[i][j] 的内存地址为：
地址(A[i][j]) = Base + (j × 行数 + i) × sizeof(元素类型)
注意与行主映射的差别：
-
行主是
(i × 列数 + j) -
列主是
(j × 行数 + i)
示例推导：
访问 A[2][1]（第3行第2列）：
-
假设 A[0][0] 的起始地址是
0x1000 -
每个
int占 4 字节 -
行数
M = 3
那么偏移量为：
(j × M + i) × 4 = (1 × 3 + 2) × 4 = 5 × 4 = 20
地址为：
0x1000 + 20 = 0x1014
三维数组的性映射公式
int A[L][M][N];
表示一个三维数组，有：
-
L层（depth） -
M行（row） -
N列（column）
这个数组逻辑上可以理解成一个立方体结构：
A[i][j][k] // 第 i 层，第 j 行，第 k 列的元素│ │ └─ 第 k 列
│ └──── 第 j 行
└──────── 第 i 层（或“面”）我们的问题是：在一维内存中，A[i][j][k] 在第几个位置？
行主映射推导
Step 1：理解行主到底是什么意思
行主映射（Row-Major Mapping）：
优先存储最里面的一维（列） → 然后是行 → 最后是层。
也就是说，数组在内存中按以下顺序排布：
A[0][0][0], A[0][0][1], A[0][0][2], ..., A[0][0][N-1],
A[0][1][0], A[0][1][1], ..., A[0][M-1][N-1],
A[1][0][0], ..., A[L-1][M-1][N-1]
Step 2：我们先思考二维数组 A[i][j]
对于二维数组 A[M][N]：
-
每行有 N 个元素
-
第 i 行第 j 列 → 前面有 i×N + j 个元素
Step 3：现在是三维了，A[i][j][k]
❓ 问题：哪些维度在我“前面”？
我们要计算的是 偏移量：
-
有
i个完整的“层”（每层包含 M×N 个元素） -
每个“层”内，有
j个完整的“行”（每行有 N 个元素） -
然后还有本行内的第
k个元素
✅ 所以，偏移 =
偏移元素个数 = (i × M × N) + (j × N) + k地址(A[i][j][k]) = Base + ((i × M × N) + (j × N) + k) × sizeof(type)列主映射推导
Step 1：理解列主的顺序
列主映射（Column-Major Mapping）：
-
第一维（
i，层）变化最快 -
第二维（
j，行）其次 -
第三维（
k，列）变化最慢
也就是说，数组在内存中排成：
A[0][0][0], A[1][0][0], A[2][0][0], ..., A[L-1][0][0],
A[0][1][0], A[1][1][0], ..., A[L-1][M-1][0],
A[0][0][1], ..., A[L-1][M-1][N-1]
Step 2：问自己：A[i][j][k] 前面有几个元素？
-
有
k个完整的“列块”排在前面，每个“列块”有 L×M 个元素 -
有
j个完整的“行块”排在当前列前面，每个“行块”有 L 个元素 -
当前是第
i层的第一个元素
所以，偏移量为：
偏移量 = 列偏移 + 行偏移 + 层偏移(k × L × M) + (j × L) + i地址(A[i][j][k]) = Base + ((k × L × M) + (j × L) + i) × sizeof(type)
-
k是最慢变的 → 它乘最大跨距L×M -
j是中间变的 → 乘L -
i是最快变的 → 直接加
Column-Major 映射顺序（i 变化最快 → k 最慢）↑ k (列)|||o────→ j (行)//i (层) 是内存中变化最快的维度
📌 本质总结
多维数组在线性内存中的表示，实质是：“你在某个维度的偏移 × 该维度之后所有维度的乘积”
