【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)

简介: 【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)

一、回调函数

回调函数通过一个函数指针调用的函数。把一个函数的地址作为一个参数传递给另外一个函数,当这个地址被用来调用其指向的函数时,被调用函数称为回调函数跟函数嵌套差不多

//使⽤回到函数改造后
#include <stdio.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 d(int a, int b)
{
  return a / b;
}
void calc(int(*pf)(int, int))
{
  int ret = 0;
  int x, y;
  printf("输⼊操作数:");
  scanf("%d %d", &x, &y);
  ret = pf(x, y);
  printf("ret = %d\n", ret);
}
int main()
{
  int input = 1;
  do
  {
    scanf("%d", &input);
    switch (input)
    {
    case 1:
      calc(add);
      break;
    case 2:
      calc(sub);
      break;
    case 3:
      calc(mul);
      break;
    case 4:
      calc(d);
      break;
    case 0:
      printf("退出程序\n");
      break;
    default:
      printf("选择错误\n");
      break;
    }
  } while (input);
  return 0;
}

二、快速排序(Qsort)

快速排序属于九大排序之一,并且该函数在头文件stdlib.h 声明

2.1 Qsort参数部分介绍

void qsoer(void *base, size_t num, size_t size, int (*compare)(const void*,const void*));
  • void * base:待排序数据的起始位置,第一个元素
  • size_t num:待排序数据的元素个数
  • size_t size:待排序数据的每个元素的大小,单位是字节
  • int (*compare)(const void *,const void *):函数指针-指针指向的函数是来比较待排序数据中的两个元素大小关系

注意】:void 是无具体类型的指针(通用指针类型),对此可以接收任意数据类型的地址

2.2 不同类型的比较方法

提前说明】:关于比较函数的参数部分,void *是无具体类型的指针(通用指针类型),对此可以接收任意数据类型的地址。

整形类型:

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

字符类型(比较单字符的大小,字符串函数头文件string.h):

int char_compare(const void* e1, const void* e2)
{
  return strcmp((char*)e1, (char*)e2);
} 

字符串长度

int charnums_compare(const void* e1, const void* e2)
{
  return strlen((char*) e1) - strlen((char*) e1);
}

结构体整形成员

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

结构体字符串成员

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

说明】:不同类型数据的比较不能单单只通过大于小于号去判断,需要掌握不同类型的比较方法,以便于更好的使用qsort函数,但是在C++中,一般使用sort,而不是qsort函数,因为使用起来很复杂,而且需要自己实现个比较函数。

2.3 简单使用Qsort(对任意数据类型进行排序)

struct su
{
    int age;
    char name[100];
};
int main()
{
    int nums[] = { 2,6,7,9,10,1,8,5,3 };
    int sz = sizeof(nums) / sizeof(nums[0]);
    qsort(nums, sz, sizeof(nums[0]), compare);//函数名变身就是一个函数指针变量
    
    //结构体数组
    struct su s[] = { {18,"zhangsana"},{14,"xiaoming"},{9,"lierdan"} };
    int sz2 = sizeof(s) / sizeof(s[0]);
    qsort(s, sz, sizeof(s[0]), age_compare);
    return 0;
}

三、冒泡排序思想模拟实现快速排序(不是真正的快速排序)

前文:冒泡排序是一种简单的排序,但是只能排序整形数据,无法适应不同类型的场景。对此,我们将通过冒泡排序的思想模拟实现一个对任意类型能排序的快速排序

注意】:快速排序的底层不是这样子实现的,对此这里不是真正的快速排序

int main()
{
  int nums[] = { 2,6,7,9,10,1,8,5,3 };
  int sz = sizeof(nums) / sizeof(nums[0]);
  int with = sizeof(nums[0]);
  my_qsort(nums, sz, with, int_compare);
    return
}

3.1 函数内部:

void my_qsort(int* p, int sz, int width, int (*compare)(const void* e1, const void* e2))
{
  for (int i = 0; i < sz - 1; i++)
  {
    for (int j = 0; j < sz - i - 1; j++)
    {   
      if(compare((char*)base+j*width,(char *)base+(j+1)*width)>0)//compare 根据类型去定义
      { 
        Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
      }
    }
  }
}

【说明】:函数实现框架跟冒泡排序相似,主要的不同在于判断和交换语句底层逻辑的不同


3.2 底层逻辑解析

3.2.1 判断语句:

if(compare((char*)base+j*width,(char *)base+(j+1)*width))

说明】:

强制类型转化为char*类型(char *类型对于±整形,偏移量为一个字节)。width是某个类型的大小,那么这两个参数之间相差width大小,正好跳过某个类型元素。(适用于任意的数据进行比较)

3.2.2 比较函数:

int int_compare(const void* e1, const void* e2)//对比分类型
{
  return *(int*)e1 - *(int*)e2;
}

函数名】:int_compare表明了这里适合对整形数据对比,对于不同数据类型有不同的比较方法,在上面使用库函数qsort中有所涉及

3.2.3 Swap函数参数:

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

说明】:base是待排序数据的起始位置(首元素的地址),强制类型转化为char*类型,使得对于±整型,偏移量为一个字节。width是某个类型的大小,那么这两个参数之间相差width大小,正好跳过某个类型元素(j * width(j + 1) * width )。(适用于任意的数据进行比较)

3.2.4 Swap内部逻辑:

void Swap(char* e1, char* e2,int width)
{
  for (int i = 0; i<width;i++)
  {
    char tmp = *e1;
    *e1 = *e2;
    *e2 = tmp;
    e1++;
    e2++;
    }
}

说明】:强制类型转化为char *的目的是对于两个参数部分,逐一字节交换e1/2++不断向后移动到新的位置,再进行交换。Swap只交换一次,交换的字节数到达某类型的大小,则完成交换。(适用于任意的数据进行交换)


以上就是本篇文章的所有内容,在此感谢大家的观看!这里是店小二C语言笔记,希望对你在学习C语言中有所帮助!


相关文章
|
7天前
|
C语言
【c语言】指针就该这么学(1)
本文详细介绍了C语言中的指针概念及其基本操作。首先通过生活中的例子解释了指针的概念,即内存地址。接着,文章逐步讲解了指针变量的定义、取地址操作符`&`、解引用操作符`*`、指针变量的大小以及不同类型的指针变量的意义。此外,还介绍了`const`修饰符在指针中的应用,指针的运算(包括指针加减整数、指针相减和指针的大小比较),以及野指针的概念和如何规避野指针。最后,通过具体的代码示例帮助读者更好地理解和掌握指针的使用方法。
27 0
|
1天前
|
存储 算法 数据管理
C语言算法复杂度
【10月更文挑战第20天】
C语言算法复杂度
|
6天前
|
C语言
【c语言】指针就该这么学(3)
本文介绍了C语言中的函数指针、typedef关键字及函数指针数组的概念与应用。首先讲解了函数指针的创建与使用,接着通过typedef简化复杂类型定义,最后探讨了函数指针数组及其在转移表中的应用,通过实例展示了如何利用这些特性实现更简洁高效的代码。
10 2
|
6天前
|
C语言
如何避免 C 语言中的野指针问题?
在C语言中,野指针是指向未知内存地址的指针,可能引发程序崩溃或数据损坏。避免野指针的方法包括:初始化指针为NULL、使用完毕后将指针置为NULL、检查指针是否为空以及合理管理动态分配的内存。
|
6天前
|
C语言
C语言:哪些情况下会出现野指针
C语言中,野指针是指指向未知地址的指针,通常由以下情况产生:1) 指针被声明但未初始化;2) 指针指向的内存已被释放或重新分配;3) 指针指向局部变量,而该变量已超出作用域。使用野指针可能导致程序崩溃或不可预测的行为。
|
13天前
|
存储 C语言
C语言32位或64位平台下指针的大小
在32位平台上,C语言中指针的大小通常为4字节;而在64位平台上,指针的大小通常为8字节。这反映了不同平台对内存地址空间的不同处理方式。
|
12天前
|
存储 算法 C语言
C语言:什么是指针数组,它有什么用
指针数组是C语言中一种特殊的数据结构,每个元素都是一个指针。它用于存储多个内存地址,方便对多个变量或数组进行操作,常用于字符串处理、动态内存分配等场景。
|
13天前
|
存储 C语言
C语言指针与指针变量的区别指针
指针是C语言中的重要概念,用于存储内存地址。指针变量是一种特殊的变量,用于存放其他变量的内存地址,通过指针可以间接访问和修改该变量的值。指针与指针变量的主要区别在于:指针是一个泛指的概念,而指针变量是具体的实现形式。
|
13天前
|
C语言
C语言指针(3)
C语言指针(3)
10 1
|
13天前
|
C语言
C语言指针(2)
C语言指针(2)
11 1

热门文章

最新文章