计算器的 switch 里,四个 case 都是同一套动作:

printf("输入操作数:");
scanf("%d %d", &x, &y);
ret = add(x, y);
printf("ret = %d\n", ret);

读入、调用、打印各写四遍,只有函数名在变。输入输出是框架,具体运算才是策略。把框架抽出来,“该调用哪个运算”就只能作为参数传进去。

函数地址传进去,由框架决定何时调用

#include <stdio.h>
 
int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int mul(int a, int b) { return a * b; }
 
void calc(int (*pf)(int, int))
{
    int x;
    int y;
 
    printf("输入操作数:");
    if (scanf("%d %d", &x, &y) != 2)
    {
        printf("输入格式错误\n");
        return;
    }
    printf("ret = %d\n", pf(x, y));    /* 回调发生在这里 */
}
 
int main(void)
{
    int input = 1;
 
    while (input != 0)
    {
        printf("1:add 2:sub 3:mul 0:exit\n请选择:");
        if (scanf("%d", &input) != 1)
        {
            break;
        }
 
        switch (input)
        {
        case 1: calc(add); break;
        case 2: calc(sub); break;
        case 3: calc(mul); break;
        case 0: printf("退出\n"); break;
        default: printf("选择错误\n"); break;
        }
    }
    return 0;
}

calc 不知道 pf 指向谁,它只负责读两个数、调用、打印。add 是回调函数(callback),calc 是框架;calc(add) 把“做什么”交出去,“什么时候做”由框架决定。控制权在这里翻了一次:原来是 main 直接调用 add,现在是把 add 交给 calc,由 calc 在合适的时机调用。

回调函数的定义可以按这条链复述:把函数的指针作为参数传给另一个函数,当那个指针被用来调用它指向的函数时,被调用的函数就是回调函数。它不由实现方直接调用,而是在特定事件或条件发生时由另一方调用。排序里的比较函数每比较一对就回调一次,属于同步回调,必须很快返回;按钮点击、网络库的“数据到达”、信号处理,则是先注册、等事件发生再调用,生命周期长于注册动作。

switch 在这里只负责“从编号找到函数”,那是转移表的事。回调解决“行为可替换”,转移表解决“按编号索引”,两个问题分开看。

qsort 只认返回值的符号

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

四个参数依次是:待排数组的首地址、元素个数、每个元素的字节数、比较函数的地址。base 是 void * 而不是 const void *,因为排序要交换元素,必须能写;比较函数收到的是 const void *,因为它只读。nmemb 和 size 用 size_t,元素个数和字节数都不该是负的。

比较函数的约定只有一条:第一个参数小于第二个时返回负值,大于时返回正值,相等时返回 0。库只检查符号,不关心具体是 -1 还是 -100。

#include <stdio.h>
#include <stdlib.h>
 
int CmpInt(const void *p1, const void *p2)
{
    int a = *(const int *)p1;
    int b = *(const int *)p2;
 
    return (a > b) - (a < b);      /* 只会得到 -1、0、1 */
}
 
int main(void)
{
    int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    size_t n = sizeof(arr) / sizeof(arr[0]);
    size_t i;
 
    qsort(arr, n, sizeof(arr[0]), CmpInt);
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

直接写 *(int *)p1 - *(int *)p2 也能排序,但两个 int 的差可能超出 int 范围,有符号溢出在 C 里是未定义行为。写成 (a > b) - (a < b),两个关系表达式的结果是 0 或 1,相减不会溢出,对任何支持大小比较的类型都成立。

另一个常见错误是写成 return a < b;。这个表达式只有 0 和 1,永远不会返回负数,qsort 收到的信号永远是“a 不该排在 b 后面”,排出来就是倒序。比较函数必须能表达三种关系,不是两种。

结构体数组按字段排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct Stu
{
    char name[20];
    int age;
};
 
int CmpByAge(const void *e1, const void *e2)
{
    const struct Stu *s1 = (const struct Stu *)e1;
    const struct Stu *s2 = (const struct Stu *)e2;
 
    return (s1->age > s2->age) - (s1->age < s2->age);
}
 
int CmpByName(const void *e1, const void *e2)
{
    const struct Stu *s1 = (const struct Stu *)e1;
    const struct Stu *s2 = (const struct Stu *)e2;
 
    return strcmp(s1->name, s2->name);
}
 
int main(void)
{
    struct Stu s[] = {{"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15}};
    size_t n = sizeof(s) / sizeof(s[0]);
    size_t i;
 
    qsort(s, n, sizeof(s[0]), CmpByAge);
    for (i = 0; i < n; i++)
    {
        printf("%s:%d ", s[i].name, s[i].age);
    }
    printf("\n");
 
    qsort(s, n, sizeof(s[0]), CmpByName);
    for (i = 0; i < n; i++)
    {
        printf("%s ", s[i].name);
    }
    printf("\n");
    return 0;
}

qsort 传给比较函数的是“某个元素的地址”,元素类型是 struct Stu,所以先转成 struct Stu * 再取字段。按名字排时交给 strcmp,它按字典序返回负数、0 或正数,正好符合比较函数的约定。

课件这段代码调用了 strcmp,却没有包含 <string.h>。在 C99 之后,调用未声明的函数不再是“默认返回 int”,GCC 会报 implicit declaration 的警告,新版本直接当错误处理。

如果主关键字相等还想有确定顺序,就在比较函数里补第二关键字:

int CmpByAgeThenName(const void *e1, const void *e2)
{
    const struct Stu *s1 = (const struct Stu *)e1;
    const struct Stu *s2 = (const struct Stu *)e2;
 
    if (s1->age != s2->age)
    {
        return (s1->age > s2->age) - (s1->age < s2->age);
    }
    return strcmp(s1->name, s2->name);
}

qsort 不保证稳定:比较函数认为相等的两个元素,在结果里的顺序未指定。标准也不要求它必须用快速排序,名字里的 quick 只是历史遗留。要可复现的顺序,就给元素一个全序,把“相等”变成“可区分”。

用 void * 和回调写一个通用冒泡

通用排序有三个不知道:元素类型、比较规则、交换方式。前两个用 void * 和函数指针解决,第三个靠“把对象当字节看”。

#include <stddef.h>
 
static void SwapBytes(void *p1, void *p2, size_t size)
{
    size_t i;
 
    for (i = 0; i < size; i++)
    {
        char tmp = *((char *)p1 + i);
        *((char *)p1 + i) = *((char *)p2 + i);
        *((char *)p2 + i) = tmp;
    }
}
 
void MyQsort(void *base, size_t n, size_t size,
             int (*cmp)(const void *, const void *))
{
    size_t i;
    size_t j;
    char *p = (char *)base;
 
    if (base == NULL || cmp == NULL || size == 0 || n < 2)
    {
        return;
    }
 
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < n - i - 1; j++)
        {
            void *a = p + j * size;
            void *b = p + (j + 1) * size;
 
            if (cmp(a, b) > 0)
            {
                SwapBytes(a, b, size);
            }
        }
    }
}

void * 不能解引用,也不能直接做算术,所以先转成 char *。p + j * size 是全部地址计算的来源:元素按 size 字节等距排列,第 j 个元素的地址就是“基地址 + j 个元素宽度”。这也是 qsort 必须知道 size 的原因,没有它连第二个元素在哪都算不出来。

逐字节交换是标准允许的:可以通过 char * 或 unsigned char * 访问任意对象的字节表示。交换前后对象的位置不变,对齐也不变,不会破坏类型;代价是元素大时效率低,可以预分配一块临时缓冲,用三次 memcpy 搬。

两个边界要提前判掉。size == 0 时 p + j * 0 永远等于 p,比较的永远是同一个元素;n < 2 时外层上界 n - 1 在 size_t 下会绕成一个巨大的数。这两条不是防御性过度设计,是真的会跑飞。

课件的模拟实现有两处类型问题。bubble 的比较函数参数写成 int (*)(void *, void *),而 int_cmp 是 int (*)(const void *, const void *),两个函数指针类型不兼容,GCC 会报 incompatible pointer type;比较函数只读数据,参数应当带 const。count 和 size 写成了 int,标准库用的是 size_t,元素很大或数组极长时 int 会溢出,接口也没法和 qsort 互换。

qsort 的比较函数只有两个参数,没有上下文,“按哪个字段排、升序还是降序”没法通过参数传进去,只能写死在函数里或者借全局变量。GNU 的 qsort_r 和 C11 附录 K 的 qsort_s 多给了一个 void *context,补的就是这个口子;自己写排序时在接口里留一个 ctx,会干净得多。