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

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;
	else
		return 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();
}

按年龄排序的运行结果：

到这里今天的内容就结束了
谢谢观看！
这篇内容是我在qsort函数上的总结，如果你觉得有用，不妨点个赞收藏一下让更多人看到，非常欢迎在评论区交流指正，一起进步~感谢读到这里的每一位朋友！
“技术的路上，一个人走可能会很慢，但一群人同行就会更有力量！”