目录
- 一、回调函数
- 二、快速排序函数 qsort
- 1. qsort() 函数原型
- 2. 使用 qsort() 函数
- 三、仿照 qsort 函数设计一个可以排序任意类型数组的冒泡函数
- 1. 函数原型
- 2. 函数设计思路
一、回调函数
在 C 语言中，回调函数是一种通过函数指针调用的函数，也就是一个被作为参数传递的函数。在特定的事件或条件发生时，主程序可以调用这个被传递进来的函数来执行特定的操作。
在指针进阶（二）（C 语言）中的最后我们使用函数指针数组模拟了简单的计算器，我们把其中的输入计算部分，封装成了一个函数 calc()，需要传入对应操作的函数地址，然后在 calc() 函数中通过函数指针来调用相应的函数。而这个被调用的函数就被称为回调函数。而在这里使用回调函数的主要作用是减少代码的冗余，如果不使用回调函数，那么 switch 语句部分就会是如下代码：
switch (input)
{
case 1:
printf("输⼊操作数：");
scanf("%d %d", &x, &y);
ret = add(x, y);
printf("ret = %d\n", ret);
break;
case 2:
printf("输⼊操作数：");
scanf("%d %d", &x, &y);
ret = sub(x, y);
printf("ret = %d\n", ret);
break;
case 3:
printf("输⼊操作数：");
scanf("%d %d", &x, &y);
ret = mul(x, y);
printf("ret = %d\n", ret);
break;
case 4:
printf("输⼊操作数：");
scanf("%d %d", &x, &y);
ret = div(x, y);
printf("ret = %d\n", ret);
break;
case 0:
printf("退出程序\n");
break;
default:
printf("选择错误\n");
break;
}
可以看到上述代码的前四个选项中，除了调用的函数不同，其他代码部分都是相同的。所以，前四个选项的功能设计成一个函数，根据不同的功能传递不同的函数指针，使用回调函数来完成相应的功能。这样减少了代码的冗余，提升了代码的可读性。
switch (input)
{
case 1:
calc(add);
break;
case 2:
calc(sub);
break;
case 3:
calc(mul);
break;
case 4:
calc(div);
break;
case 0:
printf("退出程序\n");
break;
default:
printf("选择错误\n");
break;
}
二、快速排序函数 qsort
C 语言标准库中的 qsort() 函数是专门用来给数组排序的，且只要给它提供一个合适的比较函数，它可以排序任意类型的数组。
1. qsort() 函数原型
void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*));
可以看到上面函数原型中的第一个参数 base 是 void* 指针，因为该函数预先并不知道你要排序哪种类型的数组，所以只能使用 void* 指针来进行接收待排序数组的首地址。第二个参数 nmemb 的类型是 size_t 用来接收数组元素的个数。第三个参数 size 的类型是 size_t 用来接收数组每个元素的大小，单位字节。最后一个参数 compar 的类型是指向需要两个 const void* 的指针作为参数且返回值为 int 的数组，该指针的作用是回调我们传递的比较函数，因为 qsort 函数预先不知道我们需要比较的类型，可能是 int、double，也可能是字符串或者结构体。
2. 使用 qsort() 函数
接下来分别使用 qsort() 函数来排序 int 数组、double 数组、字符串数组以及结构体数组。需要分别为这四种类型设计四个比较函数：
// 头文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 学生结构体
typedef struct Stu
{
char name[20];
char age;
}Stu;
// int 类型比较
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*) e2;
}
// double 类型比较
int cmp_double(const void* e1, const void* e2)
{
return *(double*)e1 - *(double*)e2;
}
// 字符串类型比较
int cmp_str(const void* e1, const void* e2)
{
return strcmp((char*)e1, (char*)e2);
}
// Stu 结构比较
int cmp_Stu(const void* e1, const void* e2)
{
return (*(Stu*)e1).age - (*(Stu*)e2).age;
}
使用 qsort() 函数需要包含头文件 stdlib.h，使用字符串比较函数 strcmp() 需要包含头文件 string.h。下面是创建所需变量和排序的代码：
int main()
{
// int 类型排序
int arr_i[10] = { 1,3,5,7,9,2,4,6,8,0 };
int sz = sizeof(arr_i) / sizeof(arr_i[0]);
printf("排序前: ");
print_arr_i(arr_i, sz);
printf("排序后: ");
qsort(arr_i, sz, sizeof(int), cmp_int);
print_arr_i(arr_i, sz);
// double 类型排序
double arr_d[] = { 1.1,9.9,8.8,3.3,6.6,7.7,4.4,5.5 };
sz = sizeof(arr_d) / sizeof(arr_d[0]);
printf("排序前: ");
print_arr_d(arr_d, sz);
printf("排序后: ");
qsort(arr_d, sz, sizeof(double), cmp_double);
print_arr_d(arr_d, sz);
// 字符串类型排序
char arr_str[5][20] = {
"abcde111",
"ecdba222",
"mnbvd333",
"iknhk444",
"cvbnm555"
};
sz = sizeof(arr_str) / sizeof(arr_str[0]);
printf("\n排序前:\n");
print_arr_str(arr_str, sz);
printf("排序后:\n");
qsort(arr_str, sz, sizeof(arr_str[0]), cmp_str);
print_arr_str(arr_str, sz);
// Stu 结构类型排序
Stu arr_Stu[3] = {
{"张三", 20},
{"王五", 19},
{"李四", 18}
};
sz = sizeof(arr_Stu) / sizeof(arr_Stu[0]);
printf("\n排序前:\n");
print_arr_Stu(arr_Stu, sz);
printf("排序后:\n");
qsort(arr_Stu, sz, sizeof(arr_Stu[0]), cmp_Stu);
print_arr_Stu(arr_Stu, sz);
return 0;
}
程序的运行结果如下：
三、仿照 qsort 函数设计一个可以排序任意类型数组的冒泡函数
1. 函数原型
// 仿照 qsort 函数设计一个可以排序任意类型数组的冒泡函数
void bubble_sort(void* start, size_t n, size_t size, int (*cmp)(const void* e1, const void* e2));
这里需要知道，我们实现的 bubble_sort() 函数和库函数 qsort() 只是排序使用的算法不同，其他的思路都是一样的，所以函数的参数和返回类型也是一样的。
2. 函数设计思路
进入函数 bubble_sort 以后，冒泡排序的整体是不变的，依旧是嵌套循环，外层是排序次数，内层是比较次数。但是由于预先不知道传入数组的元素类型，所以我们面临如下两个问题：
（1）在比较的时候如何传递每个元素的地址
（2）如何交换相邻的元素
首先，我们知道传入数组的首地址以及数组每个元素的大小。那么我们可以把数组首地址强制类型转换为 char* 类型，然后加上数组元素大小的整数倍，那么就可以得到数组的每个元素的地址了。思路如下图：
所以，就可以写出如下代码：
// 仿照 qsort 函数设计一个可以排序任意类型数组的冒泡函数
void bubble_sort(void* start, size_t n, size_t size, int (*cmp)(const void* e1, const void* e2))
{
int i;
for (i = 0; i < n - 1; ++i) // 外层排序 n-1 轮
{
int j;
for (j = 0; j < n - i - 1; ++j) // 内层比较 n-i-1 次
{
if (cmp((char*)start + j * size, (char*)start + (j + 1) * size) > 0) // 排升序
{
// 交换
}
}
}
}
那么如何交换两个元素？我们知道两个元素的首字节地址，也知道两个元素的大小，那么我们可以通过交换两个元素的每个字节来实现两个元素的交换。思路如下图：
按理来说应该把这个交换功能设计成一个函数，但是这里为了方便观看，就放在函数内部了：
// 仿照 qsort 函数设计一个可以排序任意类型数组的冒泡函数
void bubble_sort(void* start, size_t n, size_t size, int (*cmp)(const void* e1, const void* e2))
{
int i;
for (i = 0; i < n - 1; ++i) // 外层排序 n-1 轮
{
int j;
for (j = 0; j < n - i - 1; ++j) // 内层比较 n-i-1 次
{
if (cmp((char*)start + j * size, (char*)start + (j + 1) * size) > 0) // 排升序
{
// 交换
int k;
for (k = 0; k < size; ++k)
{
char tmp = *((char*)start + j * size + k);
*((char*)start + j * size + k) = *((char*)start + (j + 1) * size + k);
*((char*)start + (j + 1) * size + k) = tmp;
}
}
}
}
}
接下来使用前面 qsort() 函数排序的数据检验我们所写的 bubble_sort() 函数，只需要把调用的函数名 qsort 改成 bubble_sort 即可：
int main()
{
// int 类型排序
int arr_i[10] = { 1,3,5,7,9,2,4,6,8,0 };
int sz = sizeof(arr_i) / sizeof(arr_i[0]);
printf("排序前: ");
print_arr_i(arr_i, sz);
printf("排序后: ");
bubble_sort(arr_i, sz, sizeof(int), cmp_int);
print_arr_i(arr_i, sz);
// double 类型排序
double arr_d[] = { 1.1,9.9,8.8,3.3,6.6,7.7,4.4,5.5 };
sz = sizeof(arr_d) / sizeof(arr_d[0]);
printf("排序前: ");
print_arr_d(arr_d, sz);
printf("排序后: ");
bubble_sort(arr_d, sz, sizeof(double), cmp_double);
print_arr_d(arr_d, sz);
// 字符串类型排序
char arr_str[5][20] = {
"abcde111",
"ecdba222",
"mnbvd333",
"iknhk444",
"cvbnm555"
};
sz = sizeof(arr_str) / sizeof(arr_str[0]);
printf("\n排序前:\n");
print_arr_str(arr_str, sz);
printf("排序后:\n");
bubble_sort(arr_str, sz, sizeof(arr_str[0]), cmp_str);
print_arr_str(arr_str, sz);
// Stu 结构类型排序
Stu arr_Stu[3] = {
{"张三", 20},
{"王五", 19},
{"李四", 18}
};
sz = sizeof(arr_Stu) / sizeof(arr_Stu[0]);
printf("\n排序前:\n");
print_arr_Stu(arr_Stu, sz);
printf("排序后:\n");
bubble_sort(arr_Stu, sz, sizeof(arr_Stu[0]), cmp_Stu);
print_arr_Stu(arr_Stu, sz);
return 0;
}
运行结果和使用 qsort() 函数时是一样的：