C++|从qsort函数了解void类型和回调函数

我们知道，数组排序中的“快速排序”有较高的时间效率，为此C函数库stdlib提供了此函数，并能够对整形、浮点型、字符串及至结构体中的某个关键字实现排序。我们知道，C语言是强类型语言，且没有C++的函数重载和模板机制，那怎样实现这种类型泛化的操作呢？C用void*指针和函数指针实现回调函数来达成。这也是此函数的参数看起来特别复杂的原因：

void qsort(
		 void *base, 
		 size_t nitems, 
		 size_t size, 
		 int (*compar)(const void *, const void*))

void *base：类型为void*，相当于泛型，指向要排序的数组的第一个元素的指针。

nitems：数组中元素的个数，在数组指针中无法内含元素个数，需要另外的参数提供。

size：因为数据指针提供的是void*类型，需要另外的参数来提供数组中每个元素的大小，以字节为单位。

int compar(const void *p1, const void *p2);

compar是一个函数指针，注意函数参数的类型是void*，可以是各种基本类型、字符串、结构体的某个关键字，用来比较两个元素的函数，即函数指针（回调函数）

如果compar返回值小于0（< 0），那么p1所指向元素会被排在p2所指向元素的前面；

如果compar返回值等于0（= 0），那么p1所指向元素与p2所指向元素的顺序不确定；

如果compar返回值大于0（> 0），那么p1所指向元素会被排在p2所指向元素的后面。

实例：

#include <stdio.h>
#include <stdlib.h>
#define NUM 40
void fillarray(double ar[], int n);
void showarray(const double ar[], int n);
int mycomp(const void * p1, const void * p2);
int main(void)
{
 double vals[NUM];
 fillarray(vals, NUM);
 puts("Random list:");
 showarray(vals, NUM);
 qsort(vals, 	NUM, sizeof(double), mycomp);
 puts("\nSorted list:");
 showarray(vals, NUM);
	system("pause");
 return 0;
}
void fillarray(double ar[], int n)
{
 int index;
 
 for( index = 0; index < n; index++)
 ar[index] = (double)rand()/((double) rand() + 0.1);
}
void showarray(const double ar[], int n)
{
 int index;
 
 for( index = 0; index < n; index++)
 {
 printf("%9.4f ", ar[index]);
 if (index % 6 == 5)
 putchar('\n');
 }
 if (index % 6 != 0)
 putchar('\n');
}
/* sort by increasing value */
int mycomp(const void * p1, const void * p2)
{
 /* need to use pointers to double to access values */
 const double * a1 = (const double *) p1;
 const double * a2 = (const double *) p2;
	return *(int*)a-*(int*)b; 
 if (*a1 < *a2)
 return -1;
 else if (*a1 == *a2)
 return 0;
 else
 return 1;
}

各种类型回调函数的写法

1 整形

int comp(const void*a,const void*b)
{
return *(int*)a-*(int*)b;//由小到大排序
//return *(int *)b - *(int *)a; 为由大到小排序。
}

2 浮点型

int mycomp(const void * p1, const void * p2)
{
 const double * a1 = (const double *) p1;
 const double * a2 = (const double *) p2;
	return *(int*)a-*(int*)b; 
 if (*a1 < *a2)
 return -1;
 else if (*a1 == *a2)
 return 0;
 else
 return 1;
}

3 对一个整型二维数组按行的第一个元素进行排序，要求整行一起移动交换。

qsort(a,1000,sizeof(int)*2,comp);//两列
int comp(const void*a,const void*b)
{
return((int*)a)[0]-((int*)b)[0];
}

4 字符串

int Comp(const void*p1,const void*p2)
{
return strcmp((char*)p2,(char*)p1);
}

5 按结构体中某个关键字排序

structNode
{
double data;
int other;
}s[100];
int Comp(constvoid*p1,constvoid*p2)
{
return(*(Node*)p2).data>(*（Node*）p1).data?1:-1;
}

5 按结构体中多个关键字排序（对结构体多级排序）[以二级为例]

struct Node
{
int x;
int y;
}s[100];
//按照x从小到大排序，当x相等时按y从大到小排序
int Comp(const void*p1,const void*p2)
{
struct Node*c=(Node*)p1;
struct Node*d=(Node*)p2;
if(c->x!=d->x) returnc->x-d->x;
else return d->y-c->y;
}

6 对结构体中字符串进行排序

struct Node
{
int data;
char str[100];
}s[100];
//按照结构体中字符串str的字典序排序
int Comp(const void*p1,const void*p2)
{
return strcmp((*(Node*)p1).str,(*(Node*)p2).str);
}
qsort(s,100,sizeof(s[0]),Comp);

－End－