Doodle, doodle, pointer to the advanced bus to the terminal 🚏 la
In this station, we will learn the callback function, the use of qsort and the simulation implementation
1. Callback function
definition:
A callback function is a function called through a function pointer. If you pass the pointer (address) of a function as a parameter to another function, when the pointer is used to call the function it points to, we say it is a callback function. The callback function is not called directly by the implementer of the function, but by another party when a specific event or condition occurs, which is used to respond to the event or condition.
In the last blog Function pointer array In, I mentioned the code of a calculator
Here we can use our callback function to call the calculation function through a new calc function, which also achieves the purpose of avoiding the repetition of switch/case statements
However, the focus of our study today is not here, but a new function: qsort
2.qsort function
qsort function is also called quick sort function
2.1 void * pointer
void* p = &a;
- void * is a pointer that has no type and no specific type
- The pointer variable of void * can store any type of address
- The pointer of void * cannot be dereferenced directly
- The pointer of void * cannot add or subtract integers directly
After knowing this, let's take a look qsort function Definition of
2.2qsort function definition
void qsort (void* base, size_t num, size_t size,
int (*compar)(const void*,const void*));
What do these parameters mean?
-
void*base is the starting address of the data to be sorted
-
size_t num is the number of data to be sorted
-
size_t size is the size of each data in the data to be sorted
siez_t is specially designed for the return value of sizeof function
It is an unsigned integer
-
Int (* compare) (const void *, const void *) is a function pointer
The parameters of this function are (const void*,const void *), and the return value is int
In the application of qsort, we need to write such a compar e function to judge who is big and who is small
The qsort library function specifies the compar function as follows:
- When P1 > P2, the number of > 0 is returned
- Return 0 when p1=p2
- When P1 < P2, the number of < 0 is returned
Why compare pointers of void * type used by functions?
Because the qsort function does not know what type of data you need to sort, but as users, we know the data type to be sorted and how to compare the data to be sorted. At this time, we can force the type conversion of void * pointer to the required pointer!
2.3 using qsort function to sort int/char
First, we create an integer array to be sorted, and fill the parameters into the qsort function according to the definition of the qsort function
int main()
{
int arr[10] = { 3,4,7,9,0,1,2,5,8,6 };
int sz = sizeof(arr) / sizeof(arr[0]);
int* ptr = arr;//This can be replaced by arr directly
qsort(ptr, sz, sizeof(arr[0]), cmp_int);
return 0;
}
Next, we need to write this cmp_int function, used to determine the size of two integers
Then write the function name to qsort
//Write a function to compare integers
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
After running, you can see that the data has been reordered in ascending order!
If you want to sort in descending order, just swap e1 and e2 in the comparison function parameters
Try sorting char character types again!
//Compare characters
int cmp_char(const void* e1, const void* e2)
{
char a = *(char*)e1;
char b = *(char*)e2;
if (a == b)
return 0;
else if (a > b)
return 1;
else
return -1;
}
int main()
{
char arr1[5] = { 'd','i','a','c','k'};
int sz1 = sizeof(arr1) / sizeof(arr1[0]);
int* pc = arr1;
qsort(pc, sz1, sizeof(arr1[0]), cmp_char);
for(int i = 0; i < sz1; i++)
{
printf("%c ", arr1[i]);
}
printf("\n");
return 0;
}
2.4 sorting structures with qsort
Define a structure whose contents represent name, age and grade respectively
struct Stu
{
char name[20];
int age;
float score;
};
The structure has three types of data: char, int and float. We need to write three corresponding sorting functions
//Ranking score
int cmp_stu_by_socre(const void* e1, const void* e2)
{
if (((struct Stu*)e1)->score > ((struct Stu*)e2)->score)
{
return 1;
}
else if (((struct Stu*)e1)->score < ((struct Stu*)e2)->score)
{
return -1;
}
else
{
return 0;
}
}
//Sort by age
int cmp_stu_by_age(const void* e1, const void* e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
//Sort by name
int cmp_stu_by_name(const void* e1, const void* e2)
{ //Compare strings with strcmp function
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
Write another function to print structure variables
void print_stu(struct Stu arr[], int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s %d %.2f\n", arr[i].name, arr[i].age, arr[i].score);
}
printf("\n");
}
Finally, the structure type is defined in the main function and written into the qsort function
int main()
{
struct Stu arr[] = { {"zhangsan",20,87.5f},{"lisi",22,99.0f},{"wangwu", 10, 68.5f},{"niuyeye",30,95.0f} };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);
print_stu(arr,sz);
return 0;
}
You can see that our data has been sorted by name!
3. Simulate the implementation of qsort function
So, what is the principle of qsort function?
We've written about sorting integers before Bubble sorting
The principle is to compare the element a and the next element of a in the array. If a is greater than a+1, they will be interchanged
void bubble_sort(int arr[], int sz)//The formal parameter arr is essentially a pointer
{
//Determine the number of trips
int i = 0;
for (i = 0; i < sz; i++)
{
//Bubble sort
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1] )
{
//exchange
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
Is there any way to rewrite bubble sorting into a general sorting function?
reflection:
- When bubble sorting, the int type is used. The int type is 4 bytes. Data types smaller than 4 bytes cannot be sorted
- The size of struct types is not necessarily an integer multiple of 4, nor can they be sorted by int
- Char type is 1 byte. Can all types be changed through char type?
Of course, the answer is yes!
In the previous pointer learning, we learned that although both char * and int * pointers occupy 4 bytes, char * can only access 1 byte of data.
We can use the char * pointer to exchange data byte by byte. Can't we exchange an int type four times? Similarly, you can also exchange other types of data through multiple visits of char *!
Since the qsort function is simulated, the parameters of the function should be the same as qsort
Directly change the qsort function to my_qsort, open the whole!
Using the basic framework of bubble sorting, we can write the following code
//Analog implementation of qsort
void my_qsort(void* base, int sz,int width, int(*cmp)(const void* e1, const void* e2))
{
for (int i = 0; i < sz - 1; i++)
{
for (int j = 0; j < sz - i - 1; j++)
{
if (cmp((char*)base + j * width , (char*)base + (j + 1) * width)>0)
{
my_swap((char*)base + j * width, (char*)base + (j+1) * width ,width);
}
}
}
}
You may feel confused about the sentences in if. Don't worry, look at the picture!
cmp is a callback function, which uses the function pointer to call the comparison function
Then write a swap function to realize byte exchange
//Access one by one with a pointer of type char
void my_swap(char* e1, char* e2,int sz)
{
//sz is the width of the data to be sorted: width
for (int k = 0; k < sz; k++)
{
char tmp = *e1;
*e1 = *e2;
*e2 = tmp;
e1++;
e2++;
}
}
Test it, and the success is sorted according to the score!
epilogue
The advanced journey of the pointer will come to a successful end here! Does it feel full of harvest?
Friends who have spare power in learning can take a look at this kind of pointer written test questions 👉 Point me
Stop, get off! 🚍