Hsian Studio

兩個最重要的資料結構就是「搜尋」和「排序」了，所以看過資料結構的人，想必知道快速排序算是在排序中最好用的，而二元搜尋也是一樣，但是實做的過程往往很複雜，但是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;
}