文章目录
- 前言：
- 思维导图
- 函数作用：
- 参数分析:
- 函数原型
- 1. void * base
- 2.size_t num
- 3.size_t width
- 4.int(__cdecl* compare)(const void * elem1, const void * elem2)
- 排序结构体代码
- 初始化结构体函数
- 打印结构体函数
- 种子
- 交换元素函数
- my_sqort
- 全部代码
- 结果展示
- 总结
前言：
| 博主实力有限，博文有什么错误，请你扶正 |
|---|
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.同名情况， 比较学号这个很好的。为后面通讯录垫基础 |