@[TOC]
前言:
博主实力有限,博文有什么错误,请你扶正 |
---|
qsort内部是使用快排法 对缓冲区(数组)进行排序,因博主目前对快排法不了解,因此本文使用选择法 复写qsort |
qsort 可以任意数组排序,结构体数组也可以,这其中的原因是 依次交换2元素所占内存中字节 的内容 |
![]() |
思维导图
函数作用:
- 对缓冲区进行快速排序
参数分析:
函数原型
void qsort( void base, size_t num, size_t width,int(__cdecl compare )(const void elem1, const void elem2 ) )
1. void * base
void *
- 是无类型指针,可以接受任何类型的指针的传入
- 指针进行运算时必须明确其类型,但是void* 为无类型,因此在函数内部需要对其进行强制类型转换,以满足运算要求
base
接受传入的缓冲区的首地址
2.size_t num
- num接受要排序缓冲区数据的数量
- 既然接受数量,那么我们就可以对数组中
部分元素
进行排序,这在后面的对通讯录
排序很有意义
3.size_t width
- qsort 是通过内存中的单一字节进行交换数组元素,但是通过字节交换,必然需要知道数组元素的大小。
4.int(__cdecl compare)(const void elem1, const void * elem2)
- 参数类型 函数指针类型,因此必然需要回调函数 ,而回调函数的实现方是我们,我们暂且称这个回调函数为种子
- 回调函数内部是 比较2元素的大小
- 回调比较元素后,然后返回以下值之一:
返回值描述
- 这种类型的返回值描述,qsort默认是==递增==排序,而要想==递减==排序,
![]()
排序结构体代码
初始化结构体函数
void ININ_Date(struct peo * pc)//对数组初始化
{
assert(pc);//防止传入NULL指针
for (size_t i = 0; i < MAX; i++)
{
printf("请输入名字:");
scanf("%s", (pc+i)->name);
printf("请输入年龄:");
scanf("%d", &((pc + i)->age));//scanf是跳过地址进行赋值的,因此需要&
printf("请输入性别:");
scanf("%s", (pc + i)->sex);
printf("请输入学号:");
scanf("%s", (pc + i)->id);
printf("\n");
}
}
打印结构体函数
void show(struct peo * pc)//打印数据
{
assert(pc);//防止传入NULL指针
printf("%20s\t %10s\t %10s\t %10s\n", "name", "age", "sex", "id");
for (size_t i = 0; i < MAX; i++)
{
printf("%20s\t %10d\t %10s\t %10s\n", (pc+ i)->name,
(pc + i)->age, (pc + i)->sex, (pc + i)->id);
}
}
种子
因为再排序数组时存在同名情况,因此需要2个比较元素的种子
int compare1(const void* e1, const void* e2)//种子1 比较名字
//比较结构体2元素中成员 名字
{
assert(e1 && e2);//防止传入NULL指针
return strcmp(((struct peo*)e1)->name, ((struct peo*)e2)->name);
}
int compare2(const void* e1, const void* e2)//种子2 比较学号
{
assert(e1 && e2);
return strcmp(((struct peo*)e1)->id, ((struct peo*)e2)->id);
}
交换元素函数
void swap(void* e1,void *e2 ,size_t width)//交换2元素所占内存字节中的内容
{
assert(e1 && e2);
for (size_t i = 0; i < width; i++)//依次交换e1,e2中的字节内容
{
unsigned char tmp = *((unsigned char*)e1+i);
*((unsigned char*)e1+i) = *((unsigned char*)e2+i);
*((unsigned char*)e2 + i) = tmp;
}
}
my_sqort
void my_qsort(void* base,
size_t num,
size_t width,
int (*compare)(const void* elem1, const void* elem2))
{
assert(base && compare);//防止传入NULL指针
//选择法排序数组
for (size_t i = 0; i < num - 1; i++)
{
size_t min = i;
for (size_t j = i + 1; j < num; j++)
{
//因为char* 指针在加一时通过一个字节,
// 但是结构体指针加一跳过 width个字节,
//因此需要j*width,min*width
//来获得2个不同结构体元素首地址
if (compare1((char*)base + j * width, (char*)base + min * width )< 0)
{
min = j;
}//一旦同名就比较学号
else if(compare1((char*)base + j * width, (char*)base + min * width)==0)
{
if (compare2((char*)base + j * width, (char*)base + min * width) < 0)
{
min = j;
}
}
}
if (min != i)//交换2元素
{
swap((char*)base + i * width, (char*)base+min * width,width);
}
}
}
全部代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
//程序通过qsort 通过名字对结构体数组继续排序
//但是对于同名的情况,只需要比较学号就行,因此设置2个种子:compare1,compare2
enum cut//存放全部常量
{
MAX=6,
Name_Max = 20,
Sex_Max = 20,
Id_Max = 100
};
struct peo
{
char name[Name_Max];
int age;
char sex[Sex_Max];
char id[Id_Max];
};
void ININ_Date(struct peo * pc)//对数组初始化
{
assert(pc);//防止传入NULL指针
for (size_t i = 0; i < MAX; i++)
{
printf("请输入名字:");
scanf("%s", (pc+i)->name);
printf("请输入年龄:");
scanf("%d", &((pc + i)->age));//scanf是跳过地址进行赋值的,因此需要&
printf("请输入性别:");
scanf("%s", (pc + i)->sex);
printf("请输入学号:");
scanf("%s", (pc + i)->id);
printf("\n");
}
}
void show(struct peo * pc)//打印数据
{
assert(pc);//防止传入NULL指针
printf("%20s\t %10s\t %10s\t %10s\n", "name", "age", "sex", "id");
for (size_t i = 0; i < MAX; i++)
{
printf("%20s\t %10d\t %10s\t %10s\n", (pc+ i)->name,
(pc + i)->age, (pc + i)->sex, (pc + i)->id);
}
}
int compare1(const void* e1, const void* e2)//种子1 比较名字
//比较结构体2元素中成员 名字
{
assert(e1 && e2);//防止传入NULL指针
return strcmp(((struct peo*)e1)->name, ((struct peo*)e2)->name);
}
int compare2(const void* e1, const void* e2)//种子2 比较学号
{
assert(e1 && e2);
return strcmp(((struct peo*)e1)->id, ((struct peo*)e2)->id);
}
void swap(void* e1,void *e2 ,size_t width)//交换2元素所占内存字节中的内容
{
assert(e1 && e2);
for (size_t i = 0; i < width; i++)//依次交换e1,e2中的字节内容
{
unsigned char tmp = *((unsigned char*)e1+i);
*((unsigned char*)e1+i) = *((unsigned char*)e2+i);
*((unsigned char*)e2 + i) = tmp;
}
}
void my_qsort(void* base,
size_t num,
size_t width,
int (*compare)(const void* elem1, const void* elem2))
{
assert(base && compare);//防止传入NULL指针
//选择法排序数组
for (size_t i = 0; i < num - 1; i++)
{
size_t min = i;
for (size_t j = i + 1; j < num; j++)
{
//因为char* 指针在加一时通过一个字节,
// 但是结构体指针加一跳过 width个字节,
//因此需要j*width,min*width
//来获得2个不同结构体元素首地址
if (compare1((char*)base + j * width, (char*)base + min * width )< 0)
{
min = j;
}//一旦同名就比较学号
else if(compare1((char*)base + j * width, (char*)base + min * width)==0)
{
if (compare2((char*)base + j * width, (char*)base + min * width) < 0)
{
min = j;
}
}
}
if (min != i)//交换2元素
{
swap((char*)base + i * width, (char*)base+min * width,width);
}
}
}
int main ()
{
struct peo date[MAX];
ININ_Date(date);
show(date);
//排序:
my_qsort(date, MAX, sizeof(struct peo), compare1);
show(date);
return 0;
}
结果展示
总结
1.理解qsort的关键就是 理解交换数据时的内存角度,这个非常重要!!!!!!!!!! |
---|
2. 在编代码时明确,只有确定类型的指针,指针才能进行相关运算 |
3.同名情况, 比较学号这个很好的。为后面通讯录垫基础 |