目录
一、qsort函数原型
二、compar参数
三、各种类型的qsort排序
1. int 数组排序
2. 结构体排序
3. 字符串指针数组排序
4. 字符串二维数组排序
四、回调函数
1. 什么是回调函数
2. 为什么要用回调函数?
3. 怎么使用回调函数?
4.下面是一个四则运算的简单回调函数例子:
五、qsort函数的模拟实现
一、qsort函数原型
void qsort( void *base,size_t nmemb,size_t size,int (*compar)(const void *, const void *));
头文件:<stdlib.h> 函数功能:qsort()函数的功能是对数组进行排序,数组有nmemb个元素,每个元素大小为size。
参数base - base指向数组的起始地址,通常该位置传入的是一个数组名
参数nmemb - nmemb表示该数组的元素个数
参数size - size表示该数组中每个元素的大小(字节数)
参数(*compar)(const void *, const void *)
- 此为指向比较函数的函数指针,决定了排序的顺序。
函数返回值:无
注意:如果两个元素的值是相同的,那么它们的前后顺序是不确定的。也就是说qsort()是一个不稳定的排序算法。
二、compar参数
compar参数是qsort函数排序的核心内容,它指向一个比较两个元素的函数,注意两个形参必须是const void *
型,同时在调用compar 函数(compar实质为函数指针,这里称它所指向的函数也为compar)时,传入的实参也必须转换成const void *
型。在compar函数内部会将const void *
型转换成实际类型,见下文。
int compar(const void *p1, const void *p2);
如果compar返回值小于0(< 0),那么p1所指向元素会被排在p2所指向元素的前面,如果compar返回值等于0(= 0),那么p1所指向元素与p2所指向元素的顺序不确定,如果compar返回值大于0(> 0),那么p1所指向元素会被排在p2所指向元素的后面。因此,如果想让qsort()进行从小到大(升序)排序,那么一个通用的compar函数可以写成这样:
int compare (const void * a, const void * b){if ( *(MyType*)a < *(MyType*)b ) return -1;if ( *(MyType*)a == *(MyType*)b ) return 0;if ( *(MyType*)a > *(MyType*)b ) return 1;}
注意:你要将MyType换成实际数组元素的类型。 或者
//升序排序
int compare(const void* a, const void* b)
{return (*(int*)a - *(int*)b);
}
//降序排列
int compare(const void* a, const void* b)
{return (*(int*)b - *(int*)a);
}
三、各种类型的qsort排序
1. int 数组排序
#include <stdio.h>
#include <stdlib.h> int values[] = { 40, 10, 100, 90, 20, 25 };int compare(const void* a, const void* b)
{return (*(int*)a - *(int*)b);
}int main()
{int n;qsort(values, sizeof(values) / sizeof(values[0]), sizeof(int), compare);for (n = 0; n < sizeof(values) / sizeof(values[0]); n++)printf("%d ", values[n]);return 0;
}
2. 结构体排序
#include <stdio.h>
#include<stdlib.h>
// void qsort(void* base, size_t num, size_t size, int(*compare)(const void*, const void*))typedef struct
{char name[30]; // 学生姓名int Chinese; // 语文成绩int Math; // 数学成绩 int English; // 英语成绩
}st;
int cmp(const void* a, const void* b)
{st* pa = (st*)a;st* pb = (st*)b;int num1 = pa->Chinese + pa->English + pa->Math;int num2 = pb->Chinese + pb->English + pb->Math;//return (int)num1 - num2; // 从小到大,return (int)num2 - num1; // 从大到小
}
int main(void)
{st students[7] = {{"周",97,68,45},{"吴",100,32,88},{"郑",78,88,78},{"王",87,90,89},{"赵",87,77,66},{"钱",59,68,98},{"孙",62,73,89}};qsort(students, 7, sizeof(st), cmp); // 注意区别 students 与 stfor (int i = 0; i < 7; i++){printf("%s%4d%4d%4d\t", students[i].name, students[i].Chinese, students[i].Math, students[i].English);printf("总分:%d\n", students[i].Chinese + students[i].English + students[i].Math);}system("pause");return 0;
}
3. 字符串指针数组排序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>int compare(const void* arg1, const void* arg2);int main(int argc, char** argv)
{int i;char* arr[5] = { "i", "love", "c", "programming", "language" };qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(char*), compare);for (i = 0; i < 5; i++) {printf("%s ", arr[i]);}printf("\n");}int compare(const void* arg1, const void* arg2) {char* a = *(char**)arg1;char* b = *(char**)arg2;int result = strcmp(a, b);if (result > 0) {return 1;}else if (result < 0) {return -1;}else {return 0;}
}
那么我们向qsort传入arr之后,qsort将arr理解为指向数组中第一个元素的指针,所以形参表中,arg1和arg2其实是指向“指向常量字符串的指针”的指针,是char**
。而我们需要传给strcmp这个字符串比较函数的,是“指向字符串的指针”,是char*
,所以我们将void*
转换为char**
,然后解引用,得到char*
,赋予a和b。接下来使用strcmp对a和b进行比较。(数组名本身算一层指针,而里面的内容又是一层指针,数组存放的是指向字符串的地址)
4. 字符串二维数组排序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>int compare(const void* arg1, const void* arg2);int main(int argc, char** argv)
{int i;char arr[5][16] = { "i", "love", "c", "programming", "language" };qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(arr[0]), compare);printf("%s\n", arr[0]);for (i = 0; i < 5; i++) {printf("%s ", arr[i]);}printf("\n");
}int compare(const void* arg1, const void* arg2)
{char* a = (char*)arg1;char* b = (char*)arg2;int result = strcmp(a, b);if (result > 0) {return 1;}else if (result < 0) {return -1;}else {return 0;}
}
这里对二维数组进行排序,其实是对二维数组的第二维中存放的字符串进行排序。所以qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), compare);
对qsort函数的调用中,第二个参数是待排元素的个数(5个),第三个参数是待排元素的大小(16)。
我们将arr传入qsort函数,qsort函数将arr理解为指向数组第一个元素的指针,arr的第一个元素是arr[0][0]
,所以参数arg1和arg2指的是指向"a[i][0]
"的指针,我们知道,a[i][0]
是字符,就是char,所以arg1和arg2指的是char *
。我们将void*
转换为char*
,赋予a和b,调用strcmp函数对a和b进行比较。
四、回调函数
1. 什么是回调函数
我们先来看看百度百科是如何定义回调函数的:
回调函数就是一个通过函数指针调用的函数。如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,我们就说这是回调函数。回调函数不是由该函数的实现方直接调用,而是在特定的事件或条件发生时由另外的一方调用的,用于对该事件或条件进行响应。
这段话比较长,也比较绕口。下面我通过一幅图来说明什么是回调:
假设我们要使用一个排序函数来对数组进行排序,那么在主程序(Main program)中,我们先通过库,选择一个库排序函数(Library function)。但排序算法有很多,有冒泡排序,选择排序,快速排序,归并排序。同时,我们也可能需要对特殊的对象进行排序,比如特定的结构体等。库函数会根据我们的需要选择一种排序算法,然后调用实现该算法的函数来完成排序工作。这个被调用的排序函数就是回调函数(Callback function)。
结合这幅图和上面对回调函数的解释,我们可以发现,要实现回调函数,最关键的一点就是要将函数的指针传递给一个函数(上图中是库函数),然后这个函数就可以通过这个指针来调用回调函数了。注意,回调函数并不是C语言特有的,几乎任何语言都有回调函数。在C语言中,我们通过使用函数指针来实现回调函数。
我的理解是:把一段可执行的代码像参数传递那样传给其他代码,而这段代码会在某个时刻被调用执行,这就叫做回调。
如果代码立即被执行就称为同步回调
,如果过后再执行,则称之为异步回调
。
回调函数
就是一个通过函数指针调用的函数。如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,我们就说这是回调函数。
回调函数不是由该函数的实现方直接调用,而是在特定的事件或条件发生时由另外的一方调用的,用于对该事件或条件进行响应。
2. 为什么要用回调函数?
因为可以把调用者与被调用者分开,所以调用者不关心谁是被调用者。它只需知道存在一个具有特定原型和限制条件的被调用函数。
简而言之,回调函数就是允许用户把需要调用的方法的指针作为参数传递给一个函数,以便该函数在处理相似事件的时候可以灵活的使用不同的方法。
int Callback() ///< 回调函数
{// TODOreturn 0;
}
int main() ///< 主函数
{// TODOLibrary(Callback); ///< 库函数通过函数指针进行回调// TODOreturn 0;
}
回调似乎只是函数间的调用,和普通函数调用没啥区别。
但仔细看,可以发现两者之间的一个关键的不同:在回调中,主程序把回调函数像参数一样传入库函数。
这样一来,只要我们改变传进库函数的参数,就可以实现不同的功能,这样有没有觉得很灵活?并且当库函数很复杂或者不可见的时候利用回调函数就显得十分优秀。
3. 怎么使用回调函数?
#include <stdio.h>
int Callback_1(int a) ///< 回调函数1
{printf("Hello, this is Callback_1: a = %d \n", a);return 0;
}int Callback_2(int b) ///< 回调函数2
{printf("Hello, this is Callback_2: b = %d \n", b);return 0;
}int Callback_3(int c) ///< 回调函数3
{printf("Hello, this is Callback_3: c = %d \n", c);return 0;
}int Handle(int x, int (*Callback)(int)) ///< 注意这里用到的函数指针定义
{Callback(x);
}int main()
{Handle(4, Callback_1);Handle(5, Callback_2);Handle(6, Callback_3);return 0;
}
看看结果:
如上述代码:可以看到,Handle()函数里面的参数是一个指针,在main()函数里调用Handle()函数的时候,给它传入了函数Callback_1() / Callback_2() / Callback_3()的函数名,这时候的函数名就是对应函数的指针,也就是说,回调函数其实就是函数指针的一种用法。
4.下面是一个四则运算的简单回调函数例子:
#include <stdio.h>
#include <stdlib.h>/***************************************** 函数指针结构体***************************************/
typedef struct _OP {float (*p_add)(float, float);float (*p_sub)(float, float);float (*p_mul)(float, float);float (*p_div)(float, float);
} OP;/***************************************** 加减乘除函数***************************************/
float ADD(float a, float b)
{return a + b;
}float SUB(float a, float b)
{return a - b;
}float MUL(float a, float b)
{return a * b;
}float DIV(float a, float b)
{return a / b;
}/***************************************** 初始化函数指针***************************************/
void init_op(OP* op)
{op->p_add = ADD;op->p_sub = SUB;op->p_mul = &MUL;op->p_div = &DIV;
}/***************************************** 库函数***************************************/
float add_sub_mul_div(float a, float b, float (*op_func)(float, float))
{return (*op_func)(a, b);
}int main(int argc, char* argv[])
{OP* op = (OP*)malloc(sizeof(OP));init_op(op);/* 直接使用函数指针调用函数 */printf("ADD = %f, SUB = %f, MUL = %f, DIV = %f\n", (op->p_add)(1.3, 2.2), (*op->p_sub)(1.3, 2.2),(op->p_mul)(1.3, 2.2), (*op->p_div)(1.3, 2.2));/* 调用回调函数 */printf("ADD = %f, SUB = %f, MUL = %f, DIV = %f\n",add_sub_mul_div(1.3, 2.2, ADD),add_sub_mul_div(1.3, 2.2, SUB),add_sub_mul_div(1.3, 2.2, MUL),add_sub_mul_div(1.3, 2.2, DIV));return 0;
}
五、qsort函数的模拟实现
使⽤回调函数,模拟实现qsort(采⽤冒泡的⽅式)。
注意:这里第⼀次使用 void* 的指针,讲解 void* 的作⽤。
#include <stdio.h>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;for (i = 0; i < width; i++) {char 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 (arr[j] > arr[j + 1])if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){/*int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;*///交换Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}void print_arr(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}void test()
{//设计和实现bubble_sort2(),这个函数能够排序任意类型的数据int arr[] = { 3,1,5,7,9,2,4,0,8,6 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);print_arr(arr, sz);
}int main()
{test();return 0;
}