计算器的 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,会干净得多。
还没有评论 — 第一条由你来留。