第 5 章 · 指针与多维数组

多维数组 = 数组的数组；核心区分：指针数组 int *p[3] 与数组指针 int (*p)[3] 不是一回事。

4.1 内存布局：二维数组是连续的一块

int a[2][3] = {{1, 2, 3}, {4, 5, 6}};

它在内存里是连续 6 个 int，按行优先（row-major）排列：

a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2]
  1       2       3       4       5       6

a 的类型是 int[2][3]。a 退化时不是退化成 int*，而是退化成 int (*)[3]——指向「含 3 个 int 的一行」的指针。

4.2 行指针：`int (*p)[3]`

int a[2][3];
int (*p)[3] = a;      // p 指向第一行，类型 int (*)[3]

p + 1;                // 前进一行 = 前进 sizeof(int[3]) = 12 字节
(*p)[1];              // 第一行第 1 列 = a[0][1]
p[1][2];              // 第二行第 2 列 = a[1][2]

p 指向「一行」，p + 1 跳一整行（12 字节），*p 得到那一行（退化成 int*）。
一般化公式：a[i][j] ≡ *(*(a + i) + j)。先 a + i 定位第 i 行，* 得到该行首元素指针，再 + j 定位列。

函数接收二维数组，必须知道列数（一行多大），否则无法算出行步长：

void f(int a[][3], int rows) {   // 等价 int (*a)[3]，列数 3 必须写
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < 3; j++)
            printf("%d ", a[i][j]);
}

4.3 指针数组 vs 数组指针

这两个声明长得像，意义完全不同，读法从内向外看括号：

int *p[3];      // 指针数组：p 是「含 3 个 int* 的数组」，先 [3] 再 *
int (*q)[3];    // 数组指针：q 是「指向 int[3] 的指针」，先 * 再 [3]

	指针数组 `int *p[3]`	数组指针 `int (*q)[3]`
是什么	一个数组，元素是指针	一个指针，指向数组
大小	`3 × sizeof(int*)` = 24	`sizeof(int*)` = 8
元素	每个元素可指向不同地方	指向一整块连续内存

指针数组典型用途：存长度不一的字符串（比固定二维数组省内存）：

char *names[] = {"Alice", "Bob", "Charlie"};  // 3 个 char*，各指向不同长度
// 对比固定布局 char names[3][8] 会浪费空间

4.4 动态二维数组的两种做法

静态二维数组 int a[2][3] 是连续内存；动态分配时有两种截然不同的布局：

做法一：真正的连续二维（数组指针）

int (*m)[3] = malloc(2 * sizeof(int[3]));   // 一次性分配 2 行，连续
m[1][2] = 42;
free(m);

做法二：指针数组 + 每行单独分配（交错内存）

int **m = malloc(2 * sizeof(int*));         // 先分配行指针数组
for (int i = 0; i < 2; i++)
    m[i] = malloc(3 * sizeof(int));         // 每行单独分配
m[1][2] = 42;
for (int i = 0; i < 2; i++) free(m[i]);     // 释放顺序：先每行，再行指针
free(m);

两种做法 m[1][2] 都能写，但内存布局不同：做法一是连续一块，做法二每行分散。这影响缓存局部性（做法一更快）、memcpy 是否能用一整块（做法二不能）、释放是否要逐行。

4.5 与汇编 / 其他语言对照

汇编：a[i][j] 编译成 [base + i*rowsize + j*elemsize]——二维访问只是一次地址算术，没有中间指针跳转。这正是「连续二维」比「指针数组」快的原因：少一次内存读取。
Java：int[][] 本质是指针数组（做法二）——外层是 int[] 的数组，每行是独立对象，可以锯齿状（每行长度不同），a[i][j] 要做两次引用跳转。
C++：std::vector<std::vector<T>> 同样是锯齿/交错布局；想要连续二维，用 std::vector 展平成一维或 std::mdspan（C++23）。
Python：list 嵌套是引用数组，与 Java 类似，且每行可异构、可变长。