指针专题(4)【qsort函数的概念和使用】

2024-04-23 14:04

本文主要是介绍指针专题(4)【qsort函数的概念和使用】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.前言

上节我们学习了指针的相关内容,本节我们在有指针的基础的条件下学习一下指针的运用,那么废话不多说,我们正式进入今天的学习

2.回调函数

我们既然已经学习了指针的相关基础,那么我们此时就可以用指针来实现回调函数

而回调函数又是什么呢?

回调函数是一个通过函数指针调用的函数

如果我们把一个函数的地址作为参数传递给第二个函数,当第二个函数被用来调用它所指向的第一个函数的时候,此时第一个函数就被称为回调函数;

我们来举一个例子,这样就会更通俗易懂:假如有A和B两个函数,如果把A的地址传递给B,当B被用来调用A函数的时候,此时A函数就是回调函数;

我们需要注意:回调函数并不是由函数的实现方直接调用的,而是在特定的情况下通过另外一方去调用的,也就是说,回调函数是一种机制,用于对特定的事件进行响应;

上一节我们学习了计算器的代码编写,我们就可以使用回调函数的知识对代码进行修改和优化

我们在使用回调函数改造前,我们通常会这样编写代码:

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;
}
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("  0:exit                 \n");printf("*************************\n");printf("请选择:");scanf("%d", &input);switch (input){case 1:printf("输⼊操作数:");scanf("%d %d", &x, &y);ret = add(x, y);printf("ret = %d\n", ret);break;case 2:printf("输⼊操作数:");scanf("%d %d", &x, &y);ret = sub(x, y);printf("ret = %d\n", ret);break;case 3:printf("输⼊操作数: ");scanf("%d %d", &x, &y);ret = mul(x, y);printf("ret = %d\n", ret);break;case 4:printf("输⼊操作数:");scanf("%d %d", &x, &y);ret = div(x, y);printf("ret = %d\n", ret);break;case 0:printf("退出程序\n");break;default:printf("选择错误\n");break;}} while (input);return 0;
}

此时的代码重复率非常高,代码非常冗余

我们若想要对代码进行优化,我们需要注意以下几点:

1.我们要把相似代码抽象成函数

2.我们学习了函数指针以后,我们知道了:函数的调用可以使用函数名来调用也可以使用函数指针来调用;我们可以通过参数的差异来计算不同的逻辑

有了这些理论基础我们就可以对代码进行修改了:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
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;
}void calc(int(*pf)(int, int))
{int x, y;int ret = 0;printf("输入操作数:");scanf("%d %d", &x, &y);ret = pf(x, y);printf("ret = %d\n", ret);
}
int main()
{int input = 1;do{printf("*************************\n");printf("  1:add           2:sub  \n");printf("  3:mul           4:div  \n");printf("  0:exit                 \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;
}

我们这个方法就是把一个函数的地址传递给了另外一个函数,然后通过另外一个函数用函数指针去调用要使用的函数

3.qsort函数

我们刚才学习了回调函数,我们现在接着来学习一个和回调函数逻辑差不多的函数:qsort函数

qsort函数是一个用来排序的函数,它是一个库函数,可以直接拿来排序,其底层原理使用的是快速排序的方式

我们之前说过:函数排序的底层方式有很多,大致包括:选择排序、插入排序、冒泡排序、快速排序、希尔排序

我们先来思考一下qsort函数为什么被设计出来呢?它的存在相比较其他的函数有什么优势呢?

我们首先将qsort函数与冒泡排序做一个对比,我们先写出冒泡排序的代码:

我们来回顾一下冒泡排序的核心思想:冒泡排序是将两两相邻的元素进行比较,如果不满足顺序就交换

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]);}printf("\n");
}
int main(void)
{//冒泡排序,排序为升序int arr[] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);print_arr(arr, sz);return 0;
}

写完代码以后我们可以发现冒泡排序的局限性:因为冒泡排序数据传入的时候已经确定了类型,冒泡排序只能排序一种类型的数据,如果排序的是整型 ,则无法排序字符串、结构体数据等;如果要用冒泡排序排序字符串有需要重新创造一个函数,这样就会导致代码重复率高,代码冗杂等问题

此时我们就可以了解一下qsort函数,qsort函数可以排序任意类型的数据,我们来看一下qsort函数的使用方法:

我们通过上图可以知道,qsort函数使用需要包含头文件<stdlib.h>,而且qsort函数的使用需要4个变量:

1.void* base,该变量是一个指针变量,指针指向的是待排序数组的第一个元素

2.size_t num,该变量表示的是待排序数组里面的元素个数

3.size_t size,该变量表示的是待排序数组里面每个元素的大小

4.int (*compar)(const void*, const void*),该变量是一个函数指针,该函数指向一个函数,这个函数的功能是用来比较两个元素的大小。这个概念有点抽象,我们逐步理解:

刚才我们编写了冒泡排序的代码,假设我们需要在原冒泡排序代码的基础上改造冒泡排序。让它能够排序任意类型的数据,我们来思考一下哪些地方需要修改?

我们在两个数据的比较方式这里不能直接用大于号或者小于号比较只有整型元素可以直接用>、<比较,字符串、结构体等元素是不能用>、<比较的,而是使用strcmp函数等其他方法比较

所以要想比较所有类型的数据,我们比较的代码就需要修改:

此时我们就不能直接比较,应该要把比较两个元素的方法封装成一个函数,然后把函数的地址传递给排序函数。如果传递的是整型比较函数的地址,那么就按照整型的比较方式比较;如果传递的是字符比较函数的的地址,那么就按照字符串的比较方式比较......

其实这种方法就是qsort的比较方法, qsort函数的第四个变量指向的就是两个元素的比较函数,所以我们要传入两个元素比较函数的地址这里的传入需要我们自己实现,因为qsort函数的实现者并不知道要排序的数据的类型,只有qsort函数的使用者知道要排序的数据的类型,所以需要我们自己提供两个元素的比较函数,然后把比较函数的地址传给qsort函数,qsort函数内部在比较的时候就会调用这个函数;

那么知道了qsort函数的原理,我们来写一串代码使用qsort函数排序整型数据:

我们要想用qsort函数排序整型数据,那么我们需要自己完成整型数据比较的函数,并将函数地址传给qsort函数:

我们可以看到,第四个变量的形式是:int (*compar)(const void*, const void*)

所以我们在写代码的时候就需要按照以上的形式来确定变量的类型,这样qsort函数才能顺利接收到函数

我们可以看到,compare函数的两个参数的类型都是const void*,此时p1中存放的是第一个要比较元素的地址,p2中存放的是第二个要比较元素的地址,如果p1指向的元素大于p2指向的元素,那么将返回一个大于0的数字;如果p1指向的元素小于p2指向的元素,那么将返回一个小于0的数字;如果p1指向的元素等于于p2指向的元素,那么将返回一个等于0的数字;

如果要对两个元素进行比较,不能够直接解引用,因为p1和p2两个变量的类型是void* ,是没有具体类型的,我们不能直接解引用,也不能进行+-整数的运算。此时我们就需要强制类型转换,转换完以后再进行解引用

有了这些理论基础,我们此时就可以写出代码如下:

int cmp_int(const void* p1, const void* p2)
{if (*(int*)p1 > *(int*)p2)return 1;else if (*(int*)p1 == *(int*)p2)return 0;elsereturn -1;
}

现在我们就可以完成全代码的书写了:

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)
{if (*(int*)p1 > *(int*)p2)return 1;else if (*(int*)p1 == *(int*)p2)return 0;elsereturn -1;
}void test01()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_int);print_arr(arr, sz);
}int main(void)
{test01();return 0;
}

代码运行成功,编写成功

如果我们再仔细思考一下,我们可以发现比较函数的代码可以简化:

int cmp_int(const void* p1, const void* p2)
{return (*(int*)p1 - *(int*)p2);
}

我们可以直接让两个变量解引用的值做差,也可以完成该函数的功能,并且代码量更少,更加简洁

如果我们需要对元素进行降序比较,我们修改代码也同样很方便,我们只需要让后面的元素减去前面的元素就可以实现降序的功能:

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*)p2 - *(int*)p1);
}void test01()
{int arr[] = { 5,8,7,6,9,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_int);print_arr(arr, sz);
}int main(void)
{test01();return 0;
}

既然我们刚才已经学习了使用qsort函数排序整型数据,我们接着来用qsort函数排序一下结构体

我们知道,结构体是不能直接用>、<号来比较的,我们先来定义一个结构体:

struct Stu
{char name[20];int age;
};

我们定义了一个学生的结构体,结构体成员为学生的姓名和年龄,我们若是要对结构体进行排序,那么我们就有两种排序方法:

1.我们可以通过年龄来排序

2.我们可以通过姓名来排序

我们先来创建一个数组用于存储结构体数据:

    struct Stu arr[3] = { {"zhangsan",20},{"lisi",35},{"wangwu",18} };

1.我们先写用姓名来排序的代码:

要想通过姓名来排序,我们需要使用到strcmp函数:

strcmp 是按照对应字符串的字符的ASCII码值进行比较的函数

我们发现strcmp的返回值非常适合我们自己写的比较函数,所以我们可以写出代码如下:

int cmp_stu_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}

我们先要对p1、p2强制类型转换为结构体类型,再通过结构体成员访问操作符->来找到姓名,再使用strcmp函数进行比较

通过这些,我们就可以很轻易的写出代码:

struct Stu
{char name[20];int age;
};int cmp_stu_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}void print_arr(struct Stu arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%s ", arr->name);arr++;}printf("\n");
}void test02()//结构体
{struct Stu arr[3] = { {"zhangsan",20},{"lisi",35},{"wangwu",18} };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);print_arr(arr, sz);
}int main(void)
{test02();return 0;
}

2.接下来我们再来按年龄排序

(代码相似度很高,逻辑差不多,所以不作详解,请自主思考解题过程谢谢)

struct Stu
{char name[20];int age;
};int cmp_stu_by_age(const void* p1, const void* p2)
{return (((struct Stu*)p1)->age - ((struct Stu*)p2)->age);
}void print_arr(struct Stu arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr->age);arr++;}printf("\n");
}void test02()//结构体
{struct Stu arr[3] = { {"zhangsan",20},{"lisi",35},{"wangwu",18} };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);print_arr(arr, sz);
}int main(void)
{test02();return 0;
}

模拟实现qsort函数

刚才我们学习了qsort函数的概念以及使用,现在我们来模仿qsort函数来实现一个冒泡排序的函数,这个函数可以排列任意类型的数据

因为我们要接受任意类型的数据,所以我们接受参数的临时变量的类型就不能是int,我们就需要将变量类型改成void* ,可以用来接收任意类型的数据

此时函数的参数就可以直接修改成qsort函数里的参数:

void bubble_sort(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2));

我们可以不用修改趟数只需要改变比较数据的方式

            if (cmp()>0)

那么此时cmp函数里面应该存入什么参数呢?我们应该存入arr[j]和arr[j+1]的地址,此时我们不能直接用&找到地址,我们应该用什么方法来取到它们的地址呢?

如果我们要找到下标为0和下标为1处的地址,我们知道下标为0处的地址就是base,下表为1处的地址就为base处的地址跳过width个字节,因为base是void* 类型的地址,不能进行+-操作,所以此时我们就需要把base转换成char* 类型的变量,然后再+width

所以arr[j]处的地址就为 (char*)base+j*width,arr[j+1]处的地址就为 (char*)base+(j+1)*width

            if (cmp((char*)base+j*width,(char*)base+(j+1)*width)>0)

此时我们交换的具体代码也需要改变,我们封装一个函数Swap,用于交换

我们需要往Swap函数里面传入3个参数:

Swap(cmp((char*)base + j * width, (char*)base + (j + 1) * width), width);

有了这些理论基础,我们就能很轻易的写出代码如下:

结尾

本节我们学习了指针的相关运用,加强了对指针的理解,下一节是指针的最后一节,谢谢您的浏览!!!

这篇关于指针专题(4)【qsort函数的概念和使用】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/928995

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]