目录
在内存中,数据只能线性存储(一维地址线),但二维数组是逻辑上的“表格”结构。
所以,编译器必须把二维数组的元素映射到内存中的线性地址。
行主映射(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 4
1 | 5 6 7 8
2 | 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 (层) 是内存中变化最快的维度
📌 本质总结
多维数组在线性内存中的表示,实质是:“你在某个维度的偏移 × 该维度之后所有维度的乘积”