【C语言篇】深入理解指针4（模拟实现qsort函数）

2024-10-09 19:19:10 浏览数 (1)

回调函数是什么

回调函数就是⼀个通过函数指针调⽤的函数。

如果你把函数的指针（地址）作为参数传递给另⼀个函数，当这个指针被⽤来调⽤其所指向的函数时，被调⽤的函数就是回调函数。

回调函数不是由该函数的实现⽅直接调⽤，⽽是在特定的事件或条件发⽣时由另外的⼀⽅调⽤的，⽤于对该事件或条件进⾏响应。

回想一下我们在设计一个计算器的时候：

需要写加减乘除函数如下：

代码语言：javascript复制
int add(int a, int b)
{
    return a   b;
}
int sub(int a, int b)
{
    return a - b;
}
int mul(int a, int b)
{
    return a * b;
}
int div(int a, int b)
{
    return a / b;
}

在使用回调函数改造前：

  • 可以发现存在很多冗余的地方，在每个分支都需要书写相同的scanf和printf语句
代码语言：javascript复制
int main()
{
    int x, y;
    int input = 1;
    int ret = 0;
    do
    {       
        printf("*********************n");
        printf(" 1:add 2:sub n");
        printf(" 3:mul 4:div n");
        printf("*********************n");
        printf("请选择：");
        scanf("%d", &input);
        switch (input)
        {
            case 1:
                printf("输⼊操作数：");
                scanf("%d %d", &x, &y);
                ret = add(x, y);
                printf("ret = %dn", ret);
                break;
            case 2:
                printf("输⼊操作数：");
                scanf("%d %d", &x, &y);
                ret = sub(x, y);
                printf("ret = %dn",ret);
                break;
            case 3:
                printf("输⼊操作数：");
                scanf("%d %d", &x, &y);
                ret = mul(x, y);
                printf("ret = %dn", ret);
                break;
            case 4:
                printf("输⼊操作数：");
                scanf("%d %d", &x, &y);
                ret = div(x, y);
                printf("ret = %dn", ret);
                break;
            case 0:
                printf("退出程序n");
                break;
            default:
                printf("选择错误n");
                break;
        }
    } while (input);
    return 0;
}

我们发现调用的函数都是int (int,int)类型的，我们可以把调⽤的函数的地址以参数的形式传递过去，使⽤这样类型的函数指针接收，函数指针指向什么函数就调⽤什么函数，这⾥其实使⽤的就是回调函数的功能。

代码语言：javascript复制
void calc(int(*pf)(int, int))
{
    int ret = 0;
    int x, y;
    printf("输⼊操作数：");
    scanf("%d %d", &x, &y);
    ret = pf(x, y);
    printf("ret = %dn", ret);
}

使用回调函数改造后：

代码语言：javascript复制
int main()
{
    int x, y;
    int input = 1;
    int ret = 0;
    do
    {       
        printf("*********************n");
        printf(" 1:add 2:sub n");
        printf(" 3:mul 4:div n");
        printf("*********************n");
        printf("请选择：");
        scanf("%d", &input);
        switch(input)
        {
            case 1:
                calc(add);
                break;
            case 2:
                calc(sub);
                break;
            case 3:
                calc(mul);
                break;
            case 4:
                calc(div);
                break;
            case 0:
                printf("退出程序n");
                break;
            default:
                printf("选择错误n");
                break;
        }
    } while (input);
    return 0;
}

注意区分这和我们在【C语言篇】深入理解指针3（附转移表源码）中实现的转移表，这里使用的是回调函数，但在转移表中我们使用的是函数指针数组

qsort函数介绍和使用举例

qsort函数介绍

代码语言：javascript复制
void qsort(void* base, //指向待排序数组的第一个元素的指针
           size_t num, //base指向数组中的元素个数
           size_t size,//base指向的数组中一个元素的大小，单位是字节
           int (*cmp)(const void*, const void*) //函数指针 - 传递函数的地址    
          );
  • 头文件为stdlib.h
  • 参数四个介绍如上
  • 对最后一个参数特别介绍一下：
    • 函数指针，指向的函数是用来比较待排序数组的元素大小的
    • 由使用qsort函数的用户来实现
    • 如果p1指向的元素小于p2，则返回小于0的数字
    • 如果二者相等，则返回0
    • 如果p1指向的元素大于p2，则返回大于0的数字
  • qsort函数默认是排升序，如果想排降序，则在compare函数里将上述规则反一下即可，即当p1指向的元素小于p2时返回大于0的数字

qsort函数排序整型数据

代码语言：javascript复制
#include <stdio.h>
#include <stdlib.h>
    //qosrt函数的使⽤者得实现⼀个⽐较函数
    int int_cmp(const void * p1, const void * p2)
{
    return (*( int *)p1 - *(int *) p2);
}
int main()
{
    int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
    int i = 0;
    qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof (int), int_cmp);
    for (i = 0; i< sizeof(arr) / sizeof(arr[0]); i  )
    {
        printf( "%d ", arr[i]);
    }
    printf("n");
    return 0;
}

使用qsort排序结构数据

代码语言：javascript复制
struct Stu //学⽣
{
    char name[20];//名字
    int age;//年龄
};
//假设按照年龄来⽐较
int cmp_stu_by_age(const void* e1, const void* e2)
{
    return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
//strcmp - 是库函数，是专⻔⽤来⽐较两个字符串的⼤⼩的
//假设按照名字来⽐较
int cmp_stu_by_name(const void* e1, const void* e2)
{
    return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
//按照年龄来排序
void test2()
{
    struct Stu s[] = { {"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15} };
    int sz = sizeof(s) / sizeof(s[0]);
    qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}
//按照名字来排序
void test3()
{
    struct Stu s[] = { {"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15} };
    int sz = sizeof(s) / sizeof(s[0]);
    qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
}
int main()
{
    test2();
    test3();
    return 0;
}

qsort函数的模拟实现

使用回调函数，模拟实现qsort

注意：

  • qsost底层采用的是快速排序的方法，在这里我们使用更简单的冒泡排序的排序算法来模拟实现qsort函数，对快排想要了解更多的读者可以看看【初阶数据结构篇】冒泡排序和快速排序（中篇）
  • 这里使用void*的指针，以实现泛型编程

在实现前我们先温故一下冒泡排序

  • 总共n个数据，要排n-1趟
  • 第i（i从0开始取）趟要比较n-1-i次
代码语言：javascript复制
void bubble_sort(int arr[], int sz)
{
    //趟数
    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])
            {
                int tmp = arr[j];
                arr[j] = arr[j   1];
                arr[j   1] = tmp;
            }
        }
    }
}
void print_arr(int arr[], int sz)
{
    int i = 0;
    for (i = 0; i < sz; i  )
    {
        printf("%d ", arr[i]);
    }
}

int main()
{
    int arr[] = { 3,1,7,9,4,2,6,5,8,0 };
    //排序 - 升序
    int sz = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, sz);
    print_arr(arr, sz);
    return 0;
}

冒泡排序只需要两个参数，待排序数组和数组元素个数

我们要实现的qsort是可以针对任何数据进行排序，那想一下我们知道用户使用这个函数的时候是拿来排序什么数据吗？显然是不知道的，所以在内部实现时，我们需要更改什么呢？分析如下：

  • 首先是趟数和一趟之内的比较次数，这是冒泡算法，无论什么数据都不需要改变整体的大框架

重点在于以下两点：

  1. 比较的方式
  • 由于不知道用户排序的数据类型，传过来的数组首元素地址我们必须使用void*指针接收，是不能进行解引用的，且数据类型是不能传参的，那我们该怎么找到相邻元素比较呢？

于是我们在参数中添加了数组元素的大小（即宽度，一个元素占几个字节，这是用户可以传参的），这样就能找到相邻元素了

代码语言：javascript复制
(char*)base   j * width
(char*)base   (j   1) * width)

这样在内层循环中就能依次找到两个相邻元素了

接下来就是如何比较，由于我们不知道用户排序什么数据，所以没办法实现两个数据的比较，例如整数可以直接使用关系操作符，而字符串需要strcmp函数等等，于是我们把比较两个数据大小的函数交给用户去实现，所以在参数中使用了一个函数指针

这样比较两数的方式就更改完毕了

代码语言：javascript复制
if (cmp((char*)base   j * width, (char*)base   (j   1) * width) > 0)
  • 这里我们默认还是qsort的比较规则，用户实现compare函数时如果遵守：当第一个元素大于第二个元素时，就返回大于0的数字，此时我们交换，按这个规则排序出来为升序，反之为降序
  1. 交换数据的方式
  • 同样的是，我们不知道数据类型，但我们知道数据的大小，所以我们可以一个一个字节的交换
代码语言：javascript复制
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  ;
    }
}

这样我们就完成了qsort函数的模拟实现

如下：

代码语言：javascript复制
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 (arr[j] > arr[j   1])
            //比较两个元素
            if (cmp((char*)base   j * width, (char*)base   (j   1) * width) > 0)
            {
                //交换两个元素
                Swap((char*)base   j * width, (char*)base   (j   1) * width, width);
            }
        }
    }
}

总结

本篇模拟实现qsort函数是很典型的回调函数的例子，因为不知道用户排序数据的类型，所以qsort函数的实现方把比较两个数据的函数交给用户自己去实现，这个函数通过函数指针传递给qsort，在qsort函数内部发生比较时再根据函数指针调用这个比较函数，这种就是回调函数

同时，在qsort函数的实现中，我们多次使用了void*指针

  • void* base用以接收不同类型的数组
  • 规定compare函数参数设置为两个const void*，用以接收不同的数据类型，用户使用时知道排序什么数据进行强制类型转换后再使用

巧妙地使用void*指针实现了对不同数据排序，这种编程也叫做泛型编程

写在最后

C语言指针是一个重头戏，关于指针的内容会有4-5篇博客，敬请期待喔

指针 函数 排序 数据 数组

0 人点赞