qsort 与bsearch

╰半夏微凉° 2022-08-13 14:58 217阅读 0赞

兩個最重要的資料結構就是「搜尋」和「排序」了，所以看過資料結構的人，想必知道快速排序算是在排序中最好用的，而二元搜尋也是一樣，但是實做的過程往往很複雜，但是std的標準函式庫已有提供給我們使用了，以下就來討論如何使用qsort和bsearch。

**※qsort函式**

*  void qsort( void \*buf, size\_t num, size\_t size, int (\*compare)(const void \*, const void \*));
 *  buf 是指向要排序陣列開頭的指標
 *  num 是資料的數量
 *  size 是每個元素的大小
 *  int (\*compare)(const void\*, const void\*) 是指向如何比較的函式指標

**※qsort使用(數字排序)**

> Example:
> 
> `#define size_of_ary(ary) sizeof(ary)/sizeof(*ary)`
> 
> `int main() {     int ints[] = {12,46,4,8,413,86,15,2,48,0,54,6};     qsort(ints, size_of_ary(ints), sizeof(int), int_comp);     return 0; } int int_comp(const void* a, const void* b) {     int* temp_a = (int*)a;     int* temp_b = (int*)b;     if (*temp_a < *temp_b)         return -1;     else if (*temp_a == *temp_b)         return 0;     else         return 1; }`

使用size\_of\_ary這個巨集可以算出陣列有多少個元素，對於compare這個函式指標，主要目的就是要告訴函式要怎麼去做比較，那個小那個大或是相等，才可以準確的去幫你排序出來，在compare這函式指標原型說要使用const void\*泛指標，主要目的是為了要讓所有的型別都可以支援，所以你可以自由的轉成int\*或是double\*所以實做compare函主第一個目的就是先轉型成你真正的型別。

**※qsort使用(字串排序)**

> Example:
> 
> `#define size_of_ary(ary) sizeof(ary)/sizeof(*ary)`
> 
> `int main() {     const char* color[] = {     "Red", "Blue", "Yellow", "Black", "Green", "Axz"     };     qsort(color, size_of_ary(color), sizeof(char*), my_compare);     return 0; } int my_compare(const void* a, const void* b) {     int ans;     const char** temp_a = (const char**)a;     const char** temp_b = (const char**)b;     ans = strcmp(*temp_a, *temp_b);     return ans; }`

這邊我想最大的問題，一定是看不懂const char\*\* temp\_a = (const char\*\*)a這是雙指標，但是為什麼要用雙指標呢？你可以改成單指標，但是我保證一定不能跑，因為其實你的color\[\]的每個元素都是一個char\*的指標，而對於const void\* a它的意思是指向color\[\]的每一個陣列元素，那意思不是為「const void\* a 指向char\*指向字串」嗎？所以const void\* a應該要轉型成const char\*\* a才正確。

**※bsearch 函式**

*  void \*bsearch(const void \*key,const void \*buf, size\_t num, size\_t size, int (\*compare)(const void \*, const void \*));
 *  key 要尋找的資料的指標
 *  buf 是指向要搜尋陣列開頭的指標
 *  num 元素的數量
 *  size 每個元素的大小
 *  int (\*compare)(const void\*, const void\*)指向如何比較的函式指標
 *  若找不到回傳NULL，否則回傳指向資料的指標

**※bsearch 使用(數字搜尋)**

> Example:
> 
> `#define size_of_ary(ary) sizeof(ary)/sizeof(*ary)`
> 
> `int main() {     int ints[] = {12,46,4,8,413,86,15,2,48,0,54,6};     int key = 8;     int* gets;     if ((gets = (int*)bsearch(&key, ints, size_of_ary(ints), sizeof(int), int_comp)))     {         printf("find int %d/n", *gets);     }     return 0; } int int_comp(const void* a, const void* b) {     int* temp_a = (int*)a;     int* temp_b = (int*)b;     if (*temp_a < *temp_b)         return -1;     else if (*temp_a == *temp_b)         return 0;     else         return 1; }`

和qsort不同的地方在於他需要傳入一個比較鍵值key的指標，而會回傳找到資料的指標，或是找不到回傳NULL所以可以透過if來判斷有沒有找到，以免對NULL做解參考(dereference)的動做。

**※bsearch 使用(字串搜尋)**

> Example:
> 
> `#define size_of_ary(ary) sizeof(ary)/sizeof(*ary)`
> 
> `int main() {     const char* color[] = {     "Red", "Blue", "Yellow", "Black", "Green", "Axz"     };     char* key = "Yellow";     char** find;     if ((find = (char**)bsearch(&key, color, size_of_ary(color), sizeof(char*), my_compare)))     {         printf("i find %s/n", *find);     }     return 0; } int my_compare(const void* a, const void* b) {     int ans;     const char** temp_a = (const char**)a;     const char** temp_b = (const char**)b;     ans = strcmp(*temp_a, *temp_b);     return ans; }`