数据结构：多维数组在内存中的映射（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   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)

🔍 示例推导：

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

为什么使用行主映射？

✅ 优点：

在 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 (层) 是内存中变化最快的维度

 📌 本质总结

多维数组在线性内存中的表示，实质是：“你在某个维度的偏移 × 该维度之后所有维度的乘积”