数据结构:多维数组在内存中的映射(Address Mapping of Multi-dimensional Arrays)

发布于:2025-07-10 ⋅ 阅读:(24) ⋅ 点赞:(0)

目录

行主映射(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)
符号 含义
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 (层) 是内存中变化最快的维度

 📌 本质总结

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

 


网站公告

今日签到

点亮在社区的每一天
去签到