C语言库函数之 qsort 讲解、使用及模拟实现(下)

简介: C语言库函数之 qsort 讲解、使用及模拟实现(下)

结构体类型

如果我们想要排序结构体类型的变量,那就很有意思了,我们一步一步来分析

明确需要

main函数、test3函数、cmp_stu函数

下面我们重点解释一下test3函数和cmp_stu函数

test3函数

1.创建结构体类型的数组,并初始化

2.求数组元素个数

3.调用qsort函数,里面包含了cmp_stu函数的地址,即调用cmp_stu函数

cmp_stu函数

照猫画虎

我们按照前面的两个例子写出来的应该是

int cmp_struct(const void* e1, const void* e2)
{
  return *(struct*)e1 - *(struct*)e2;
}

但这么写是错误的, 因为结构体是复杂对象,无法直接用 > 或 < 进行比较,那么我们就需要确定是用哪个成员去作为比较的标准

再通过->来访问相应的成员

下面给出两个例子,此处分别以年龄age作为排序标准和以名字name来排序,

cmp_stu_by_age函数

将e1和e2从void* 类型转换成结构体类型指针,然后再通过->访问相应的成员

然后直接让二者相减即可,此处在强制类型转换时别忘了写上struct就行

int cmp_stu_by_age(const void* e1, const void* e2)
{
  return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

这个函数的实现还是与cmp_int函数有一些相似的,

cmp_stu_by_name函数

提示:此处比较的是字符串,同样不能用 > < 来进行比较

而是要用strcmp函数进行比较,包含头文件<string.h>

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

最终代码

#include<stdlib.h>
struct Stu
{
  char name[40];
  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);
  提示,此处比较的是字符串,同样不能用 > < 来进行比较
    而是要用strcmp函数进行比较
}
void test3()
{
  struct Stu s[3] = { {"zhang", 20},{"li", 30},{"wang", 40} };
  int sz = sizeof(s) / sizeof(s[0]);
  qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}
int main()
{
  test3();
  return 0;
}

三个例子到这里就介绍结束了,其实这样看下来也不是很难理解。

下面我们来学习qsort函数的模拟实现,也就是优化bubble_sort函数,使它能排序任意类型的元素

模拟实现

引入:

此处提出一个问题:如果说,我不想使用qsort函数,我就想使用冒泡函数,那我要如何改进它,才能达到和qsort函数相同的效果呢?

函数调用方面的改进

接收地址

如果说想让冒泡排序函数具有排序任意类型元素的功能,那么首先,它就应该能接收任意类型元素的地址(类似于qsort中的base参数)

元素个数

函数需要知道要排序多少个元素,所以就需要传入数组的大小(类似num参数)

元素大小(宽度)

知道了待排序数组的起始位置和元素个数后,我们需要对数组中的元素进行移动操作, 那么我们就需要知道元素的大小是什么

简易版框架如下:

void bubble_sort(void* base, int sz, int width)
{
  int i = 0;//次数
  for (i = 0; i < sz; i++)
  {
    //每次需要比较的元素对数
    int j = 0;
    for (j = 0; j < sz - 1 - i; j++)//比较两个元素
    {
    }
  }
}

疑问1:

基本框架搭建好了,那我们要如何比较两个元素呢,我们又不知道他们的类型?

所以我们在传参的时候,还需要将两个元素的比较方法(函数)一并传进bubble_sort函数中,也就是第四个参数

首先,要传入的肯定是函数的地址,

其次,我们需要返回一个值来告诉我们比较的结果是什么(此处类似qsort函数的返回值)

最后,对于要比较的两个元素,因为要求函数具有通用性,所以参数类型就是void *类型

代码如下:

void bubble_sort(void* base, int sz, int width, int(*cmp)(void* e1,void* e2) )
{
  int i = 0;//次数
  for (i = 0; i < sz; i++)
  {
    //每次需要比较的元素对数
    int j = 0;
    for (j = 0; j < sz - 1 - i; j++)//比较两个元素
    {
      if(cmp()>0)//交换if(cmp()>0)//交换
      {
      }
      }
    }
  }
}

疑问2:if语句

if(cmp()>0)//交换
  {
  }

我们知道这个语句是比较两个元素,那我们怎么找到这俩个元素呢?

我们知道,base就是首元素的地址,

想法1

那么有人想通过加减整数来找到后面的元素,这个问题在我前面的文章提到过:因为元素是void*类型的,不知道元素大小,无法与整数进行运算

想法2

那么又有人想:将base传换成(int*)类型再运算不就行了吗,

还是不对,因为我们不知道传进来的参数究竟是什么类型,所以我们不能假定他的类型

想法3

小明这时候提出来:我们已经知道了每个元素的大小:width,那可不可以先把base转换成char*类型,再加上每个元素的字节大小width呢?

这么做就可以了,

因为char*大小是一个字节,每次移动width个字节,就进入到下一个元素中了

if语句代码如下:

if(cmp((char*)base+ j*width, (char*)base +(j+1)*width)>0)//交换
{
}

疑问3:怎么交换

这里先创建一个swap函数用于两个元素的交换

void Swap(char*buf1, char*buf2)
{
}
void bubble_sort(void* base, int sz, int width)
{
  int i = 0;//次数
  for (i = 0; i < sz; i++)
  {
    //每次需要比较的元素对数
    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);
      }
    }
  }
}

但是,我们仔细看,Swap函数接收的参数类型是char*,一个字节大小,如果我这个元素是8个字节类型,要怎么交换呢,

所以如果按照一个字节一个字节这么交换的方式,我们就需要知道要交换的元素的字节大小(width),以及要交换几次

代码如下:

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类型)

完整代码如下:

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++;
  }
}
void bubble_sort(void* base, int sz, int width, int (*cmp)(void*e1, void*e2))
{
  int i = 0;//次数
  for (i = 0; i < sz; i++)
  {
    //每次需要比较的元素对数
    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);
      }
    }
  }
}
int cmp_int(const void* e1, const void* e2)
{
  return *(int*)e1 - *(int*)e2;
}
void test4()
{
  int arr[10] = { 1,2,3,4,5,6,7,8,9,0 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
}
int main()
{
  test4();
  return 0;
}

想要进行其他类型的比较只需要在调用bubble_sort函数时,将第四个参数修改成对应的比较方法即可(当然,这需要自己构建)

小提示:

->的优先级高于强制类型转换,所以要用()先将强制类型转换括起来,先转换,再访问

题外话

因为想要使bubble_sort函数具有通用性,所以我们需要将不同类型元素的比较方法的函数的地址传进来(也就是第四个参数),而这种将函数地址传进另一个函数,由这个函数去实现调用的方法,就称为回调函数(大概就是这个意思),我这几天在整理指针的知识,有时间就写一篇博客。

结语

没想到感觉没怎么写,就写了六千多字(捂脸)

只能再一次感叹C的丰富

文章到这里就结束了,希望这篇文章对你有所帮助,我们下篇文章见~

相关文章
|
17小时前
|
算法 Java C语言
Java中的算法与C语言中的函数
Java中的算法与C语言中的函数
7 2
|
5天前
|
安全 C语言
【C语言基础】:内存操作函数
【C语言基础】:内存操作函数
|
5天前
|
编译器 C语言 C++
【C语言基础】:字符函数和字符串函数-2
【C语言基础】:字符函数和字符串函数
|
5天前
|
C语言
【C语言基础】:字符函数和字符串函数-1
【C语言基础】:字符函数和字符串函数
TU^
|
5天前
|
编译器 程序员 Serverless
C语言之函数
C语言之函数
TU^
4 0
TU^
|
5天前
|
机器学习/深度学习 C语言
C语言之函数递归
C语言之函数递归
TU^
10 1
|
5天前
|
C语言
C语言——字符串操作函数
C语言——字符串操作函数
6 0
|
5天前
|
机器学习/深度学习 算法 C语言
【C语言基础】:函数递归详解
【C语言基础】:函数递归详解
|
5天前
|
编译器 程序员 C语言
【C语言基础】:函数详解
【C语言基础】:函数详解
|
5天前
|
存储 API C语言
C语言函数大全--f开头的函数(上)
【6月更文挑战第7天】本篇介绍 C语言中 f 开头的函数(上篇)【C语言函数大全】
18 3
C语言函数大全--f开头的函数(上)