✨ 猪巴戒:个人主页✨
所属专栏:《C语言进阶》
🎈跟着猪巴戒,一起学习C语言🎈
目录
前情回顾
1、回调函数
2、冒泡排序
3、库函数qsort
cmp(sqort中的比较函数,需要我们自定义)
整形的升序排列
整形的倒序排列
结构体的排序
结构体按照名字(char类型)排序
结构体按照年龄(int类型)排序
库函数qsort的模拟实现(bubble_sort)
呈现bubble_sort函数的整体代码:
bubble_sort的结构体排序
age:
name:
前情回顾
函数指针
我们有一个函数,为Add,我们将函数的地址用指针来存储,这个指针就叫做函数指针。
int Add(int x,int y)
{
return x+y;
}
int main()
{
int (*pf)(int,int) = Add;//pf就是函数指针。
return 0;
}
函数指针数组
把函数指针放在数组中,就是函数指针的数组。
int Add(int x,int y)
{
return x+y;
}
int Sub(int x,int y)
{
return x-y;
}
int Mul(int x,int y)
{
return x*y;
}
int Div(int x,int y)
{
return x/y;
}
int main()
{
int (*arr[4])(int ,int) = {Add,Sub,Mul,Div};//这个就是函数指针数组。
return 0;
}
函数指针数组就可以调用函数:
int main()
{
int i = 0;
scanf("%d",&i);
int ret = arr[i](8,4);
printf("%d\n",ret);
}
1、回调函数
回调函数就是应该通过函数指针调用的函数。如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,我们就说这是回调函数。回调函数不是由这个函数的实现方直接调用,而是在特定的事件或条件发生时由另外的一方调用的,用于对该事件或条件进行响应。
我们可以把Add函数称为回调函数。
int Add(int x,int y)
{
return x+y;
}
int main()
{
int (*pf)(int,int) = Add;
int ret = pf(8,4);
return 0;
}
2、冒泡排序
对一个数组进行升序排序。
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;
}
}
}
}
int main()
{
int arr[] = {9,8,7,6,5,4,3,2,1 };
//把数组排成升序
int sz = sizeof(arr)/sizeof(arr[0]);
bubble_sort(arr,sz);
int i = 0;
for(i=0;i<sz;i++)
{
printf("%d",arr[i]};
}
这个冒泡排序不够高效,如果我们进行一趟冒泡排序,但是一个数字都没有交换,就说明这个数组已经排序好了,就不用继续排序了,
我们可以通过,在进行这一趟冒泡排序前设定int flag = 1;
如果数字进行了交换,就把flag的值改为0;
没有数字进行交换,那么flag的值还是1;
我们通过判断flag的值看数组是否已经排好序。
void bubble_sort(int arr[],int sz)
{
int i=0;
//趟数
for(i=0;i<sz-1;i++)
{
int flag = 1;//假设数组是排好序的。
//一趟冒泡排序的过程
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;
flag = 0;//数组进行了排序
}
}
if(flag == 1)
{
break;
}
}
}
int main()
{
int arr[] = {9,8,7,6,5,4,3,2,1 };
//把数组排成升序
int sz = sizeof(arr)/sizeof(arr[0]);
bubble_sort(arr,sz);
int i = 0;
for(i=0;i<sz;i++)
{
printf("%d",arr[i]};
}
return 0;
}
3、库函数qsort
使用快速排序的思想实现的一个排序函数。
qsort可以排序任何类型的数据
void qsort(void* base,//你要排序的数据的起始位置
size_t num,//待排序的数据元素的个数
size_t width,//待排序的数据元素的大小(单位是字节)
int(* cmp)(const void* e1,const void* e2)//函数指针-比较函数
);
cmp(sqort中的比较函数,需要我们自定义)
int(* cmp)(const void* e1,const void* e2)中的e1,e2就是我们要比较数据的地址。
在这个比较函数中我们实现不同类型的元素比较
void*是无具体类型的指针,可以接收任何类型的地址
void*是无具体类型的指针,所以不能解引用操作,也不能+-整数
当比较函数返回的是大于0的数字,那么两组数据就会进行交换。
进行整型数据的比较, 这是进行升序排列
int cmp_int(const void* e1,const void* e2)
{
return (*(int*)e1 - *(int*)e2);
}
整形的升序排列
通过qsort来将数组进行升序排序
//比较两个整形元素
//e1指向一个整形
//e2指向另外一个整形
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void* e1,const void* e2)
{
return (*(int*)e1 - *(int*)e2);
}
int main()
{
int arr[] = {9,8,7,6,5,4,3,2,1};
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr,sz,sizeof(arr[0]),cmp_int);
int i = 0;
for(i=0;i<sz;i++)
{
printf("%d ",arr[i]);
}
return 0;
}
cmp_int就是回调函数
整形的倒序排列
当我们需要进行降序排列,只要将e2和e1的顺序倒过来就可以实现
int cmp_int(const void* e1,const void* e2)
{
return (*(int*)e2 - *(int*)e1);
}
结构体的排序
结构体按照名字(char类型)排序
char类型的数据不能够直接比较,我们用到strcmp进行比较,
库函数strcmp
头文件<string.h>
int strcmp( const char *string1, const char *string2 );
如果string1小于string2,就会返回小于0的数
如果string1等于string2,就会返回0
如果string1大于string2,就会返回大于0的数
#include<stdlib.h>
#include<string.h>
struct Stu
{
char name[20];
int age;
};
int cmp_stu_by_name(const void* e1,const void* e2)
{
return strcmp(((struct Stu*)e1)->name,((struct Stu*)e2)->name);
}
int main()
{
struct Stu s[] = {{"zhangsan",15},{"lisi",30},{"wangwu",25}};
int sz = sizeof(s) / sizeof(s[0]);
qsort(s,sz,sizeof(s[0]),cmp_stu_by_name);
return 0;
}
cmp_stu_by_name就是回调函数
结构体按照年龄(int类型)排序
#include<stdlib.h>
#include<string.h>
struct Stu
{
char name[20];
int age;
};
int cmp_stu_by_age(const void*e1,constvoid* e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
int main()
{
struct Stu s[] = {{"zhangsan",15},{"lisi",30},{"wangwu",25}};
int sz = sizeof(s) / sizeof(s[0]);
qsort(s,sz,sizeof(s[0]),cmp_stu_by_age);
return 0;
}
库函数qsort的模拟实现(bubble_sort)
如何实现qsort函数?库函数qsort的设计原理是什么?
创建自定义函数实现库函数qsort的功能。
基于qsort实现原理,实现将整形数组升序排列
设计自定义函数bubble_sort,等同于库函数qsort
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );
base:数据的起始位置,首元素的地址
sz: 数据元素的个数,比较数组的话,就是数组中元素的个数
width:待排序的数据元素的大小(单位是字节),比较整形数组的话,就是4个字节,数组元素占内存的大小
cmp:自定义的比较函数。
关于bubble_sort的设计细节
这是我们对解决整形数组升序排列问题,也就是冒泡排序,原来的的bubble_sort.
但是我们现在要设计的bubble_sort,需要与qsort有相同的功能(排序任何类型的数据)
void bubble_sort(int arr[],int sz)
{
int i=0;
//趟数
for(i=0;i<sz-1;i++)
{
int flag = 1;//假设数组是排好序的。
//一趟冒泡排序的过程
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;
flag = 0;//数组进行了排序
}
}
if(flag == 1)
{
break;
}
}
}
1.
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
参数void类型可以接收任何类型的数据
2.
判断大小,
原来:数组元素比较大小
现在:比较一种无知类型元素大小,通过比较函数(cmp)来比较,由于我们不知道要比较的元素类型是什么,但是我们要找到每个元素的地址,就通过(char*)base + j * width,
第一个元素的地址就是首元素的地址,
第二个元素的地址就是首元素的地址加上一个元素的字节
width:待排序的数据元素的大小(单位是字节)
在bubble_sort中,cmp((char*)base + j * width, (char*)base + (j + 1) * width)
3.
自定义函数(cmp)的实现,已知我们要比较的是整形元素的大小,和库函数qsort解决整形的升序排列一样
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
4.
交换元素
cmp_int的功能
当比较函数返回的是大于0的数字,那么两组数据就会进行交换。
进行整型数据的比较, 这是进行升序排列
在bubble_sort中,当cmp判断>0时
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
进行交换
交换函数
我们要找到各个元素我们才能进行比较,所以和cmp函数的实现类似,
我们要传递的参数
Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
找到了各个元素的地址,也知道元素的大小(字节),就可以进行比较,
一个一个字节进行比较,
Swap函数实现:
void Swap(char* buf1, char* buf2, int width)
{
int i = 0;
for (i = 0; i < width; i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
5.
为了函数的高效性,我们把原来的flag的设计保留。
也就是int flag = 1;(假设数组已经排列好)
如果在这一趟的冒泡排序的过程中,数字进行了交换,就把flag的值改为0;
没有数字进行交换,那么flag的值还是1,就可以直接跳出循环;
呈现bubble_sort函数的整体代码:
#include<stdio.h>
void Swap(char* buf1, char* buf2, int width)
{
int i = 0;
for (i = 0; i < width; i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
int i = 0;
//趟数
for (i = 0; i < sz - 1; i++)
{
int flag = 1;//假设数组是排好序
//一趟冒泡排序的过程
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);
flag = 0;
}
}
if (flag == 1)
{
break;
}
}
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
//0 1 2 3 4 5 6 7 8 9
//把数组排成升序
int sz = sizeof(arr) / sizeof(arr[0]);
//bubble_sort(arr, sz);
bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
}
bubble_sort的结构体排序
前面有完整的bubble_sort的实现,这里就不把bubble_sort写上了
#include<string.h>
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;
}
int cmp_stu_by_name(const void* e1, const void* e2)
{
return strcmp(((struct Stu*)e1)->name , ((struct Stu*)e2)->name);
}
void test()
{
struct Stu s[] = { {"zhangsan", 15}, {"lisi", 30}, {"wangwu", 25} };
int sz = sizeof(s) / sizeof(s[0]);
bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_name);
//bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}
int main()
{
test();
return 0;
}