Sherfiter's wiki for fun

第 5 章 · 指针与多维数组

二维数组是「数组的数组」,这句话人人会说,但真正的分水岭在两个长得几乎一样的声明:int *p[3] 和 int (*p)[3],一个是「装指针的数组」,一个是「指向数组的指针」,差一对括号,天壤之别。本章顺着这条线把多维数组讲穿:内存里它到底是不是「二维的」(剧透:是一维的)、行指针怎么用、动态分配的两种流派各是什么脾气。原文小节编号错成 4.x,一并修正。

5.1 内存布局:二维是幻觉,一维是真相

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

内存里没有行列,只有连续 6 个 int,按行优先(一行存完再下一行)摆开:

地址:  +0    +4    +8    +12   +16   +20
内容:  [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ]
        └── 第 0 行 ──┘   └── 第 1 行 ──┘

「二维」只是访问公式制造的错觉:a[i][j] 的地址 = 首地址 + (i×3 + j)×4,编译器把 i、j 折算成一维偏移。第 2 章计算机组成课讲过的「按行遍历快、按列遍历慢」的物理原因就在这:按行走,地址连续吃满缓存行;按列跳,每步跨一整行,一缓存行只用 4 字节。第 12 章(内存视角)还会回来算这笔账。

5.2 行指针:二维数组退化成的类型

关键事实:二维数组名退化时,不是退化成 int*,而是退化成行指针 int (*)[3](指向「一行」):

int a[2][3];
int (*p)[3] = a;      // p 指向第 0 行(整个 int[3])

p + 1;                // 前进一整行,12 字节
(*p)[1];              // 第 0 行第 1 列 = a[0][1]
p[1][2];              // 第 1 行第 2 列 = a[1][2]

一般化公式 a[i][j] ≡ *(*(a + i) + j):先加 i 定位到行(步长一行),解引用得到该行(行退化成 int*),再加 j 定位到元素。这条公式是理解「为什么传二维数组必须写列数」的钥匙:函数不知道一行多宽,就算不出 i 行的偏移。

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

5.3 一对括号的鸿沟

把易混的两兄弟并排放:

int *p[3];      // 指针数组:p 是数组,装 3 个 int*,sizeof(p) = 24
int (*q)[3];    // 数组指针:q 是指针,指向 int[3],sizeof(q) = 8

读法规则(第 13 章系统讲):从内向外,先看括号里 (*q) 决定 q 是指针,再看右边 [3] 决定指向什么。指针数组的经典用途是存长短不一的字符串(第 6 章的 char *names[]),各元素指向各自 malloc 的地盘,互不牵连;数组指针的用途是指向连续的二维块,即 5.1 那种一体的内存。

5.4 动态二维:两种流派

运行时才知道行列数时,有两条路线,布局完全不同:

流派一:一块连续。malloc 一整块,用数组指针按行切:

int rows = 2, cols = 3;
int (*m)[cols] = malloc(rows * sizeof(*m));   // VLA 指针类型,C99+
m[1][2] = 42;                                 // 用法和静态二维完全一样
free(m);                                      // 一次 free

连续内存,缓存友好,memcpy 整块搬运,一次释放。代价:必须凑齐连续空间,超大矩阵可能要不动。

流派二:指针数组 + 散装行(Java、Python 的 int[][] 就长这样):

int **m = malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++)
    m[i] = malloc(cols * sizeof(int));
m[1][2] = 42;
for (int i = 0; i < rows; i++) free(m[i]);    // 先逐行,再行指针
free(m);

每行独立分配,可以锯齿(各行长度不同),单行可以单独 realloc/free;代价是每行一次 malloc、每次访问两次解引用(m[i] 先跳到行指针,再跳到数据),缓存和分配器都不友好。第 12 章的指针税理论在这里直接兑现:实测同样矩阵乘法,流派一常比流派二快一个数量级。数值计算用流派一,需要锯齿/独立行时才用流派二,这句话能省掉很多「为什么我的矩阵运算这么慢」的深夜。

常见错误

  • 把 int **m 传给 int (*)[3] 参数(或反过来)。类型不兼容,数值碰巧相同也不行;二维数组和「指针的指针」是两种内存布局,不是一回事。
  • 流派二忘释放行指针数组。逐行 free 完,最后那个 free(m) 漏了,泄漏整块行指针;释放顺序写反(先 free(m) 再用 m[i])更是直接 use-after-free。
  • p[1][2] 与 (*p)[2] 混用。前者是「第 1 行第 2 列」,后者是「p 指向的那行(第 0 行)的第 2 列」,差一行,查 bug 时盯着括号看。

练习

  1. 动手:验证 5.1 的连续性:打印 &a[0][0] 到 &a[1][2] 的字节差,应是 20;再把 int a[2][3] 强转 int* 用一维下标访问 a[4],验证等于 a[1][1]。
  2. 手算:int a[3][4],求 *(*(a + 2) + 3) 对应的下标、(a + 2) 的类型和步长(字节数)。
  3. 动手:用两种流派各写一个 1000×1000 矩阵乘法,计时对比(开 -O2),记录差距;把流派二改成「每次 malloc 大块、行指针指进去」的混合方案,看能否追平流派一。
  4. 思考:Java 的 int[][] 是流派二,且每行可以是锯齿。这个设计换了什么、丢了什么?如果让你在 Java 里模拟流派一,你会怎么写(提示:一维数组 + 手动下标换算)?
豫ICP备2026027944号