距离上次更新本文已经过去了 729 天，文章部分内容可能已经过时，请注意甄别

[TOC]

嘟嘟嘟，指针进阶的公交车到终点站🚏啦！

这一站我们将学习回调函数、qsort 的使用以及模拟实现

1. 回调函数

定义：

回调函数就是一个通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一 个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。回调函数不是由该 函数的实现方直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或 条件进行响应。

在上篇博客函数指针数组里，提到了一个计算器的代码

在这里就能用到我们的回调函数，通过一个新的 calc 函数来调用计算函数，同样达到了避免 switch/case 语句重复的目的

image-20220124174511858

不过今天我们的学习重点的内容不在这里，而是一个全新的函数：qsort

2.qsort 函数

qsort 函数又称 快速排序函数

2.1void * 指针

c
1
void* p = &a;
  • void* 是一种无类型的指针，无具体类型的指针
  • void* 的指针变量可以存放任意类型的地址
  • void* 的指针不能直接进行解引用操作
  • void* 的指针不能直接进行加减整数

了解了这个之后，我们再来看看 qsort 函数的定义

2.2qsort 函数定义

image-20220124192610616

c
1
2
void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));

这些参数分别代表什么意义呢？

  • void*base 是待排序数据的起始地址

  • size_t num 是待排序数据的个数

  • size_t size 是待排序数据中每个数据的大小

    siez_t 是专为 sizeof 函数的返回值设计的

    它是一个无符号整型

image-20220124192745459

  • int (*compar)(const void*,const void*) 是一个函数指针

    该函数的参数为 (const void*,const void*)，返回值为 int

    在 qsort 的应用中，需要我们自己来编写这样一个 compar 函数，来判断待排序数据谁大谁小

    qsort 库函数对 compar 函数做出了如下规定：

    • p1>p2 时 返回 > 0 的数
    • p1=p2 时 返回 0
    • p1<p2 时 返回 < 0 的数

    image-20220124193234638

为什么比较函数用的 void * 类型的指针？

因为 qsort 函数并不知道你需要排序什么类型的数据，但是作为使用者，我们知道待排序的数据类型以及如何比较待排序的数据，这时候就可以将 void * 指针强制类型转换，变为所需要的指针！

2.3 利用 qsort 函数来排序 int/char

首先我们建立一个待排序的整型数组，依照 qsort 函数的定义，将参数填入该函数

c
1
2
3
4
5
6
7
8
9
int main()
{
	int arr[10] = { 3,4,7,9,0,1,2,5,8,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int* ptr = arr;//此处可以直接用arr来代替
	qsort(ptr, sz, sizeof(arr[0]), cmp_int);
    
    return 0;
}

接着，我们需要来编写这个 cmp_int 函数，用于判断两个整型的大小

然后把这个函数名写入 qsort

c
1
2
3
4
5
//编写一个函数比较整型
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}

运行，可以看到数据已经按照升序重新排序了！

如果你想降序排序，只需要将比较函数参数里的 e1 和 e2 对调位置

image-20220124194040462

再来试试排序 char 字符类型吧！

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//比较字符
int cmp_char(const void* e1, const void* e2)
{
	char a = *(char*)e1;
	char b = *(char*)e2;
	if (a == b)
		return 0;
	else if (a > b)
		return 1;
	else
		return -1;
}

int main()
{
	char arr1[5] = { 'd','i','a','c','k'};
	int sz1 = sizeof(arr1) / sizeof(arr1[0]);
	int* pc = arr1;
	qsort(pc, sz1, sizeof(arr1[0]), cmp_char);

	for(int i = 0; i < sz1; i++)
	{
		printf("%c ", arr1[i]);
	}
	printf("\n");
	return 0;
}

2.4 用 qsort 排序结构体

定义一个结构体，内容分别代表姓名、年龄、成绩

c
1
2
3
4
5
6
struct Stu
{
	char name[20];
	int age;
	float score;
};

该结构体有 char、int、float 三种类型的数据，需要我们写三种对应的排序函数

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//排序成绩
int cmp_stu_by_socre(const void* e1, const void* e2)
{
	if (((struct Stu*)e1)->score > ((struct Stu*)e2)->score)
	{
		return 1;
	}
	else if (((struct Stu*)e1)->score < ((struct Stu*)e2)->score)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}
//按年龄排序
int cmp_stu_by_age(const void* e1, const void* e2)
{
	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
//按名字排序
int cmp_stu_by_name(const void* e1, const void* e2)
{   //用strcmp函数比较字符串
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

再写一个函数来打印结构体变量

c
1
2
3
4
5
6
7
8
9
void print_stu(struct Stu arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s %d %.2f\n", arr[i].name, arr[i].age, arr[i].score);
	}
	printf("\n");
}

最后在主函数里定义结构体类型并写入 qsort 函数

c
1
2
3
4
5
6
7
8
9
10
int main()
{
	struct Stu arr[] = { {"zhangsan",20,87.5f},{"lisi",22,99.0f},{"wangwu", 10, 68.5f},{"niuyeye",30,95.0f} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);

	print_stu(arr,sz);

	return 0;
}

可以看到，我们的数据已经按照姓名排序了！

image-20220124195049760

3. 模拟实现 qsort 函数

那么，qsort 函数的原理是什么呢？

之前我们写过用于排序整型的冒泡排序

其原理是比较数组内的 a 元素以及 a 的下一位元素，如果 a 大于 a+1 的元素，则将它们互换位置

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bubble_sort(int arr[], int sz)//形参arr本质是指针
{
	//确定趟数
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		//一趟冒泡排序
		int j = 0;
		for (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;
			}
		}
	}
}

有没有办法将冒泡排序给改写成通用的排序函数呢？

思考：

  • 冒泡排序的时候，使用是 int 类型，int 类型是 4 个字节，无法排序比 4 个字节小的数据类型
  • 结构体类型的大小不一定是 4 的整数倍，也无法用 int 来排序
  • char 类型是 1 个字节，能否通过 char 类型来更改所有类型？

答案当然是肯定的！

在之前的指针学习里，我们了解到，尽管 char* 和 int* 类型的指针都占 4 个字节，但是 char * 类型只能访问 1 个字节的数据。

我们可以利用 char* 指针的这个特点，对数据进行一个字节一个字节的交换，交换 4 次不就能交换完一个 int 类型了吗？同理也能通过 char* 的多次访问，交换其他类型的数据！

image-20220124200912793

既然是模拟实现 qsort 函数，那函数的参数应该和 qsort 相同

直接把 qsort 函数改成 my_qsort，开整！

image-20220124201240991

利用冒泡排序的基本框架，我们可以写出以下的代码

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//模拟实现qsort
void my_qsort(void* base, int sz,int width, int(*cmp)(const void* e1, const void* e2))
{
	for (int i = 0; i < sz - 1; i++)
	{
		for (int j = 0; j < sz - i - 1; j++)
		{
			if (cmp((char*)base + j * width , (char*)base + (j + 1) * width)>0)
			{
				my_swap((char*)base + j * width, (char*)base + (j+1) * width ,width);
			}
		}
	}
}

你可能对 if 里面的语句感到很懵，别急，看图！

cmp 就是一个回调函数，利用函数指针来调用比较函数

image-20220124201419541

再来写一个 swap 函数，实现字节的交换

c
1
2
3
4
5
6
7
8
9
10
11
12
13
//用char类型的指针来一个一个地访问
void my_swap(char* e1, char* e2,int sz)
{    
    //sz是待排序数据的宽度:width
	for (int k = 0; k < sz; k++)
	{
		char tmp = *e1;
		*e1 = *e2;
		*e2 = tmp;
		e1++;
		e2++;
	}
}

测试一下，成功按照成绩来排序！

image-20220124201625996

结语

指针进阶的行程到这里就圆满结束啦！是不是感觉收获满满呢？

学有余力的朋友们可以看看这一类指针笔试题👉点我

到站，下车！🚍