【C指针（五）】6种转移表实现整合longjmp()/setjmp()函数和qsort函数详解分析&&模拟实现3：https://developer.aliyun.com/article/1474742
3.2.1qsort函数排序整型数据
s#include <stdio.h> #include <stdlib.h> 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*)p1 - *(int*)p2; } //测试qsort排序整型数据的 int main() { int arr[10] = { 4,2,5,3,1,6,7,8,0,9 }; int sz = sizeof(arr) / sizeof(arr[0]); print_arr(arr, sz);//打印前 qsort(arr, sz, sizeof(arr[0]), cmp_int); //arr->数组首元素地址 //sz->数组元素个数也可以这样写sz==sizeof(arr)/sizeof(arr[0]) //sizeof(arr[0])->数组元素大小，这里字节大小为4 //cmp_int比较函数 print_arr(arr, sz);//打印后 }
3.2.2 使⽤qsort排序结构数据
- 定义结构体类型
struct Stu { char name[20];//名字 int age; };
- 定义比较函数
- 怎么比较2个结构体数据？ - 不能直接使用 > < ==比较
- 可以按照名字比较
- 可以按照年龄比较
void test2() { struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 38}, {"wangwu", 18} }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age); }
代码实现：
# define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> 测试qsort函数排序结构体数据 struct Stu { char name[20];//名字 int age; }; int cmp_stu_by_age(const void* p1, const void* p2) { return ((struct Stu*)p2)->age - ((struct Stu*)p1)->age; } void print(struct Stu arr[], int sz) { for (int i = 0; i < sz; i++) { printf("%s %d\n", arr[i].name, arr[i].age); } } void test2() { struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 38}, {"wangwu", 18} }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age); print(arr, sz); } // //两个字符串不能使用> < == // //而是使用库函数strcmp - string compare int cmp_stu_by_name(const void* p1, const void* p2) { return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name); } void test3() { struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 38}, {"wangwu", 18} }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name); print(arr, sz); } int main() { test3();//姓名排序 //test2();//年龄排序 return 0; } # def
四、 qsort函数的模拟实现
4.1 模拟qsort整形数据
- 主函数：
- 定义
int测试数据 - 调用
bubble排序 - 打印结果验证
#include <stdio.h> int main() { int arr[] = { 3, 1, 5, 8, 4, 2, 9, 6, 7, 0 }; int i = 0; //元素个数 //元素大小 bubble(arr, sizeof(arr) / sizeof(arr[0]), sizeof(int), int_cmp); //数组首元素地址arr //比较函数 for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
- bubble函数：
- 接收基地址、元素个数、元素大小、比较函数作为参数
- 实现冒泡排序核心算法
- 通过传递的比较函数
int_cmp来决定排序顺序 - 使用
_swap函数交换元素
void bubble(void* base, int count, int size, int(*cmp)(void*, void*)) { int i = 0; int j = 0; for (i = 0; i < count - 1; i++) { for (j = 0; j < count - i - 1; j++) { if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0) { _swap((char*)base + j * size, (char*)base + (j + 1) * size, size); } } } }
int_cmp函数：
- 定义一个
int类型的数据比较函数 - 通过减法实现两个int*指针所指向的数据比较
- 返回值
大于0表示p1大于p2（升序）,小于0表示p1小于p2（降序） - 实现了冒泡排序中的比较规则
int int_cmp(const void* p1, const void* p2) { return (*(int*)p1 - *(int*)p2); }
_swap函数：
- 定义泛型数据交换函数
- 通过循环交换每个字节实现数据交换
- 使用
char*来交换，实现数据类型无关
void _swap(void* p1, void* p2, int size) { int i = 0; for (i = 0; i < size; i++) { char tmp = *((char*)p1 + i); *((char*)p1 + i) = *((char*)p2 + i); *((char*)p2 + i) = tmp; } }
总结：
每个代码块实现的功能：
- 主函数： 测试驱动开发
bubble: 实现冒泡排序算法int_cmp: 提供比较规则_swap: 实现泛型数据交换
4.2 模拟qsort排序结构数据
各个代码块分析如下：
struct Stu定义结构体类型，包含姓名和年龄字段。
# define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> struct Stu { char name[20]; int age; };
- Swap函数实现泛型数据交换，通过循环交换每个字节实现数据交换。
void Swap(char* buf1, char*buf2, size_t width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } }
- bubble_sort2函数实现冒泡排序算法，和普通冒泡排序区别在于使用void*作为参数，通过width实现对结构体进行排序。
void bubble_sort2(void* base, int sz, int 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) { /*int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp;*/ //交换 Swap((char*)base + j * width, (char*)base + (j + 1) * width, width); } } } }
cmp_stu_by_age函数实现结构体比较规则，根据年龄字段进行比较。
int cmp_stu_by_age(const void* p1, const void* p2) { return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age; }
- test4函数定义测试数据，调用
bubble_sort2进行排序，打印结果验证。
void test4() { struct Stu arr[] = { {"zhangsan", 18},{"lisi", 35},{"wangwu", 15} }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort2(arr, sz, sizeof(arr[0]), cmp_stu_by_age); //打印arr数组的内容 int i = 0; for (i = 0; i < sz; i++) { printf("%s %d\n", arr[i].name, arr[i].age); } } voi
main函数调用test4函数进行测试。
inint main() { //模拟结构体按年龄排序 test3(); return 0; }
小总结：
struct Stu定义了需要排序的数据类型Swap函数实现数据交换bubble_sort2实现泛型冒泡排序cmp_stu_by_age定义了结构体比较规则test4函数测试驱动开发
总结
一、转移表
利用函数指针数组实现转移表是动态规划算法解决最优子结构问题时使用的一种技术。它记录了子问题的解，避免重复计算。
二、回调函数是什么?
回调函数是指在函数调用后，被当作参数传递给另一个函数的函数。调用方在需要时，会调用被调用方内部的这个函数。
三、qsort函数细解
3.1 类比冒泡排序?
qsort函数实现的也是冒泡排序算法。不同之处在于：
qsort是通用排序函数，可以对任意数据类型进行排序，而冒泡排序只能对数组进行排序;
qsort通过回调函数来指定元素的比较方式，而冒泡排序直接比较元素值;
qsort内部实现采用快速排序思想，而不是纯粹的冒泡排序。
3.2 qsort函数超详解
qsort函数原型：
void qsort(void *base, size_t num, size_t size, int (*compar)(const void*, const void*)); • 1
base:待排序数组首地址- num:数组元素个数
size:每个元素大小
compar:比较函数回调，返回值小于0时交换元素
3.2.1 qsort排序整型数据
直接传入整型比较函数如int cmp(const void*, const void*)
3.2.2 使用qsort排序结构数据
定义结构体比较函数，通过强制类型转换比较结构体字段
四、qsort函数的模拟实现
4.1 模拟qsort整形排序
实现了一个简单快速排序函数，可以对整型数组排序。
4.2 模拟qsort结构体排序 同样实现快速排序，但使用结构体比较函数作为回调。
