3.1 回调函数
先了解一下回调函数的概念
为后面自我实现qsort做准备:
回调函数就是一个通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。回调函数不是由该函数的实现方直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或条件进行响应。
4. 库函数中qsort分析
首先qsort是一个用于排序的函数!
先来看官方的定义:
阅读文档可以知道以下内容:
- base指针是传待排序的空间
- num是指待排序元素个数
- size是指每一个元素所占字节大小
- 而最后一个参数是一个函数指针
经过仔细查阅资料可得:
函数指针指向的函数需要程序员自己实现
而又两个参数: 我称为A和B
A小于B: 返回值小于一
A大于B: 返回值大于一
A等于B: 返回值等于一
4.1 为什么这个函数需要我们自己实现?
因为每一个类型的数据的比较方式不同
并且操作者想要比较的数据可以有多个
比如:
- 整型的比较
int compar(void* x1,void* x2) { return *(int*)x1 - *(*int)x2); }
对代码的解释:
void*类型的数据不能直接解引用
所以要强制类型转换为int * 类型
假如你想要比较char类型的数据
这里就需要强制转换为char *
- 浮点型的比较
int compar(void* x1,void* x2) { return strcmp( (char*)x1, (char*)x2 ); }
对代码的解释:
字符不能单纯使用大于小于号比较
应该使用字符串操作函数比较大小
- 结构体的比较
struct stu { char name[20]={0};//学生姓名 int height =0;//学生身高 int grade =0;//学生成绩 }; compar(void* x1,void* x2)//以学生身高作为比较基准 { return ((struct stu*)x1)->height -((struct stu*)x2)->height; //强制转换为结构体指针 比较身高,指向height } compar(void* x1,void* x2)//以学生名字作为比较基准 { return strcmp(((struct stu*)x1)->name,((struct stu*)x2)->name); 强制类型转换为结构体指针 指向结构体中的name数组 }
对代码的解释:
在结构体中可以比较不同的成员
而比较前都应该先进行强制类型转换
并且指向对应的结构体成员
4.2 库函数qsort的使用
假设我们需要排序一个整型数组
下面来使用一下qsort函数
int compar(void* x1,void*x2) { return *(int*)x1 - *(int*)x2; } int main() { int a[6]={6,2,9,4,3,5}; qsort(a, 6, sizeof(int), compar); return 0; }
5. qsort函数的模拟实现
由于库函数中的qsort函数
的内部是由快速排序实现的
比较难理解
所以我们把内部简化为冒泡排序!
基本框架:
- 两层 if 语句实现冒泡大框架
- 比较大小时使用自定义函数compar
- 交换函数使用自定义函数Swap
5.1 大框架的实现
bubble_qsort(void* s, int sz, int width, int (*cmp)(void* x1, void* x2)) { for (int i = 0; i < sz - 1; i++) { for (int j = 0; j < sz - i - 1; j++) { if (比较条件函数) { Swap函数 } } } }
模仿库函数中的参数
用冒泡函数原理自己实现一个qsort!
5.2 比较函数的实现
在本章的4.2部分已经模拟了很多情况
假设我们想要排序整型数组:
int cmp(void* x1, void* x2)//整数比较 { return *(int*)x1 - *(int*)x2; }
5.3 对于交换函数的思考
在使用冒泡排序时
我们通常已知待排序的数组的类型
所以能够使用不同的方法来交换不同类型
然而
qsort函数需要满足所有类型的交换
解决方法:
可以把数据一个字节一个字节的交换
任何类型的大小都大于等于一个字节
所以只需要知道数据所占字节数
就能解决这个问题!
5.4 交换函数的实现
void Swap_by_bite(char* s1, char* s2, int width) { for (int i = 0; i < width; i++)//一个字节一个字节的拷贝过去 { char tmp = *s1; *s1 = *s2; *s2 = tmp; s1++; s2++; } }
对代码的解释:
函数参数使用char*是因为
将数据单位化,方便以字节为单位交换
width参数是指数据所占字节大小
5.5 qsort函数所有代码
int cmp(void* x1, void* x2)//整数比较 { return *(int*)x1 - *(int*)x2; } void Swap_by_bite(char* s1, char* s2, int width) { for (int i = 0; i < width; i++)//一个字节一个字节的拷贝过去 { char tmp = *s1; *s1 = *s2; *s2 = tmp; s1++; s2++; } } bubble_sort(void* s, int sz, int width, int (*cmp)(void* x1, void* x2)) { for (int i = 0; i < sz - 1; i++) { for (int j = 0; j < sz - i - 1; j++) { if (cmp((char*)s+j*width,(char*)s+(j+1)*width)>0) { Swap_by_bite((char*)s + j * width, (char*)s + (j + 1) * width, width); } } } }
对代码的解释:
给cmp函数传参:s+j*width和
s+(j+1)*width可以这样理解:
而交换函数传参也是一个意思
并且Swap函数的参数是char*
所以需要我们强制类型转换传入的数据
6. 总结
指针是C语言的一项利器
某些使用C语言编写的项目
使用高阶指针解决问题是家常便饭!
看似这种不断套娃的过程很鸡肋
实际上有一定的用途
🔎 下期预告:自定义类型详解 🔍
