C語言——深入理解指針（三）

1.回調函數是什么？

首先我們來回顧一下函數的直接調用：

在這里插入圖片描述
而回調函數就是通過函數指針調用的函數。我們將函數的指針（地址）作為參數傳遞給另一個函數，當這個指針被用來調用其所指向的函數時，被調用的函數就是回調函數。

2.qsort函數

quick sort簡稱qsort，是C語言中提供的一個排序函數，是基于快速排序算法思想的一種排序算法。
其優點有：現成的排序算法可直接使用；而且大部分情況下效率都是比冒泡排序高的；qsort函數可以排序任意類型的數據

function
在這里插入圖片描述

void qsort (void* base,//指針，指向了被排序數組的第一個元素size_t num, // 這里是base指向的被排序數組的元素個數size_t size,//這里是base指向的被排序數組的元素大小（長度），單位是字節int (*compar)(const void*,const void*)//函數指針，指針指向的函數是用來比較被排序數組中的兩個元素的);

在這里插入圖片描述
該函數排序默認為升序，希望為降序，只需將參數p1，p2順序反過來即可

3.qsort函數的使用

qsort函數對整型數組的排序：

我們在使用qsort函數排序時，常需要自己寫一個比較的邏輯，來比較整形數據的大小，如我們可以在這里寫一個int cmp_int(const void* p1,const void* p2)函數指針，而指針指向的函數是用來比較被排序數組中的兩個元素的，里面的p1,p2則分別指向一個整型變量，然后qsort函數根據返回的結果進行排序。整體整合下來如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//打印
void print_arr(int arr[], int sz)
{int i = 0;for (i = 0;i < sz;i++){printf("%d ", arr[i]);}printf("\n");
}
//寫的是升序，若想改為降序，只需改變p1，p2的位置
int cmp_int(const void* p1,const void* p2)//const修飾函數參數，表示參數在函數體內不能被修改
{if (*(int*)p1 > *(int*)p2)//強制類型轉換為整型return 1;else if (*(int*)p1 < *(int*)p2)return -1;elsereturn 0;//根據qsort函數的排序邏輯，上面這一部分也可簡化為：return(*(int*)p1 - *(int*)p2);
}
void test()
{int arr[] = { 4,3,7,9,0,2,1,6 };int sz = sizeof(arr) / sizeof(arr[0]);print_arr(arr, sz);//打印排序前的數組//排序qsort(arr,sz,sizeof(arr[0]),cmp_int);print_arr(arr, sz);//打印排序后的數組
}
int main()
{test();return 0;
}

運行結果：
在這里插入圖片描述

qsort函數對結構體數據的排序：

1.按照年齡比較，只需比較整形數據的大小：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Stu
{char name[30];int age;
};
void print_stu(struct Stu arr[], int sz)
{int i = 0;for (i = 0;i < sz;i++){printf("%s:%d\n", arr[i].name, arr[i].age);}
}
int cmp_stu_by_age(const void* p1, const void* p2)
{return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;
}
void test()
{struct Stu arr[] = { {"Jack",28},{"Rose",25},{"liming",19} };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);print_stu(arr, sz);
}
int main()
{test();return 0;
}

運行結果：
在這里插入圖片描述

2.按照名字比較，這里注意比較的是字符串的大小，注意這里不能使用> >= < <= == !=，需要使用strcmp()函數：

//按照名字比較
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Stu
{char name[30];int age;
};
//p1指向了一個結構體變量
//p2指向了一個結構體變量
void print_stu(struct Stu arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%s: %d\n", arr[i].name, arr[i].age);}printf("\n");
}
int cmp_stu_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}
void test()
{struct Stu arr[] = { {"zhangsan", 20},{"lisi", 38},{"wangwu", 18} };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);print_stu(arr, sz);
}
int main()
{test();return 0;
}

運行結果：
在這里插入圖片描述

4.qsort函數模擬實現

這里，依照qsort函數的邏輯，模擬實現一個底層邏輯為冒泡排序但可排序任意類型的數據的函數（即泛型編程）。

設計bubble_sort函數，只是底層算法和qsort函數不一樣，但其參數可模擬qsort函數，第一個參數指向數組首元素的指針類比qsort我們記為base，同理第二個參數為size_t sz,第三個參數記為size_t width，第四個參數我們要寫的是函數指針，因為不知道將要比較什么類型的數據，所以用void修飾取出的元素，而函數的返回類型因為知曉是整型則為int即int (cmp)(const void p1, const void* p2)
和冒泡排序的底層邏輯一樣，首先確定外層比較的趟數，然后內層決定趟內部比較的對數。外層只需要算出有幾個元素來確定需要幾趟，那么內層比較該如何比較？該如何確定一趟比較的對數呢？這里就不同于冒泡排序了
這里需要將if(arr[j]>arr[j+1])修改，因為不知道類型，交換的時候并不僅僅是簡單的比較整型元素的大小，但是由于此時已經知道比較方法cmp()，所以只需調用一下cmp()，現在需要將arr[j]和arr[j+1]這兩個相鄰元素的地址傳到cmp（）中一個給p1，一個給p2。現在只知道base指向數組首元素的地址，那該如何越過中間的元素獲取j和j+的地址呢？如下圖：

下面一個問題就是如何交換這兩個元素。由于不能將它們整體交換，只知道這兩個元素的地址，所以可以將它們轉換為字節來進行交換，假設一個元素占四個字節，則可將第一個字節與第一個字節交換，以此類推從而實現元素的交換。寫一個Swap函數，其參數我們則需要傳兩個元素的地址(char*)base + j * width, (char*)base + (j + 1) * width和元素的寬度width，然后在交換函數中，使用一個for循環，讓其對應字節元素相交換就實現交換了。
好，現在我們將其整合下來：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void print_arr(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}
int cmp_int(const void* p1, const void* p2)
{return (*(int*)p1 - *(int*)p2);
}
void Swap(char* buf1, char* buf2, size_t width)//交換 
{int i = 0;char tmp = 0;for (i = 0; i < width; i++){tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void bubble_sort(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i = 0;for (i = 0; i < sz - 1; i++){int j = 0;for (j = 0; j < sz - 1 - i; j++){if(cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}
void test()
{int arr[] = { 3,1,5,8,7,9,2,4,6,0 };int sz = sizeof(arr) / sizeof(arr[0]);print_arr(arr, sz);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);print_arr(arr, sz);
}
int main()
{test();  return 0;
}

運行結果：
在這里插入圖片描述
上面已經可以完全排序整型數據了，現在我們來測試排序結構體數據，排序的思想一樣，繼續用bubble_sort（）函數。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Stu
{char name[30];int age;
};
void print_stu(struct Stu arr[], int sz)
{int i = 0;for (i = 0;i < sz;i++){printf("%s:%d\n", arr[i].name, arr[i].age);}
}
int cmp_stu_by_age(const void* p1, const void* p2)
{return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;
}
void Swap(char* buf1, char* buf2, size_t width)//交換 
{int i = 0;char tmp = 0;for (i = 0; i < width; i++){tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void bubble_sort(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i = 0;for (i = 0; i < sz - 1; i++){int j = 0;for (j = 0; j < sz - 1 - i; j++){if(cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}
void test()
{struct Stu arr[] = { {"Jack",28},{"Rose",25},{"liming",19} };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);//bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);print_stu(arr, sz);
}
int main()
{test();
}