播放swf文件 自动弹出网站,怎么做招聘网站的数据分析,wordpress不显示 头像,做网站如何引流qsort函数的模拟实现 导言一、回调函数二、冒泡排序2.1 冒泡排序实现升序 三、qsort函数3.1 qsort函数的使用3.2 比较函数 四、通过冒泡排序模拟实现qsort函数4.1 任务需求4.2 函数参数4.3 函数定义与声明4.4 函数实现4.4.1 函数主体4.4.2 比较函数4.4.3 元素交换 4.5 my_qsort… qsort函数的模拟实现 导言一、回调函数二、冒泡排序2.1 冒泡排序实现升序 三、qsort函数3.1 qsort函数的使用3.2 比较函数 四、通过冒泡排序模拟实现qsort函数4.1 任务需求4.2 函数参数4.3 函数定义与声明4.4 函数实现4.4.1 函数主体4.4.2 比较函数4.4.3 元素交换 4.5 my_qsort函数测试 五、知识点总结结语 导言
大家好很高兴又和大家见面了 在数组篇章中咱们有介绍过一种排序的方式——冒泡排序。不知道大家还有没有印象如果没印象也没关系等会我们会再简单介绍一下今天我们要介绍的主角是C语言提供的一个进行排序的库函数——qsort。下面我们就开始今天的内容吧
一、回调函数
在介绍qsort函数之前我们需要先了解一个概念——回调函数。
所谓的回调函数就是通过函数指针调用的函数。如下所示
//回调函数
void test1()
{printf(hehe\n);
}
int main()
{void (*p)() test1;p();return 0;
}在这个例子中我们将test1这个函数的地址存放进函数指针p中然后通过函数指针p来调用这个test1函数此时的test1函数就是回调函数
相信冰雪聪明的各位应该一看就会了下面我们再来复习一下冒泡排序
二、冒泡排序
所谓的冒泡排序我们可以简单的理解为就是将一组数通过相邻两个元素直接进行比较从而达到排序的作用如图所示 我们需要将这些气泡从小到大的顺序从上往下排列。 此时我们要完成一趟排序的话我就需要从上往下将这些气泡两两之间进行比较 当发现上面的气泡比下面的大时我们就需要将它们两个换位置在经过两两之间的重复比较与换位后我们就可以在一趟排序中奖最大的气泡放在最下面 也就是说每完成一趟冒泡排序我们就能确定一个气泡的位置最终就能将所有的气泡按从小到大的顺序从上往下排列。 为了帮助大家更好的理解下面我们就来实现一下冒泡排序
2.1 冒泡排序实现升序
//冒泡排序
void Bubble(int* arr, int sz)
{//排序趟数for (int i 0; i sz - 1; i){//每一趟排序次数for (int j 0; j sz - 1 - i; j){if (arr[j] arr[j 1]){int tmp arr[j];arr[j] arr[j 1];arr[j 1] tmp;}}}
}我们来看一下排序的效果 冒泡排序的排序逻辑不难就是两个元素相邻的元素比较直到没有元素需要交换为止 需要比较的总趟数比元素个数少一 每一趟排序的次数要比前一趟少一
C语言为了帮助程序猿提高需要排序时的编程效率它为我们提供了一个库函数——qsort函数
三、qsort函数
qsort函数是C语言程序猿提供的可以直接使用的排序库函数。它是通过快速排序来实现的一个排序函数它的执行效率要高于冒泡排序下面我们通过 MSDN 来看一下这个库函数 (这里我们就不展开讨论什么是快速排序了后面有机会再给大家介绍。) 从qsort函数的介绍中我们可以得到以下的信息 qsort 函数是一个无返回类型的函数接收排序对象的参数是一个无类型的指针型参数函数参数中的比较函数的两个参数也是无类型的指针型的参数qsort函数中的比较函数是一个返回类型为整型的函数我们在排序进行排序时需要告诉函数排序对象的大小以及排序对象的元素所占空间大小 我们继续往下看 通过这里的介绍我们可以得到以下信息 比较函数是用户自己提供的函数有两个无类型指针型的参数 函数的返回值需要按照以下标准 当参数1参数2时返回值0当参数1参数2时返回值0当参数1参数2时返回值0; 通过这个比较函数的返回值我们可以得到一个递增的数组 当我们需要得到一个递减的数组时需要将参数1和参数2进行换位使其满足一下条件 当参数1参数2时返回值0当参数1参数2时返回值0当参数1参数2时返回值0; 从qsort函数的参数类型我们可以得知它可以接收所有类型的数组。我们前面展示的冒泡排序的函数它能接收的只有我们限定好的对应类型的数组这就是qsort函数的强大之处那它具体是如何使用的呢下面我们就来探讨一下
3.1 qsort函数的使用
qsort函数本身需要四个参数排序对象数组、数组大小、数组元素大小和比较函数。下面我们准备两个不同类型的数组一个是int类型一个是char类型为了更好的观察此时我们将这两种数组排序封装成两个函数这样我们只需要在主函数内调用这两个函数就可以了如下所示
//qsort排序整型数组
void test2()
{int arr[] { 9,8,7,6,5,4,3,2,1,0 };//通过sizeof计算数组大小int sz sizeof(arr) / sizeof(arr[0]);printf(排序前数组元素顺序:);print(arr, sz);//通过qsort实现升序排列qsort(arr, sz, sizeof(arr[0]), cmp_int);printf(排序后数组元素顺序:);print(arr, sz);}
//qsort排序字符型数组
void test3()
{char ch[] { 9,8,7,6,5,4,3,2,1,0 };//通过sizeof计算数组大小int sz sizeof(ch) / sizeof(ch[0]);printf(排序前数组元素顺序:);print(ch, sz);//通过qsort实现升序排列qsort(ch, sz, sizeof(ch[0]), cmp_char);printf(排序后数组元素顺序:);print(ch, sz);}现在我们要思考一下对于这两个数组我们应该如何进行元素间的比较
3.2 比较函数
我们再来看一下这个比较函数的介绍
int(__cdecl* compare)(const void* elem1, const void* elem2);
//int——函数返回类型为整型
//__cdecl——函数调用方法所有参数从右到左依次入栈
//const void*——参数类型为不可修改的无类型指针这里我们简答介绍一下__cdecl __cdecl 是C Declaration的缩写declaration声明表示C语言默认的函数调用方法所有参数从右到左依次入栈这些参数由调用者清除称为手动清栈。被调用函数不会要求调用者传递多少参数调用者传递过多或者过少的参数甚至完全不同的参数都不会产生编译阶段的错误。 这个我们简单了解一下就行不需要去深究我们现在的重点是看其它的部分如果我们将__cdecl省略的话我们就能得到int(*compare)(const void* elem1, const void* elem2)。
这个代码有没有一种熟悉的感觉如果我们将这个代码格式化书写的话它是不是就应该表示为
type(*point_name)(parameter_type,parameter_type);
//type——函数返回类型
//*——指针标志
//point_name——指针变量名
//parameter_type——参数类型这个格式正是函数指针的创建格式也就是说这里的compare是一个函数指针而且这个函数的参数类型还是不可修改的无类型指针。
下面我们根据这里的比较函数的格式来定义一下整型数组的比较函数与字符数组的比较函数
//比较函数——整型数组
int cmp_int(const void* p1, const void* p2);
//比较函数——字符数组
int cmp_char(const void* p1, const void* p2);根据前面的介绍我们只需要让这个比较函数的两个参数进行比较后返回对应的整型值就可以了。
对于整型来说我们不难想象两个整数要比较大小后返回一个整型值我们可以通过作差来实现但是此时的参数为void*类型我们不能对这个类型的指针进行解引用那该怎么办呢 强制类型转换——我们可以先将这个指针进行强制类型转换成int*然后再对指针进行解引用最后完成两个整型值作差并将结果返回给函数就可以了。因此我们可以编写代码
//比较函数——整型数组
int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}同理对于字符来说它们要比较大小的话是根据对应的ASCII码值来进行比较所以同样也是整型类型的比较因此我们也是可以通过将两个字符进行作差并返回差值给比较函数
//比较函数——字符数组
int cmp_char(const void* p1, const void* p2)
{return *(char*)p1 - *(char*)p2;
}下面我们就来测试一下 可以看到此时我们通过qsort函数实现了对字符数组和整型数组的排序。下面我们需要思考一下我们可不可以通过冒泡排序来实现qsort函数呢下面我们来一步一步的进行探讨
四、通过冒泡排序模拟实现qsort函数
4.1 任务需求
我们现在需要使用冒泡排序的方式来编写一个可以对任一类型的数组进行排序的my_qsort函数
4.2 函数参数
既然是模拟的qsort函数所以我们可以按照qsort函数的参数来进行传参如下所示
void test4()
{int arr[] { 5,4,3,2,8,6,1,9,7,0 };int sz sizeof(arr) / sizeof(arr[0]);print_int(arr, sz);my_qsort(arr, sz, sizeof(arr[0]), cmp_int);print_int(arr, sz);
}我们依然传入四个参数——排序对象数组大小元素所占空间大小以及一个排序函数指针
4.3 函数定义与声明
为了简化编写这里我们直接将函数定义在test4这个函数的上方参数的类型也是仿造qsort进行定义如下所示
//模拟实现qsort函数
void my_qsort(void* base, int sz, int w, int(*cmp_int)(const void*, const void*))
{}因为我们此时测试的是整型数组所以对于这个比较函数的编写我们也是根据qsort函数的比较函数的要求进行编写如下所示
//比较函数
int cmp_int(const void* p1, const void* p2)
{//升序排列return *(int*)p1 - *(int*)p2;//降序排列return *(int*)p2 - *(int*)p1;
}在完成了这两步操作后接下来我们就需要开始对my_qsort这个函数进行实现了
4.4 函数实现
4.4.1 函数主体
既然我们这里是通过冒泡排序实现的qsort那冒泡排序的主体就不能掉如下所示
//模拟实现qsort函数
void my_qsort(void* base, int sz, int w, int(*cmp_int)(const void*, const void*))
{//排序总次数for (int i 0; i sz - 1; i){//一次排序所需次数for (int j 0; j sz - 1 - i; j){}}
}我们现在要思考一下我们应该如何对不同类型的对象的元素进行判断从而决定是否进行元素之间的交换其实这里qsort已经在参数中给了我们答案——比较函数。
4.4.2 比较函数
当要进行升序排列时比较函数的返回值有三种情况
当参数1参数2时返回值0当参数1参数2时返回值0当参数1参数2时返回值0
当要进行降序排列时比较函数的返回值有三种情况
当参数1参数2时返回值0当参数1参数2时返回值0当参数1参数2时返回值0
实际上不管是要进行升序排列还是降序排列当返回值大于0时我们才需要对数组的元素进行交换因此我们可以将比较函数的返回值作为判断依据如下所示
//模拟实现qsort函数
void my_qsort(void* base, int sz, int w, int(*cmp_int)(const void*, const void*))
{//排序总次数for (int i 0; i sz - 1; i){//一次排序所需次数for (int j 0; j sz - 1 - i; j){if (cmp_int((base j), (base (j 1))) 0){}}}
}那是不是这样就完了呢并不是如果像这样编写是不对的现在我们需要注意一个点
base是void*类型的指针我们不能对这个类型的指针进行解引用以及加减整数等操作
所以我们在进行加减整数时要先将它进行强制类型转换但是我们要转换成什么类型呢
我们知道对于不同类型的元素所占内存空间大小是不相同的但是它们都有一个共同点
不同类型元素所占空间大小为字符类型的元素所占空间大小的整数倍
对于不同类型的指针来说它们在进行加减整数时它们也有一个共同点
指针变化的大小为对应类型所占空间大小的整数倍
根据这两点我们来设想一下如果我们将其转换成char*类型的指针那我们在进行加减整数时指针变化的大小就是对应的整数因为char所占内存空间大小为1个字节。
那也就是说如果我要用char*的指针完成整型的加减整数因为int所占空间大小为char的四倍是不是就相当于我需要加减整数的4倍。因此我们就可以将代码修改一下
//模拟实现qsort函数
void my_qsort(void* base, int sz, int w, int(*cmp_int)(const void*, const void*))
{//排序总次数for (int i 0; i sz - 1; i){//一次排序所需次数for (int j 0; j sz - 1 - i; j){if (cmp_int(((char*)base j * w), ((char*)base (j 1) * w)) 0){}}}
}现在简单的部分我们已经完成了剩下的就是最难的部分——实现任一类型数组的元素之间的交换。
4.4.3 元素交换
对于char*的指针来说它一次解引用访问的空间大小只有一个字节根据前面的介绍 如果我要访问一个整型元素那我是不是只需要通过char*的指针访问4次就可以了 如果有一个占据7个字节空间大小的元素那我是不是也只需要通过char*的指针访问7次就可以了。 所以我们要进行元素交换的话也是可以通过char*的指针来实现的。代码如下
//模拟实现qsort函数
void my_qsort(void* base, int sz, int w, int(*cmp_int)(const void*, const void*))
{//排序总次数for (int i 0; i sz - 1; i){//一次排序所需次数for (int j 0; j sz - 1 - i; j){if (cmp_int(((char*)base j * w), ((char*)base (j 1) * w)) 0){//将元素地址存入char*的指针中char* p1 (char*)base j * w;char* p2 (char*)base (j 1) * w;//通过char*指针访问元素for (int k 0; k w; k){char tmp *p1;*p1 *p2;*p2 tmp;p1;p2;}}}}
}现在咱们的my_qsort函数已经编写完了它现在到底能不能实现交换不同类型的数组呢下面我们就来测试一下
4.5 my_qsort函数测试
为了有更明显的效果这里我们测试三个类型的数组——整型数组、字符数组和结构体数组 可以看到此时我们成功的对这三种类型的数组进行了排序。
五、知识点总结
今天介绍的内容是一个综合性很强的内容我们在模拟实现的过程中有用到指针中的以下知识点
指针类型的意义一维数组传参void*类型的指针函数指针回调函数——比较函数的函数指针调用的比较函数就是回调函数指针±整数
在编写的过程中可能没有什么感觉但是现在回顾一下才会发现原来要模拟qsort函数仅仅指针这个篇章的内容就需要这么多的知识储备所以还是得好好学习提升自己的知识储备才行啊。
结语
到这里咱们今天的内容就全部介绍完了今天我们详细介绍了qsort函数以及使用冒泡排序模拟实现qsort函数最后对这个篇章的知识点做了一个总结。
希望这个篇章的内容能帮助大家更好的理解指针的相关知识点及其使用。感谢大家的翻阅咱们下一篇再见
