【C语言】手把手带你拿捏指针(4)（含qsort函数详解）
【C语言】手把手带你拿捏指针(4)（含qsort函数详解）
一、回调函数
什么是回调函数？ 回调函数就是⼀个通过函数指针调用的函数。 如果你把函数的指针（地址）作为参数传递给另⼀个函数，当这个指针被用来调用其所指向的函数时，被调用的函数就是回调函数。回调函数不是由该函数的实现方直接调用，而是在特定的事件或条件发⽣时由另外的一方调用的，用于对该事件或条件进行响应 可能这么说着有些抽象，我们还是举一个例子，比如上一篇文章我们讲到的计算器，我们当时为了解决代码冗余，使用了转移表，也就是函数指针数组，那么是否还有其它方法呢？比如我坚持使用Switch语句，而不使用if语句 这个内容就涉及到我们的回调函数，回调函数简单地说就是将函数指针传给另一个函数，通过这个函数来使用传过来的函数 我们可以将之前冗余的部分包装成函数，最大的冗余就是那个Switch语句，我们来看看冗余部分：
switch (input)
{
case 0:
printf("已退出计算器！");
break;
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;
}可以看到，这些冗余部分它们大都很相似，不同之处只有调用的函数不同，那我们就可以将它们包装成函数，而不同的地方是调用的函数，那我们就把对应的计算函数传给这个函数，然后通过这个函数调用计算函数，那么计算函数就是回调函数 我们需要的函数的参数就是一个函数指针，可以指向一个函数，然后我们就可以通过这个函数指针去访问对应的计算函数，而这里的计算函数都是相似的，于是这个函数可以写成：
void test(int (*p)(int,int))
{
int x, y;
printf("请输入两个整数：");
scanf("%d %d", &x, &y);
printf("\n");
int ret = p(x, y);
printf("ret = %d\n\n", ret);
}当我们要使用add函数时，我们就可以直接将add作为参数传给test函数，然后我们现在的Switch语句就可以每一项只调用一次test函数即可，参数就传对应的函数地址，也就是可以直接传函数名 所以回调函数版的计算器代码如下：
#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;
}
int div(int a, int b)
{
return a / b;
}
void menu()
{
printf("*************************\n");
printf(" 1:add 2:sub \n");
printf(" 3:mul 4:div \n");
printf(" 0:exit \n");
printf("*************************\n\n");
printf("请选择：");
}
void test(int (*p)(int,int))
{
int x, y;
printf("请输入两个整数：");
scanf("%d %d", &x, &y);
printf("\n");
int ret = p(x, y);
printf("ret = %d\n\n", ret);
}
int main()
{
int input = 0;
int ret = 0;
do
{
menu();
scanf("%d", &input);
switch (input)
{
case 0:
printf("已退出计算器！");
break;
case 1:
test(add);
break;
case 2:
test(sub);
break;
case 3:
test(mul);
break;
case 4:
test(div);
break;
}
} while (input);
return 0;
}最后我们再来总结一下回调函数：把函数的指针（地址）作为参数传递给另⼀个函数，当这个指针被⽤来调⽤其所指向的函数时，被调⽤的函数就是回调函数 在上例中，将计算函数的地址传给函数test，然后通过test函数来调用计算函数，那么这些计算函数就叫做回调函数
二、qsort函数使用举例
1.qsort解析
qsort是一个排序函数，使用它需要包含头文件stdlib.h，它可以根据我们的情况来对我们的数据进行排序，我们之前学过一种排序----冒泡排序 但是它只能对整型进行排序，如果是浮点型，字符型，甚至于是结构体类型的变量呢？如果对它们每一种类型重新写一个冒泡排序，那么就太麻烦了，于是我们可以使用qsort函数 接下来我们开始学习qsort函数，我们可以打开cplusplus网站，然后切换到旧版本，如图所示：
随后我们进入的界面如下：
我们首先看到左上角的function，说明它是一个函数，下面绿色的是它的原型，我们将它拿出来：
void qsort (void* base,
size_t num,
size_t size,
int (*compar)(const void*,const void*));可以看到它有四个参数，分别是一个未知类型的指针，两个size_t的值，还有一个函数指针类型，那它们分别是什么含义呢？在网站下方的四段就分别描述了它们的作用，如下：
根据解析，我们可以知道 （1）void* base是我们要排序的数组第一个元素的地址，也就是我们可以把要排序的数组的数组名传过去 （2）size_t的num，它的含义是数组的元素个数，所以我们需要求元素的个数 （3）size_t的size，它的含义是数组中单个元素的大小，一般的方法就是用sizeof算出数组的第一个元素大小，将其传过去 我们可以思考一下为什么要传单个元素大小，因为我们传过去的数组首元素地址是void * 的指针接收的，如果不知道单个元素的大小，函数就不知道这个void * 的指针解引用要访问几个字节，所以要传单个元素的大小，到后面模拟实现qsort函数时还会再强调 （4）最后一个参数是返回类型是int，参数为两个const void * 的指针的函数指针compar，它的作用就是比较两个元素的大小，这两个元素就是两个const void * 指针指向的对象 但是这个函数要由使用者来完成，这就是为了使得这个函数更具有兼容性，使用者要排序什么类型，就自己写一个比较这种类型的函数，并且这个函数要和规定示范的compar函数形式一致 而这个比较函数也比较简单，不用完全像实现冒泡排序一样写下全过程，只需要比较两个const void*指针对应元素的大小，当前一个元素大于后一个元素时，函数返回大于0的数，相等就返回0，小于就返回一个小于0的数
2.qsort函数排序整型举例
我们现在创建一个乱序的整型数组arr，然后使用qsort对它进行排序，最后将它打印出来： 首先我们写好头文件，然后我们将数组创建好，以及算出对应的数组元素个数，如下：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int arr[] = { 5,3,6,2,7,1,4,10,9,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
return 0;
}随后我们开始使用qsort函数，按照对应要求写上它的参数，最后一个参数我们先写上一个函数cmp_int，随后对它进行实现，如下：
qsort(arr, sz, sizeof(arr[0]), cmp_int);现在qsort准备工作做好了，我们开始实现cmp_int，这个cmp_int函数应该和上面样例中的compar函数一致，返回类型为int，参数为两个const void*，可以分别取名为e1，与e2，如下：
int cmp_int(const void* e1, const void* e2)
{
}随后就是比较e1和e2指向的对象的大小，如果前者大于后者，函数返回一个大于0的数，相等则返回0，小于返回一个小于0的数，那么我们怎么实现这个功能呢？ 其实我们可以让e1指向的元素减去e2指向的元素，然后将其作为返回值返回，如果前者大于后者，函数就会返回一个大于0的数，相等则返回0，小于返回一个小于0的数，很轻松就实现了该功能 现在最后一个问题来了，如何拿到e1和e2指向的元素，由于e1和e2是void * 的指针，无法解引用，由于我们比较的是整型的大小，所以我们可以将e1和e2强制类型转换成int * 类型的指针，然后再对它们解引用，起初将函数参数设计为void*也是因为不知道比较的元素是什么，需要真正使用时由使用者进行强制类型转换 所以最后我们可以实现这个函数了，如下：
cmp_int(const void* e1, const void* e2)
{
return *(int*) e1 - *(int*) e2;
}最后我们将数组arr打印出来，让我们来看看qsort有没有实现我们需要的结果：
可以看到qsort帮我们升序排列了这个数组，那能不能降序呢？这个时候我们可以把e1和e2换个位置，如下：
最后可以看到最后将arr降序排列了
3.qsort排序结构体举例
有了使用qsort排列整型数据的案例，就可以照猫画虎排序结构体了 首先我们创建一个结构体stu，用它描述一个学生的信息，为了方便，这里只在里面创建两个成员，一个是char数组表示姓名，一个是int类型表示年龄，如下：
struct stu
{
//姓名
char name[20];
//年龄
int age
};随后我们创建一个结构体数组，用来存放学生信息，对它进行初始化，如：
struct stu s[3] = { {"zhangsan",13},{"lisi",18},{"wangwu",23} };随后我们可以使用qsort进行排序，方法还是与整型一致，只是特别的是排序函数，我们不能贪多，一次对姓名和年龄同时排序，需要选择其中一种，这里我们选择姓名进行排名，如：
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);最后我们要关注的是如何实现这个函数，首先它的返回类型和参数就不说了，首先是我们如何通过e1和e2拿到结构体中的name数组，我们还是可以将e1强制转换为结构体指针，然后解引用，拿到结构体，最后用点操作符找到name数组 如下：
int cmp_stu_by_name(const void* e1, const void* e2)
{
return (*(struct stu*)e1).name - (*(struct stu*)e2).name;
}那么这样过后代码可以正常运行吗？我们来运行试试：
可以看到函数什么也没做，没有帮我们进行排序，那问题出在哪里呢？没错，可能你已经想到了，name数组里面一个存的是一个字符串，不能直接加减，要用函数strcmp进行比较 而strcmp的返回值刚好符合qsort的要求，前面的字符串更大就返回大于0的数，相等返回0，小于返回小于0的数，所以我们用strcmp就可以解决这个问题，最后记得包含头文件string.h，如下：
#include <string.h>
int cmp_stu_by_name(const void* e1, const void* e2)
{
return ((*(struct stu*)e1).name , (*(struct stu*)e2).name);
}最后我们来看看函数能否正确帮我们排序：
可以看到程序成功帮我们实现了相应的功能，到这里相信大家已经对qsort的了解已经大差不差，超越了许多人，随后我会手把手带你模拟实现一下qsort，来看看它到底是怎么用这四个参数就帮我们实现各种类型数据的排序的
三、qsort函数模拟实现
1.qsort解析(深入)
我们在模拟实现qsort前，首先我们要知道其实qsort的原型本质上采用的快速排序，而我们只学过冒泡排序，所以我们模拟实现时就采用冒泡排序，实现一次冒泡排序版的qsort 我们再来看看qsort的参数，以及它们的作用，方便我们对它进行模拟实现，如图：
（1）第一个参数是void*类型的指针参数，用来接收数组的第一个元素的地址。我们要知道为什么这里要使用void，因为qsort是为了排序所有类型数据而创造的，所以最开始我们并不知道要排序哪种类型，所以就要用void，那不知道具体类型，如何访问元素呢？我们后面会讲到 （2）第二个参数是size_t的num，用来表示数组元素的个数，这个没有什么特别的，就不多讲 （3）第三个参数是size_t的size，它用来表示数组中一个元素的大小，那么为什么要传一个元素的大小呢？这就是我们前面提到的，虽然我们传过去了数组首元素的地址，但是我们不知道这个数组里面是什么类型的元素，不知道解引用去访问几个字节，于是我们就可以把数组元素的大小传过去，到时候解引用就可以知道一次访问几个字节 （4）最后一个参数就非常熟悉了，就是用于比较数组两个元素的大小，我们也可以想想这是为什么，很明显是因为我们不知道具体类型，不能盲目比较两个元素的大小，比如整型可能用大于小于，而字符串用strcmp，所以需要用户帮我们写出如何比较两个元素的大小，有了这个，就可以一个一个慢慢比较所有元素的大小进行排序
2.qsort的模拟实现
在上面我们仔细分析了qsort参数的作用后，我们还需要注意几点：
- 我们的qsort函数的参数尽量与原版的qsort的参数保持一致
- 我们在排序时采用冒泡排序
- 在冒泡排序中，我们需要用用户传来的函数compar来比较两个元素的大小
- 在交换时不能指定同时交换多少字节，我们可以根据元素大小，一个字节一个字节的交换数据
现在我们来开始设计我们的qsort函数： （1）函数名：my_bubble_qsort，含义是我的冒泡qsort，可以自行取名 （2）函数参数：与原版qsort参数保持一致，如下：
void my_bubble_qsort(void* base, size_t num ,size_t size ,
int (*compar)(const void*,const void*))（3）函数实现：
- 函数的大致模型就是冒泡排序的样子，如果还不会冒泡排序，可以参见指针(2)，这里直接给出模型：
void my_bubble_qsort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*))
{
int i = 0;
int j = 0;
for (i = 0; i < num-1; i++)
{
for (j = 0; j < num-i-1; j++)
{
}
}
}- 难点一：由于不知道元素类型，所以我们首先要解决的就是如何对两个元素比大小，我们现在有了元素大小，就有了每个元素一次访问几个字节，比如元素大小4个字节，我们只需要让我们的void*的指针一次访问4个字节，怎么实现呢？
- 难点二：如何让void * 的指针一次访问一个元素的大小，我们可以把void* base指针强制类型转换为char* base，这样就可以访问一个字节，要访问数组第一个元素就可以直接使用(char*)base，第二个元素就可以使用(char*)base+1 * size，第三个元素(char * )base+2 * size，以此类推，第j个元素就是(char*)base+j*size，j的后一个元素就是(char * )base+(j+1) * size
- 然后得到第j个元素的地址，和它后一个元素的地址，就可以直接将它们传给函数compar帮我们对这两个元素进行比较，根据返回值进行判断，如果大于0，就是前一个元素大，由于我们按默认升序设计，所以此时就将它们换一个位置，我们来看一下函数的使用方法：
if (compar((char*)base + size * j, (char*)base + size * (j + 1)) > 0)- 难点三：如何将满足条件的两个元素交换，这里我们可以设计一个函数exg，用来帮我们交换这两个元素，首先我们还是将要交换的两个元素的地址传过去，然后就是交换方法，比如字符串并不能采用赋值的交换的方式，所以我们不能直接对元素解引用，我们可以采用一个字节一个字节的交换，将两个元素的所有字节交换，也就完成了两个元素的交换
- 所以我们需要将一个元素的大小传过去，比如4个字节，那么我们就以char*的方式交换4次就可以实现目的，按照元素大小进行遍历即可，函数的实现以及使用如下：
void exg(char* p1, char* p2,size_t size)
{
while (size--)
{
char a = *p1;
*p1 = *p2;
*p2 = a;
p1++;
p2++;
}
}//函数的使用：
exg((char*)base + size * j, (char*)base + size * (j + 1),size);（4）函数代码：
void exg(char* p1, char* p2,size_t size)
{
while (size--)
{
char a = *p1;
*p1 = *p2;
*p2 = a;
p1++;
p2++;
}
}
void my_bubble_qsort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*))
{
int i = 0;
int j = 0;
for (i = 0; i < num-1; i++)
{
for (j = 0; j < num-i-1; j++)
{
if (compar((char*)base + size * j, (char*)base + size * (j + 1)) > 0)
{
exg((char*)base + size * j, (char*)base + size * (j + 1),size);
}
}
}
}经过千辛万苦，我们终于实现了我们的qsort函数，接下来我们赶紧来使用一下它吧，如下：
int cmp_int(const void* e1,const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
void exg(char* p1, char* p2,size_t size)
{
while (size--)
{
char a = *p1;
*p1 = *p2;
*p2 = a;
p1++;
p2++;
}
}
void my_bubble_qsort(void* base, size_t num, size_t size,
int (*compar)(const void*, const void*))
{
int i = 0;
int j = 0;
for (i = 0; i < num-1; i++)
{
for (j = 0; j < num-i-1; j++)
{
if (compar((char*)base + size * j, (char*)base + size * (j + 1)) > 0)
{
exg((char*)base + size * j, (char*)base + size * (j + 1),size);
}
}
}
}
int main()
{
int arr[] = { 4,2,5,8,10,3,1,9,6,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
my_bubble_qsort(arr, sz, sizeof(arr[0]), cmp_int);
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}运行截图：
本期指针（4）就到此为止啦，稍微有点难，有不懂的地方可以提出来，下一篇指针（5）就是指针内容的最后一篇了，相信如果能够完全掌握这些东西，你已经是指针大佬了，敬请期待指针（5）吧！ byebye~~
腾讯云开发者
