C语言-- 深入理解指针（4）

书接上回：C语言-- 深入理解指针（3）

前言：在上一篇C语言–深入理解指针（3）中的末尾，我们讲到了转移表的实现有两种方法：使用函数指针数组 和 使用回调函数。第一种方法我们已经学习过了，下面我们就来尝试第二种方法——回调函数 。

一、回调函数

首先我们要知道回调函数是什么？
回调函数就是通过函数指针调用的函数。
如果你把一个函数的指针（地址）作为函数参数传给了另一个函数，当在另一个函数体内通过该函数指针来调用所指向的函数时，这个被调用的函数就是回调函数。

使用回调函数来实现计算器：
思考：

1. 既然case 1到case 4中的语句只有函数不一样，那么我们可以将其封装成一个函数Cal来简化代码冗余；
2. 函数名就相当于函数的地址（指针），四个运算函数的函数指针类型一样都是int(*p)(int, int)，所以需要进行什么操作（加减乘除），就可以将该操作的函数名（Add，Sub，Mul，Div），作为函数指针的参数传给Cal函数，在函数内部进行调用p(x, y)，被调用的函数就是回调函数

#include <stdio.h>void menu()
{printf("****************************\n");printf("******     计算器     ******\n");printf("****** 1.Add   2. Sub ******\n");printf("****** 3.Mul   4. Div ******\n");printf("******     0.exit     ******\n");printf("****************************\n");}int Add(int x, int y)
{return x + y;
}int Sub(int x, int y)
{return x - y;
}int Mul(int x, int y)
{return x * y;
}int Div(int x, int y)
{return x / y;
}
void Cal(int(*p)(int, int))
{printf("请输入两个操作数：\n");int x = 0;int y = 0;int ret = 0;scanf("%d %d", &x, &y);ret = p(x, y);printf("%d\n", ret);
}int main()
{int input = 0;do{menu();printf("请选择您的操作：\n");scanf("%d", &input);switch (input){case 1:Cal(Add);break;case 2:Cal(Sub);break;case 3:Cal(Mul);break;case 4:Cal(Div);break;case 0:printf("计算结束，退出计算器...\n");break;default:printf("选择错误，请重新选择：\n");break;}} while (input);return 0;
}

二、冒泡排序

在编程中，我们有时可能会遇到一些需要将数组中的一组数据排序的问题，冒泡排序就是一种对整型数据进行排序的方法。
冒泡排序的核心思想是：两两相邻元素进行比较。

具体步骤：

1. （以升序为例）每一次将两两相邻元素进行比较，如果前面一个元素大，就将两个元素交换位置，然后进行下一对比较，直到一趟比完，该趟所比较的数据中最大的数据就会被排到最后。
2. 上一趟比较已经将一个最大的数放在了最后，所以下一趟比较就不需要再比较这个数，所以对剩余的数据进行下一趟排序
3. 当只剩下最后一个数时，排序就完成了。 也就是说如果有n个数，那么就需要n - 1次趟排序，因为每一次交换是两个数据进行比较交换，n - 1趟排序已经分别将每一趟的最大数依次从后往前放在了最后面，即已经将n -
   1个数据排好了，剩下的一个数据自然也就在最前面。

比如：给你一组数据：5 8 6 3 1 2 9 7
让你将其排为升序，即：1 2 3 5 6 7 8 9

第一趟排序：两两比较，将最大的数9排在了最后

第二趟排序：9已经排好了位置，所以不需要再比较和改变，于是对剩余的7个数进行排序：
以此类推，当第七趟排序后，前七位大的数已经从后往前分别排好了位置，那么最后一个最小的数1自然就在第一个位置。

代码如下：

void Bubble_sort(int arr[], int sz)
{int i = 0;for (i = 0; i < sz - 1; i++)//n个数，需要n - 1趟排序{int j = 0;for (j = 0; j < sz - 1 - i; j++)//前一趟已经排好了一个最大的数{								//所以每一趟需要排序的数据的个数都会少一个数//如果前一个数大于后一个数，就交换if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}void print(int arr[], int sz)//打印
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}int main()
{int arr[] = { 5, 8, 6, 3, 1, 2, 9, 7 };int sz = sizeof(arr) / sizeof(arr[0]);Bubble_sort(arr, sz);print(arr, sz);return 0;
}

优化后的冒泡排序：

当我们需要排序的一组数据是一组接近有序的数据比如1 2 3 4 5 6 7 9 8时，此时仅仅需要一趟排序将8和9交换，即可完成最终排序。但是程序却还是需要每一趟一次次的排序，未免效率有些低下。

所以我们可以优化一下：

1. 在每一趟排序之前，设置一个检测变量flag，令其为1，int flag = 1;；
2. 进入每一趟的循环，如果在该趟排序中发生了交换，将检测变量flag置为0：flag = 0 ，如果没有交换，什么也不需要做，则flag == 1没有被改变；
3. 在趟数的循环内，在每一趟的循环外，当每一趟循环结束后，对检测变量flag进行检测： 如果flag == 0，说明该趟排序发生了交换，那就接着进行下一次排序； 如果flag == 1，说明该趟排序没有发生交换，那就说明所有数据已经排序完成了，就直接使用break；退出循环，循环结束。

这样就可以提升冒泡排序的效率。

代码如下：

void Bubble_sort(int arr[], int sz)
{int i = 0;for (i = 0; i < sz - 1; i++)//n个数，需要n - 1趟排序{int flag = 1;int j = 0;for (j = 0; j < sz - 1 - i; j++)//前一趟已经排好了一个最大的数{								//所以每一趟需要排序的数据的个数都会少一个数//如果前一个数大于后一个数，就交换if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = 0;}}if (flag == 1){break;}}
}

三、qsort函数

除了冒泡排序，在C语言中提供了一个快速排序的库函数qsort可以直接使用来帮助我们排序数据，而且它可以帮助我们排序各种类型的数据。
具体可以参照https://legacy.cplusplus.com/reference/cstdlib/qsort/?kw=qsort中所给的定义。

函数原型：

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

使用qsort函数需要包含头文件：#include <stdlib.h>
参数：

• base 表示指向需要排序的数组的第一个元素的指针，类型是void* 表示可以接受任意类型的元素的地址（因为qsort可以排序各种类型的数据）；
• num 表示数组中的元素个数，类型是size_t ，无符号整型；
• size 表示数组中每个元素的大小，以字节为单位，类型是size_t ，无符号整型；
• int (*compar)(const void*, const void*) 表示指向比较两个元素的函数的指针（可以是函数名），该比较函数用来实现两个数据如何进行比较。（因为qsort可以排序各种类型的数据）
  

qsort库函数规定了：
比较函数的函数原型必须遵循以下形式：int compar (const void* p1, const void* p2);
即返回类型必须是int，两个比较元素的参数必须是const void *，变量名可以随便取
该函数只需要通过返回值的形式来决定元素的顺序：

如果p1指向的元素 > p2指向的元素，返回一个大于0的数；
如果p1指向的元素 = p2指向的元素，返回0；
如果p1指向的元素 < p2指向的元素，返回一个小于0的数；

比如如果对存放int类型的数组排成升序，比较函数就可以直接写成：

int cmp_int(const void* p1, const void* p2)//比较函数
{return *(int*)p1 - *(int*)p2;
}

解释：

1. 首先p1和p2是const void*类型的指针变量，所以不能直接解引用得到数据；

2. 数组元素是int类型，所以要先将其强制类型转换为(int*)类型，然后再解引用拿到p1和p2指向的两个数；

3. 如果p1比p2指向的数大，根据qsort对比较函数的定义，要返回一个大于0的数，那么既然p1比p2指向的数大，他俩的差值必然>0。
   同理如果p1比p2指向的数小于或者相等，二者差值一样会 <0 或者 = 0；

4. 所以直接返回二者差值就能达到目的；

当然如果对数组降序排序，将两个指针换个位置就行：

int cmp_int(const void* p1, const void* p2)//比较函数
{return *(int*)p2 - *(int*)p1;
}

3.1 使用qsort函数排序整型数据

#include <stdio.h>
#include <stdlib.h>void print(int arr[], int sz)//输出打印
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}int cmp_int(const void* p1, const void* p2)//比较函数
{return *(int*)p1 - *(int*)p2;
}int main()
{int arr[] = { 1,3,5,7,9,2,4,6,8,10 };size_t sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(int), cmp_int);print(arr, sz);return 0;
}

3.2 使用qsort函数排序double数据

使用qsort库函数对于存放double类型数据的数组排序，比较函数就不能直接返回两个元素相减的值了，因为两个double得出来的还是一个double的数，而函数定义中规定了比较函数的返回值必须是int类型的数。

这时肯定会有人那将这两个double类型的数的差值强制类型转换成int类型不就行了吗？这种写法肯定是错误的，因为从double到int的强制类型转换只会取整数部分，如果两个double类型的数的差值的绝对值小于1，那么强制类型转换的结果就是0，就会造成错误。

所以可以使用if语句或者直接使用三目操作符来解决：

#include <stdio.h>
#include <stdlib.h>void print_double(double arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%lf ", arr[i]);}
}int cmp_double(const void* p1, const void* p2)
{return *(double*)p1 > *(double*)p2 ? 1 : -1;//return *(double*)p1 < *(double*)p2 ? 1 : -1;//降序
}int main()
{double arr[] = { 1.0,3.0,5.0,7.0,9.0,2.0,4.0,6.0,8.0 };size_t sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(double), cmp_double);print_double(arr, sz);return 0;
}

3.3 使用qsort来排序结构体数据

比如我们需要对学生的信息排序，一个学生的信息包括年龄和姓名，我们将其包装成结构体：

struct Student
{char name[20];int age;
};

1. 对该结构体排序，如果对name字符串排序

学生姓名是字符串，放到name字符数组中，所以我们需要写对于结构体中的字符串的比较函数，我们使用strcmp字符比较函数，刚好可以满足qsort库函数对于比较函数的返回值的要求
当然使用strcmp库函数需要包含头文件#include <string.h>

int strcmp ( const char * str1, const char * str2 );

如果str1指向的字符串比str指向的字符串大，那么返回一个>0的数字；
如果str1指向的字符串比str指向的字符串一样，那么返回一个=0的数字；
如果str1指向的字符串比str指向的字符串小，那么返回一个<0的数字；

具体函数介绍可以参考：https://legacy.cplusplus.com/reference/cstring/strcmp/?kw=strcmp

于是可以写出比较函数：
注意结构体指针对结构体成员的访问操作符->的优先级比强制类型转换的括号( )高，所以在对const void*类型的p1和p2强制类型转换为结构体指针(struct Student*)p1后再加上括号才能使用->对结构体成员进行访问。

int cmp_by_name(const void* p1, const void* p2)
{return strcmp(((struct Student*)p1)->name, ((struct Student*)p2)->name);
}

完整代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>struct Student
{char name[20];int age;
};int cmp_by_name(const void* p1, const void* p2)
{return strcmp(((struct Student*)p1)->name, ((struct Student*)p2)->name);
}int main()
{struct Student s[] = { {"zhangsan",37},{"lisi",22},{"wangwu", 19} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_by_name);return 0;
}

2. 同理，如果是对结构体中的age整型排序

对于比较函数来说，首先要将比较函数的参数类型const void*的指针变量，强制类型转换为指向结构体的指针struct Student*，加上括号然后通过->访问结构体成员age；
此时就是对于一个int类型的排序，就直接二者相减就行：

int cmp_by_age(const void* p1, const void* p2)
{return ((struct Student*)p1)->age - ((struct Student*)p2)->age;
}

完整代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>struct Student
{char name[20];int age;
};int cmp_by_age(const void* p1, const void* p2)
{return ((struct Student*)p1)->age - ((struct Student*)p2)->age;
}int main()
{struct Student s[] = { {"zhangsan",37},{"lisi",22},{"wangwu", 19} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_by_age);return 0;
}

四、模仿qsort库函数实现通用的冒泡排序

一般来说冒泡排序是用来排序整型数据的，我们了解了qsort库函数的实现逻辑，那么我们也可以尝试模仿qsort库函数来模拟实现一个可以排序任意类型数据的通用的冒泡排序。

普通冒泡排序：

void Bubble_sort(int arr[], int sz)
{int i = 0;for (i = 0; i < sz - 1; i++){int j = 0;for (j = 0; j < sz - 1 - i; j++){								if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

对于通用的冒泡排序，基于普通冒泡排序的改造分析：

1. 首先如果想要使用冒泡排序来排序任意类型的数据，参数的类型和数量毫无疑问是要改变的，

void bubble_sort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*));

• base 表示指向需要排序的数组的第一个元素的指针，类型是void* 表示可以接受任意类型的元素的地址
• num 表示数组中的元素个数，类型是size_t ，无符号整型；
• size 表示数组中每个元素的大小，以字节为单位，类型是size_t ，无符号整型；
• int (*compar)(const void*, const void*) 表示指向比较两个元素的函数的指针（可以是函数名），该比较函数用来实现两个元素如何进行比较。

2. 其次，对于冒泡排序的趟数和每一趟的比较逻辑的两层for循环框架不需要改变（要不然就不是冒泡了哈哈）；
3. 因为可以排序任意类型的数据，所以对于if语句中对于两个元素大小的比较判断，需要改为一个比较函数compar，需要比较什么类型的数据，就传参比较这种类型数据的函数。这也是为什么函数参数中需要一个函数指针
4. 比完了大小，如果需要交换，同理那么对于任意类型的数据的交换肯定也需要改为一个交换函数Swap，来交换任意类型的数据。

void bubble_sort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*))
{
//函数里面实则还是冒泡排序int i = 0;for (i = 0; i < num - 1; i++){int j = 0;for (j = 0; j < num - i - 1; j++){//进行判断和交换}}
}

通过分析，我们需要编写比较判断函数compar和交换函数Swap：

对于比较函数，和qsort库函数的比较函数是一样的，直接在if语句中判断是否>0;
如果>0，则交换；否则不交换。

但是函数需要传两个参数，分别是指向两个元素的指针（地址），所以就需要使用到其他的参数来表示这两个元素的地址了。
base是数组的首元素的地址，size是数组每一个元素的大小，j代表数组元素的下标，所以(char*)base + j * size，就可以表示第j个数组元素的指针（地址）-- （base在函数声明中是void*类型，需要强制类型转换为（char*），所以 + j * size就表示跳过 j * size个字节，从而到达可以遍历每一对元素的目的)， 而(char*)base + (j + 1) * size就可以表示第j + 1个数组元素的指针（地址）

if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0)//进行判断
{//进行交换
}

对于交换函数，既然要达到可以交换任意类型的目的，肯定不能像之前那样直接创建一个int类型的临时变量，每一次交换4个字节对二者进行交换了。

因为类型不可知，有可能是普通类型，也有可能是自定义类型，所以不能采用直接创建临时变量一次性交换的方法。
但是类型大小最小起码是一个字节，所以我们可以一个字节一个字节的交换，因为通用冒泡排序函数中有参数size来代表类型的大小，可以作为交换循环的结束条件。

void Swap(char* ptr1, char* ptr2, size_t size)
{int i = 0;for (i = 0; i < size; i++){char temp = *ptr1;*ptr1 = *ptr2;*ptr2 = temp;ptr1++;ptr2++;}
}

ptr1就传参(char*)base + j * size，ptr2就传参(char*)base + (j + 1) * size

完整代码：
注：比较函数compar有具体传参决定。

void Swap(char* ptr1, char* ptr2, size_t size)
{int i = 0;for (i = 0; i < size; i++){char temp = *ptr1;*ptr1 = *ptr2;*ptr2 = temp;ptr1++;ptr2++;}
}void bubble_sort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*))
{int i = 0;for (i = 0; i < num - 1; i++){int j = 0;for (j = 0; j < num - i - 1; j++){if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0){Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);}}}
}

4.1 通用冒泡排序函数排序整型数据

void Swap(char* ptr1, char* ptr2, size_t size)
{int i = 0;for (i = 0; i < size; i++){char temp = *ptr1;*ptr1 = *ptr2;*ptr2 = temp;ptr1++;ptr2++;}
}void bubble_sort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*))
{int i = 0;for (i = 0; i < num - 1; i++){int j = 0;for (j = 0; j < num - i - 1; j++){if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0){Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);}}}
}int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}print_int(int arr[], int sz)//输出打印
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}int main()
{int arr[] = { 9,8,7,6,5,4,3,2,1 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);print_int(arr, sz);return 0;
}

4.2 通用冒泡排序函数排序结构体数据

struct Student
{char name[20];int age;
};int cmp_by_name(const void* p1, const void* p2)
{return strcmp(((struct Student*)p1)->name, ((struct Student*)p2)->name);
}int cmp_by_age(const void* p1, const void* p2)
{return ((struct Student*)p1)->age - ((struct Student*)p2)->age;
}void Swap(char* ptr1, char* ptr2, size_t size)
{int i = 0;for (i = 0; i < size; i++){char temp = *ptr1;*ptr1 = *ptr2;*ptr2 = temp;ptr1++;ptr2++;}
}void bubble_sort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*))
{int i = 0;for (i = 0; i < num - 1; i++){int j = 0;for (j = 0; j < num - i - 1; j++){if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0){Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);}}}
}int main()
{struct Student s[] = { {"zhangsan",37},{"lisi",22},{"wangwu", 19} };int sz = sizeof(s) / sizeof(s[0]);bubble_sort(s, sz, sizeof(s[0]), cmp_by_name);//比较结构体中的name//bubble_sort(s, sz, sizeof(s[0]), cmp_by_age);//比较结构体中的agereturn 0;
}

结语：C语言-- 深入理解指针（4） 章节到这里就结束了。
本人才疏学浅，文章中有错误和有待改进的地方欢迎大家批评和指正，非常感谢您的阅读！如果本文对您又帮助，可以高抬贵手点点赞和关注哦！