【C语言】指针进阶终点站,回调函数和qsort
慕雪年华

[TOC]

嘟嘟嘟,指针进阶的公交车到终点站🚏啦!

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

1.回调函数

定义:

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

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

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

image

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


2.qsort函数

qsort函数又称 快速排序函数

2.1void*指针

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

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

2.2qsort函数定义

image

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

  • 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

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

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


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

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

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

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

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

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

image

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

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;
}

image

2.4用qsort排序结构体

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

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

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

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);
}

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

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函数

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


3.模拟实现qsort函数

那么,qsort函数的原理是什么呢?

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

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

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

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

直接把qsort函数改成my_qsort,开整!

image

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

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

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

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

结语

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

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

到站,下车!🚍