Lecture 12: 用指针与数组解决问题；函数指针与回调 (Problem Solving with Pointers and Arrays; Function Pointers and Callbacks)
Lecture 12: 用指针与数组解决问题；函数指针与回调 (Problem Solving with Pointers and Arrays; Function Pointers and Callbacks)
概述
本讲把指针与数组从”机制”变成”工具”：就地 (in-place) 算法如何在不额外分配内存的前提下完成反转、分区、去重、旋转与查找， 以及数据长度事先未知时如何用”指针的指针”与 realloc 让被调用者改掉调用者的指针。 在此之上引入函数指针 (function pointer)：函数的入口地址也是一个值，可以赋给变量、放进数组当跳转表 (jump table)、 作为参数传给别的函数（回调，callback），于是同一个排序框架能对”任意类型”工作——这正是标准库 qsort 的设计。
核心概念与底层机制图解
- 就地算法 (In-place Algorithm)：所有工作都在调用者提供的存储里完成，额外空间 O(1)。
- 直观解释：在原书架上重排书，而不是先搬到另一间屋子再搬回来。
- 底层机制图解：额外空间只体现为寄存器与一两个栈上的临时变量：
reverse (int32_t* d, int32_t n) 的机器模型 R1 = d（左指针） R2 = d + (n-1)*4（右指针） 循环: 交换 M[R1] 与 M[R2]，R1 += 4，R2 -= 4，直到 R1 >= R2对比”另分配一个数组再拷回”：额外空间 O(n)，还要
malloc/free与失败处理。 - 作用域与存储期：只读写调用者的数组，不引入新的存储期；幻灯片强调
malloc只有”没有内存”一个失败原因，能省就省。
- 双指针技术 (Two-Pointer Technique)：两个指针从两端（或同向）扫描，把 O(n²) 的朴素解法降到 O(n)。
- 直观解释：两个人从书架两头向中间整理，比一个人反复从头找到尾快得多。
- 底层机制图解：三种典型形态——
- 分区 (partition)：
left停在第一个 ≥ pivot 的元素、right停在第一个 < pivot 的元素，交换后各进一步； 循环条件必须是left <= right，否则落在同一元素上的那个值从未被归类。 - 有序配对 (pair sum)：
sum < target就left++（左边需要更大），sum > target就right--；依赖数组有序。 - 去重 (remove duplicates)：读指针扫全数组，写指针仅在”值变化”时前进；写指针永不越过读指针：
已排序 {1,1,1,2,3,3,5,5,5,8}，w（写）与 r（读）同起点 r: 1 1 1 2 3 3 5 5 5 8 值与前一个不同 → *w = *r; w++ w: 1 2 3 5 8 w 前进 5 次 → 逻辑长度 5，数组本身没有变小
- 分区 (partition)：
- 作用域与存储期：两个指针只是 automatic 变量；数据仍是调用者的数组，结果留在原地，所以函数必须用返回值报告”新长度/边界”。
- 旋转与三反转技巧 (rotation; the three-reversal trick)：设
a = [A\|B]，三步得到[B\|A]。- 直观解释：一摞牌分上下两半互换位置，做法是”各自翻面、再整体翻面”。
- 底层机制图解：
原始: A = 1 2 3 B = 4 5 6 7 8 反转 A: 3 2 1 \| 4 5 6 7 8 反转 B: 3 2 1 \| 8 7 6 5 4 全体反转: 4 5 6 7 8 1 2 3 ← 示例 2 的实测输出（每个元素恰好移动一次）先做
k = k % n（k=11、n=8等价于k=3），k <= 0直接返回。 实测片段（/tmp/ece220_algo/41b_rotate_bsearch.c，已编译运行，输出rotate_left (a, 8, 3): 4 5 6 7 8 1 2 3）：static void rotate_left (int32_t* d, int32_t n, int32_t k) { k = (n > 0) ? k % n : 0; if (k <= 0) { return; } reverse (d, k); /* reverse the first block */ reverse (d + k, n - k); /* reverse the second block */ reverse (d, n); /* reverse everything */ } - 作用域与存储期：只有整数
k是 automatic；数组没有新增存储，也没有新的生命期。
- 查找：线性 vs 二分 (linear vs binary search)。
- 直观解释：查纸质电话簿不会从第一页翻起（线性），而是翻开中间判断目标在前还是在后（二分）。
- 底层机制图解：二分每轮把区间至少减半，比较次数 O(log n)；但小数组上它未必赢，因为它每轮做两次比较 （判等 + 定方向）。实测（
/tmp/ece220_algo/31c_rotate_search.c，数组{1,3,5,7,9,11,13,15}）：target linear(idx/cmp) binary(idx/cmp) 1 0 / 1 0 / 5 15 7 / 8 7 / 7 8 -1 / 8 -1 / 6正确性论证：(1) 不变量——若
v存在，其下标始终在[low, high]内；v < d[mid]时由有序性排除mid及其右侧，[low, mid-1]仍满足不变量，反向同理。(2) 终止——区间每轮至少减半，low > high时为空， 由不变量知v不存在。(3) 溢出陷阱——mid = (low + high) / 2会溢出成负数，必须写low + (high - low) / 2； 幻灯片指出标准库曾用错这个表达式二十多年。 实测的二分核心（同一文件；对 8 个元素的目标 1、15、8 分别返回下标 0、7、−1， 比较次数 5、7、6）：static int32_t binary_search (int32_t const* d, int32_t n, int32_t v, long* cmps) { int32_t low = 0; int32_t high = n - 1; int32_t mid; *cmps = 0; while (high >= low) { mid = low + (high - low) / 2; /* NOT (low + high) / 2 */ (*cmps)++; if (v == d[mid]) { return mid; } (*cmps)++; if (v < d[mid]) { high = mid - 1; } else { low = mid + 1; } } return -1; } - 作用域与存储期：
low/high/mid都是 automatic；数组只读，参数用int32_t const*。
- 指针的指针：
alloc (int32_t**)与realloc惯用法。- 直观解释：要让别人替你换掉写着门牌号的纸条，你得先把”放纸条的抽屉”告诉他。
- 底层机制图解：
T*的副本改不了调用者的指针，T**才能；实测片段 （/tmp/ece220_algo/32c_alloc.c已编译运行：a = 0x14fd2a0是堆地址，&a = 0x7ffcd2c88500是栈地址）：static int32_t alloc_ints (int32_t** out, int32_t n) { int32_t* fresh = malloc ((size_t) n * sizeof (int32_t)); if (NULL == fresh) { *out = NULL; /* never leave a stale value */ return 0; } *out = fresh; /* writes the CALLER's pointer */ return 1; }realloc同理，但必须用临时指针接住返回值（失败时它返回 NULL 且不释放旧块）：p = realloc (p, n);会丢失旧地址造成泄漏，正确写法是temp = realloc (p, n); if (NULL != temp) { p = temp; }。 - 作用域与存储期：
*out是 allocated 存储期，由free结束；free后把指针置 NULL，可让悬垂误用立刻暴露。
- 函数指针 (Function Pointer)：函数入口地址是一个值，类型 = 返回值类型 + 参数列表。
- 直观解释：函数名像门牌号，函数指针是”把门牌号抄进变量”；通讯录里存号码，不存谈话内容。
- 底层机制图解：幻灯片最关键的对比——
int (*f)(int)与int *f(int)完全不是一回事：int32_t (*f) (int32_t); /* f 是指针：指向"int32_t → int32_t"的函数 */ int32_t* g (int32_t); /* g 是函数：接收 int32_t，返回 int32_t* */括号
(*f)是分水岭：没有它，*会与返回类型结合，变成”返回指针的函数”。 两条等价关系（示例 2 实测）：fp = □与fp = square;同值；(*fp) (7)与fp (7)都是 49。 - 作用域与存储期：函数具有 static 存储期（代码段，程序全程存在），函数指针永不悬垂；指针变量自身是 automatic，占 8 字节。
- 函数指针数组 = 跳转表 (Jump Table)：一组同签名函数地址放进数组，用下标选择行为。
- 直观解释：电视遥控器：按不同的键（下标）触发不同功能（函数）。
- 底层机制图解：这就是 LC-3”
JSRR+ 跳转表”的 C 版本：static int32_t (*table[2]) (int32_t) = {&square, &negate}; +----------------------+ 调用 table[opcode] (x)： \| &square （代码地址） \| LDR 取出地址 → 间接跳转 = 一次访存 + 一次间接调用 +----------------------+ \| &negate （代码地址） \| C 不检查下标：table[2] 会读到别的数据再跳过去（UB） +----------------------+ - 作用域与存储期：带
static的表是 static 存储期，程序启动即存在；函数内不加static则表在栈上，每次调用都要重新初始化。
- 回调 (Callback) 与泛型排序 (Generic Sort)：把函数指针作为参数交给”框架函数”，框架在合适时机回头调用它。
- 直观解释：算法是”流程”，回调是”规则”；框架只管搬元素，谁大谁小由回调决定。
- 底层机制图解：
qsort的签名是标准形态：void qsort (void* base, size_t nmemb, size_t size, int (*compar) (const void*, const void*));框架要能移动任意大小的元素，所以
base是void*而内部转成char*做字节算术：a + j * size /* 第 j 个元素的地址：只有 char* 能按字节算 */ (*compar) (a + j * size, a + best * size) /* 问回调：谁在前？ */ swap_bytes (..., size) /* 逐字节交换，不知道类型也能搬 */回调的语义必须写进文档（幻灯片特别强调）：返回负数表示第一个参数”更小/在前”。
- 作用域与存储期：框架不分配内存（字节交换就地完成），没有失败路径；回调位于 static 代码段，调用它不影响框架的栈帧布局。
代码示例与底层机制分析
示例 1：双指针就地算法（反转、去重、有序配对）
代码 (C)（/tmp/ece220_algo/40_two_pointer.c，用 gcc -g -std=c99 -Wall -Werror 40_two_pointer.c -o 40_two_pointer 实测）：
#include <stdint.h>
#include <stdio.h>
/* Reverse n elements; return the number of swaps (n / 2). */
static int32_t
reverse (int32_t* d, int32_t n)
{
int32_t* left = d;
int32_t* right = d + n - 1;
int32_t swaps = 0;
while (left < right) {
int32_t t = *left;
*left++ = *right; /* read right, write left, then advance */
*right-- = t;
swaps++;
}
return swaps;
}
/* Keep one copy of each value of a SORTED array; return the new length. */
static int32_t
dedupe (int32_t* d, int32_t n)
{
int32_t* write = d;
int32_t* read = d;
int32_t* end = d + n;
while (read != end) {
if ((write == d) || (*read != *(write - 1))) {
*write++ = *read;
}
read++;
}
return (int32_t) (write - d); /* the write pointer IS the length */
}
/* In a SORTED array, find two elements summing to target. */
static int32_t
find_pair (int32_t const* d, int32_t n, int32_t target, int32_t* out)
{
int32_t const* left = d;
int32_t const* right = d + n - 1;
while (left < right) {
int32_t sum = *left + *right;
if (sum == target) {
out[0] = *left;
out[1] = *right;
return 1;
}
if (sum < target) {
left++; /* the left value must grow */
} else {
right--; /* the right value must shrink */
}
}
return 0;
}
int
main (void)
{
int32_t a[5] = {1, 2, 3, 4, 5};
int32_t dup[10] = {1, 1, 1, 2, 3, 3, 5, 5, 5, 8};
int32_t sorted[8] = {1, 3, 4, 7, 9, 11, 15, 20};
int32_t pair[2];
int32_t i;
int32_t n;
printf ("swaps performed = %d\n", reverse (a, 5));
printf ("after reverse:");
for (i = 0; i < 5; i++) {
printf (" %d", a[i]);
}
n = dedupe (dup, 10);
printf ("\nafter dedupe (length %d):", n);
for (i = 0; i < n; i++) {
printf (" %d", dup[i]);
}
if (find_pair (sorted, 8, 16, pair)) {
printf ("\npair summing to 16: %d + %d\n", pair[0], pair[1]);
}
if (0 == find_pair (sorted, 8, 5, pair)) {
printf ("no pair sums to 5\n");
}
return 0;
}
实际输出：
swaps performed = 2
after reverse: 5 4 3 2 1
after dedupe (length 5): 1 2 3 5 8
pair summing to 16: 1 + 15
【代码做什么？】
reverse (a, 5)交换 2 次（5/2），数组变成5 4 3 2 1；中间那个元素不用动。dedupe (dup, 10)在已排序的 10 个元素里留下 5 个不同值并返回 5：数组没有变小，只是逻辑长度变成 5。find_pair (sorted, 8, 16, pair)从两端出发扫描一次，找到1 + 15并写入调用者的pair[0..1]。find_pair (sorted, 8, 5, pair)返回 0（不存在这样的两项），于是打印 “no pair sums to 5”。- 全程没有一次
malloc：函数只写调用者的数组，用返回值报告”发生了什么”。
【底层机制透视】 *left++ = *right; 的语义是”取 *right 作为右值、写入 *left、然后左指针自增”， 一条 C 语句编译成”取数—存数—指针加 4”。dedupe 里 write == d 的特判避免读 *(write-1) 越界—— 用不变量守住边界比事后检查更可靠。find_pair 传入 int32_t* out 而不是返回结构体， 是为了让函数”返回两个值”（第二讲/第九讲讲过的指针参数的典型用途）。 write - d 得到的是元素个数（指针相减按元素大小缩放），它直接就是新的长度。
【内存布局图解】
dup 数组（栈上 10 个 int32_t）与两个指针（去重过程中）
下标: 0 1 2 3 4 5 6 7 8 9
+----+----+----+----+----+----+----+----+----+----+
| 1 | 1 | 1 | 2 | 3 | 3 | 5 | 5 | 5 | 8 |
+----+----+----+----+----+----+----+----+----+----+
^w ^r
└───┘ r 前进；当 *r 与前一个写入值不同时 *w = *r 且 w++
结束时：w 停在 d+5（元素单位），于是 return 5
+----+----+----+----+----+----+----+----+----+----+
| 1 | 2 | 3 | 5 | 8 | 3 | 5 | 5 | 5 | 8 | ← 下标 5..9 是"垃圾但仍在数组内"
+----+----+----+----+----+----+----+----+----+----+
└─── 逻辑上有效的 5 个元素 ───┘
【与汇编的对应】（LC-3：双指针就是两个寄存器 + 一次比较）
; reverse (d, n)：R0 = d，R1 = n。约定 R2 = 左指针，R3 = 右指针，R4 = 临时量
ADD R2,R0,#0 ; R2 = d （左指针）
ADD R3,R1,#-1
ADD R3,R0,R3 ; R3 = d + n - 1（右指针）
REVLOOP
NOT R5,R3 ; 比较 R2 与 R3；R2 >= R3 就结束
ADD R5,R5,#1
ADD R5,R2,R5 ; R5 = R2 - R3
BRzp REVDONE
LDR R4,R2,#0 ; R4 = *left
LDR R5,R3,#0 ; R5 = *right
STR R5,R2,#0 ; *left = 旧 *right
STR R4,R3,#0 ; *right = 旧 *left
ADD R2,R2,#1 ; left++（LC-3 上一个 int 槽 = 一个字）
ADD R3,R3,#-1 ; right--
BRnzp REVLOOP
REVDONE RET
; 提示：这里把 R5 当临时寄存器用。若子程序还要调用别的子程序，
; 必须先按调用约定保存 R5（帧指针），否则返回后整个栈帧的定位都会错。
示例 2：函数指针、跳转表、回调与泛型排序
代码 (C)（/tmp/ece220_algo/42b_fptrs.c）：
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char name[16];
int32_t score;
} player_t;
static int32_t square (int32_t x) { return x * x; }
static int32_t negate (int32_t x) { return -x; }
/* A function that RETURNS a pointer: note where the '*' sits. */
static int32_t*
identity (int32_t* p)
{
return p;
}
/* An operation chosen at run time by an opcode: a jump table. */
static int32_t
apply_op (int32_t opcode, int32_t x)
{
static int32_t (*table[2]) (int32_t) = {&square, &negate};
if (0 > opcode || 1 < opcode) {
return 0; /* the bound check is OURS to do */
}
return (*table[opcode]) (x); /* like LC-3 JSRR through a table */
}
/* Exchange two elements of size bytes without knowing their type. */
static void
swap_bytes (char* x, char* y, size_t size)
{
size_t k;
for (k = 0; k < size; k++) {
char t = x[k];
x[k] = y[k];
y[k] = t;
}
}
/* mysort -- a generic sort with the same parameters and meaning as qsort:
* base is the array address, nmemb the element count, size the bytes per
* element, compar a callback returning <0, 0, or >0 for (first, second). */
static void
mysort (void* base, size_t nmemb, size_t size,
int (*compar) (const void*, const void*))
{
char* a = base; /* byte arithmetic needs char* */
size_t i;
size_t j;
for (i = 0; i + 1 < nmemb; i++) {
size_t best = i; /* index of the smallest remaining */
for (j = i + 1; j < nmemb; j++) {
if (0 > (*compar) (a + j * size, a + best * size)) {
best = j;
}
}
if (best != i) {
swap_bytes (a + i * size, a + best * size, size);
}
}
}
static int
cmp_score_desc (const void* a, const void* b)
{
player_t const* p1 = a; /* restore the real type */
player_t const* p2 = b;
if (p1->score != p2->score) {
return (p1->score > p2->score) ? -1 : 1;
}
return strcmp (p1->name, p2->name);
}
static void
show (char const* label, player_t const* p, size_t n)
{
size_t i;
printf ("%s:", label);
for (i = 0; i < n; i++) {
printf (" %s/%d", p[i].name, p[i].score);
}
printf ("\n");
}
int
main (void)
{
int32_t value = 21;
int32_t (*fp) (int32_t) = □
int32_t (*named) (int32_t) = square; /* the same address */
int32_t* ip = identity (&value);
player_t players[3] = {{"Ada", 91}, {"Grace", 88}, {"Linus", 91}};
player_t copy[3];
printf ("(&square == square) -> %d, (*fp) (7) = %d, fp (7) = %d\n",
fp == named, (*fp) (7), fp (7));
printf ("sizeof (fp) = %d, sizeof (ip) = %d, sizeof (identity (&value))"
" = %d (return type is int32_t*)\n",
(int) sizeof fp, (int) sizeof ip, (int) sizeof identity (&value));
fp = &negate; /* re-point it at run time */
printf ("after fp = &negate: fp (7) = %d, *ip = %d\n", fp (7), *ip);
printf ("apply_op (0, 6) = %d, apply_op (1, 6) = %d, apply_op (2, 6) = %d\n",
apply_op (0, 6), apply_op (1, 6), apply_op (2, 6));
show ("original", players, 3);
mysort (players, 3, sizeof (player_t), &cmp_score_desc);
show ("mysort by score", players, 3);
memcpy (copy, players, sizeof players);
qsort (copy, 3, sizeof (player_t), &cmp_score_desc);
printf ("library qsort agrees with mysort -> %d\n",
0 == memcmp (players, copy, sizeof players));
return 0;
}
实际输出：
(&square == square) -> 1, (*fp) (7) = 49, fp (7) = 49
sizeof (fp) = 8, sizeof (ip) = 8, sizeof (identity (&value)) = 8 (return type is int32_t*)
after fp = &negate: fp (7) = -7, *ip = 21
apply_op (0, 6) = 36, apply_op (1, 6) = -6, apply_op (2, 6) = 0
original: Ada/91 Grace/88 Linus/91
mysort by score: Ada/91 Linus/91 Grace/88
library qsort agrees with mysort -> 1
【代码做什么？】
fp == named为 1：&square与裸函数名square得到同一地址；(*fp) (7)与fp (7)都是 49。sizeof (fp) = 8（函数指针也是 8 字节地址），sizeof (identity (&value)) = 8是调用结果（int32_t*）的大小。fp = &negate后fp (7) = -7：同一个指针变量在运行期换成另一个函数。apply_op (0, 6) = 36、apply_op (1, 6) = -6（跳转表命中），apply_op (2, 6) = 0——越界时返回 0 是我们自己写的边界检查救的场。mysort按分数降序排好 3 个结构体；qsort得到逐字节相同的结果（memcmp为 0）， 证明”用回调实现的泛型接口”与标准库语义一致。
【底层机制透视】 mysort 把 void* base 转成 char* a：只有 char* 能做字节算术， a + j * size 就是第 j 个元素的地址，memcpy/swap_bytes 按字节搬移，框架完全不知道类型。 比较交给回调 compar，它接收元素的地址而不是元素本身（const void*）， 所以 cmp_score_desc 必须做类型还原 player_t const* p1 = a;。 sizeof (player_t) = 20（16 字节名字 + 4 字节分数）——每次交换搬 20 字节，这就是”泛型”的代价： 框架不知道类型，只能逐字节处理。qsort 的 size 参数正是为此存在。
【内存布局图解】
跳转表（static） mysort 中的字节地址算术
table （2 × 8 = 16 字节） a ──→ +----+----+----+ ... +----+
+----------------------+ | 第 0 个元素（20 字节） |
| &square （代码地址） | ← table[0] (6) = 36 +----+----+----+ ... +----+
+----------------------+ | 第 1 个元素 |
| &negate （代码地址） | ← table[1] (6) = -6 +----+----+----+ ... +----+
+----------------------+ | 第 2 个元素 |
table[2] 越界 → 读到别的数据再跳过去（UB） +----+----+----+ ... +----+
a + j * 20 = 第 j 个元素的地址
【与汇编的对应】（LC-3：跳转表 + JSRR）
; apply_op (opcode, x)：R0 = opcode，R1 = x
LEA R2,TABLE ; R2 = 跳转表首地址（标号汇编期已知 → LEA）
ADD R2,R2,R0 ; R2 = &TABLE[opcode]（每项 1 个字）
LDR R3,R2,#0 ; R3 = 函数入口地址 ← 从表里取出"函数指针"
ADD R0,R1,#0 ; R0 = x，作为被调用函数的参数（R0–R3 传参）
JSRR R3 ; 间接跳转：跳到 R3 所指的代码 ← C 的 (*table[opcode]) (x)
RET ; 返回值在 R0 中，直接交还调用者
TABLE .FILL SQUARE ; 表项就是函数的入口地址
.FILL NEGATE
SQUARE ; ... 计算 R0 * R0 ...
RET
NEGATE NOT R0,R0
ADD R0,R0,#1
RET
; 通用排序（回调）在 LC-3 上的做法完全相同：调用者把"比较子程序的地址"
; 作为参数压栈传进去，排序框架用 LDR 取出该地址再用 JSRR 调用 —— 这就是汇编里的回调。
演示（仅供演示、请勿模仿）：悬垂指针与同一块内存被释放两次
free之后的指针仍然保存着旧地址，它指向的存储已经不属于本程序：int32_t* p = malloc (4 * sizeof (int32_t)); for (i = 0; i < 4; i++) { p[i] = i + 1; } free (p); printf ("%d\n", p[0]); /* UB：读已释放的存储 */ free (p); /* UB：二次释放，可能摧毁分配器的簿记结构 */实测（gcc 12.2.0，x86-64 Linux，加
-Wall但不加-Werror）：编译器报warning: pointer 'p' used after 'free' [-Wuse-after-free]；加上-Werror后根本编译不过。 若去掉警告直接运行，读出的往往是分配器留下的簿记数据而不是原来的1； 用valgrind --leak-check=full ./prog会明确报出 invalid read 与 double free。 这是未定义行为，实际结果随编译器、优化级别与平台而异，不要把它当成”总能读到旧值”来推理。
常见错误与调试技巧
realloc的返回值直接写回原指针：p = realloc (p, n)，失败时旧块地址丢失造成泄漏。 调试：valgrind --leak-check=full --track-origins=yes ./prog会报 definitely lost；改用临时指针接住返回值并检查NULL。free之后继续使用指针或重复free：读/写已释放的存储、二次释放。 调试：gcc -Wall报-Wuse-after-free；gcc -fsanitize=address -g或valgrind直接报 invalid read/write 与 double free。- 函数指针声明写错：把
int (*f)(int)写成int* f(int)，或在数组声明里漏括号写成int* table[2](int)（非法）。 调试：gdb的ptype f读出真实类型；打印(int) sizeof f（8 说明是指针）；逐字读编译器的错误信息。 - 跳转表越界：
table[opcode]没检查opcode范围，会跳到随机地址或调用错误函数。 调试：调用前加范围检查（示例 2 就是这么做并实测到apply_op (2, 6) = 0）；gdb中x/2gx &table看表内容、p opcode看下标；用-fsanitize=address捕获越界。 - 二分中点溢出：
mid = (low + high) / 2在大数组上溢出成负下标。 调试：改用low + (high - low) / 2；gdb里watch mid观察是否出现负值；-fsanitize=undefined捕获有符号溢出。 - 把两个”有副作用”的调用塞进同一个
printf参数表：参数求值顺序未定义， 计数器可能在被写入前被读出（本讲早期版本实测打印出0 / 524288）。调试：拆成独立语句分别赋值再打印。
关键要点
- 就地算法用 O(1) 额外空间完成变换：交换是基本功，双指针是主力（分区、有序配对、去重）， 三反转法用 n 次移动完成旋转；共同点是结果留在调用者的数组里，函数用返回值报告新长度或边界。
- 二分的正确性来自不变量（目标若存在则下标在
[low, high]），每次比较丢弃一半区间；中点必须写low + (high - low) / 2，否则加法会溢出成负下标。 - 要改调用者的指针就传”指针的地址”（
void alloc (int32_t** p)）；realloc必须用临时指针接返回值， 失败时它返回 NULL 且不释放旧块，ptr = realloc (ptr, n)是经典的泄漏写法。 - 函数指针让函数成为数据：
int (*f)(int)与int *f(int)的区别全在括号；&func与func等价、(*f)(x)与f(x)等价；函数指针数组就是跳转表（LC-3 里对应LEA+LDR+JSRR），下标边界要自己检查。 - 回调是”把规则交给框架”：
qsort式签名让同一个排序框架服务任意类型，框架按字节搬移元素（size参数因此必需）， 回调负责把void*还原成真实类型；其返回值的语义必须写进文档。
思考题（带答案）
问题 1：partition 的循环条件为什么是 left <= right 而不是 left < right？请举例说明差别。
答案：因为当两个指针落在同一个元素上时，这个元素还没被归类。以 {9, 1, 3}、pivot = 5 为例： left 指向 9（≥ pivot），right 指向 3（< pivot），若用 <，当 left == right（都指向 3）时循环提前退出， 中间的 3 既没被移走也没被计数，返回的 cut 就夸大了”小于 pivot 的元素个数”。 改用 <= 时，两指针在同一元素上仍会执行一次判断与归类，返回的 cut 恰好是”真正小于 pivot 的元素个数”。 一般规则：当循环体可能改变当前元素所属的一侧时，必须让指针在同一元素上走完一次逻辑。
问题 2：下面两个声明分别是什么？sizeof 各是多少？怎样一句话区分？
int32_t (*f) (int32_t);
int32_t* g (int32_t);
答案：f 是函数指针变量（指向”接收 int32_t、返回 int32_t“的函数），sizeof (f) = 8； g 是函数（接收 int32_t、返回 int32_t*），函数名没有”大小”，sizeof (g (3)) = 8 只是调用结果（指针）的大小。 一句话：看括号——(*f) 表明被声明的标识符 f 是指针；g (int32_t) 中标识符后面直接跟参数表，表明 g 是函数。 所以 fp = □ 合法（给指针赋值），而 g = □ 非法（给函数名赋值）。
问题 3：为什么 mysort（以及 qsort）必须接收 size 参数？去掉它会怎样？
答案：泛型排序不知道元素类型，只能用字节地址与字节偏移定位元素： a + j * size 才是第 j 个元素的地址，swap_bytes (..., size) 才知道要搬多少字节。 若没有 size，框架只能假设每个元素 1 字节，那么对 int32_t 数组第二个元素会算成”首地址 + 1”而不是 “+4”， 结果完全错乱；对 20 字节的 player_t 更是灾难。 反过来，size 也解释了回调为什么接收元素的地址而不是元素本身：框架只能说”两个元素在哪里”， 由回调按自己的类型去解释那 20 个字节——这正是 const void* 参数与 player_t const* p1 = a; 这种类型还原存在的原因。