C语言——深入理解指针（三）

1.回调函数是什么？

首先我们来回顾一下函数的直接调用：

在这里插入图片描述
而回调函数就是通过函数指针调用的函数。我们将函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，被调用的函数就是回调函数。

2.qsort函数

quick sort简称qsort，是C语言中提供的一个排序函数，是基于快速排序算法思想的一种排序算法。
其优点有：现成的排序算法可直接使用；而且大部分情况下效率都是比冒泡排序高的；qsort函数可以排序任意类型的数据

function
在这里插入图片描述

void qsort (void* base,//指针，指向了被排序数组的第一个元素size_t num, // 这里是base指向的被排序数组的元素个数size_t size,//这里是base指向的被排序数组的元素大小（长度），单位是字节int (*compar)(const void*,const void*)//函数指针，指针指向的函数是用来比较被排序数组中的两个元素的);

在这里插入图片描述
该函数排序默认为升序，希望为降序，只需将参数p1，p2顺序反过来即可

3.qsort函数的使用

qsort函数对整型数组的排序：

我们在使用qsort函数排序时，常需要自己写一个比较的逻辑，来比较整形数据的大小，如我们可以在这里写一个int cmp_int(const void* p1,const void* p2)函数指针，而指针指向的函数是用来比较被排序数组中的两个元素的，里面的p1,p2则分别指向一个整型变量，然后qsort函数根据返回的结果进行排序。整体整合下来如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//打印
void print_arr(int arr[], int sz)
{int i = 0;for (i = 0;i < sz;i++){printf("%d ", arr[i]);}printf("\n");
}
//写的是升序，若想改为降序，只需改变p1，p2的位置
int cmp_int(const void* p1,const void* p2)//const修饰函数参数，表示参数在函数体内不能被修改
{if (*(int*)p1 > *(int*)p2)//强制类型转换为整型return 1;else if (*(int*)p1 < *(int*)p2)return -1;elsereturn 0;//根据qsort函数的排序逻辑，上面这一部分也可简化为：return(*(int*)p1 - *(int*)p2);
}
void test()
{int arr[] = { 4,3,7,9,0,2,1,6 };int sz = sizeof(arr) / sizeof(arr[0]);print_arr(arr, sz);//打印排序前的数组//排序qsort(arr,sz,sizeof(arr[0]),cmp_int);print_arr(arr, sz);//打印排序后的数组
}
int main()
{test();return 0;
}

运行结果：
在这里插入图片描述

qsort函数对结构体数据的排序：

1.按照年龄比较，只需比较整形数据的大小：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Stu
{char name[30];int age;
};
void print_stu(struct Stu arr[], int sz)
{int i = 0;for (i = 0;i < sz;i++){printf("%s:%d\n", arr[i].name, arr[i].age);}
}
int cmp_stu_by_age(const void* p1, const void* p2)
{return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;
}
void test()
{struct Stu arr[] = { {"Jack",28},{"Rose",25},{"liming",19} };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);print_stu(arr, sz);
}
int main()
{test();return 0;
}

运行结果：
在这里插入图片描述

2.按照名字比较，这里注意比较的是字符串的大小，注意这里不能使用> >= < <= == !=，需要使用strcmp()函数：

//按照名字比较
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Stu
{char name[30];int age;
};
//p1指向了一个结构体变量
//p2指向了一个结构体变量
void print_stu(struct Stu arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%s: %d\n", arr[i].name, arr[i].age);}printf("\n");
}
int cmp_stu_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}
void test()
{struct Stu arr[] = { {"zhangsan", 20},{"lisi", 38},{"wangwu", 18} };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);print_stu(arr, sz);
}
int main()
{test();return 0;
}

运行结果：
在这里插入图片描述

4.qsort函数模拟实现

这里，依照qsort函数的逻辑，模拟实现一个底层逻辑为冒泡排序但可排序任意类型的数据的函数（即泛型编程）。

设计bubble_sort函数，只是底层算法和qsort函数不一样，但其参数可模拟qsort函数，第一个参数指向数组首元素的指针类比qsort我们记为base，同理第二个参数为size_t sz,第三个参数记为size_t width，第四个参数我们要写的是函数指针，因为不知道将要比较什么类型的数据，所以用void修饰取出的元素，而函数的返回类型因为知晓是整型则为int即int (cmp)(const void p1, const void* p2)
和冒泡排序的底层逻辑一样，首先确定外层比较的趟数，然后内层决定趟内部比较的对数。外层只需要算出有几个元素来确定需要几趟，那么内层比较该如何比较？该如何确定一趟比较的对数呢？这里就不同于冒泡排序了
这里需要将if(arr[j]>arr[j+1])修改，因为不知道类型，交换的时候并不仅仅是简单的比较整型元素的大小，但是由于此时已经知道比较方法cmp()，所以只需调用一下cmp()，现在需要将arr[j]和arr[j+1]这两个相邻元素的地址传到cmp（）中一个给p1，一个给p2。现在只知道base指向数组首元素的地址，那该如何越过中间的元素获取j和j+的地址呢？如下图：

下面一个问题就是如何交换这两个元素。由于不能将它们整体交换，只知道这两个元素的地址，所以可以将它们转换为字节来进行交换，假设一个元素占四个字节，则可将第一个字节与第一个字节交换，以此类推从而实现元素的交换。写一个Swap函数，其参数我们则需要传两个元素的地址(char*)base + j * width, (char*)base + (j + 1) * width和元素的宽度width，然后在交换函数中，使用一个for循环，让其对应字节元素相交换就实现交换了。
好，现在我们将其整合下来：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void print_arr(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}
int cmp_int(const void* p1, const void* p2)
{return (*(int*)p1 - *(int*)p2);
}
void Swap(char* buf1, char* buf2, size_t width)//交换 
{int i = 0;char tmp = 0;for (i = 0; i < width; i++){tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void bubble_sort(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i = 0;for (i = 0; i < sz - 1; i++){int j = 0;for (j = 0; j < sz - 1 - i; j++){if(cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}
void test()
{int arr[] = { 3,1,5,8,7,9,2,4,6,0 };int sz = sizeof(arr) / sizeof(arr[0]);print_arr(arr, sz);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);print_arr(arr, sz);
}
int main()
{test();  return 0;
}

运行结果：
在这里插入图片描述
上面已经可以完全排序整型数据了，现在我们来测试排序结构体数据，排序的思想一样，继续用bubble_sort（）函数。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Stu
{char name[30];int age;
};
void print_stu(struct Stu arr[], int sz)
{int i = 0;for (i = 0;i < sz;i++){printf("%s:%d\n", arr[i].name, arr[i].age);}
}
int cmp_stu_by_age(const void* p1, const void* p2)
{return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;
}
void Swap(char* buf1, char* buf2, size_t width)//交换 
{int i = 0;char tmp = 0;for (i = 0; i < width; i++){tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void bubble_sort(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i = 0;for (i = 0; i < sz - 1; i++){int j = 0;for (j = 0; j < sz - 1 - i; j++){if(cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}
void test()
{struct Stu arr[] = { {"Jack",28},{"Rose",25},{"liming",19} };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);//bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);print_stu(arr, sz);
}
int main()
{test();
}