DSP

使用qsort()和bsearch()进行快速排序和折半查找

2019-07-13 18:56发布

站内文章 / DSP
15298 0 1691
使用提供的库函数qsort()和bsearch()，进行快速排序和折半查找。 同过对字符串的排序和查找，掌握对qsort()和bsearch()的使用。首先理解快速排序的算法，就是先设定关键字，以此为界进行划分，小的放前面，大的放后面，然后对着两拨进行同用的划分和排放，直至完成；折半查找就是先中间进行比较查找，再在符合的范围中间比较查找，直至完成。 使用这两个函数的需要注意的事项：函数参数的类型一定要匹配！ 使用快速排序示例：#include #include int compare(const void *a,const void *b); int main(void) { //int num[4] = {3,4,1,2}; char *str[3]; str[0] = "bit"; str[1] = "cout"; str[2] = "about";//字符串赋值 int i; for(i = 0;i < 3; i++) { printf("%s ",str[i]); } printf(" "); qsort(str ,3 ,sizeof(str[0]) ,compare);//函数的指针 for(i = 0;i < 3; i++) { printf("%s ",str[i]); } printf(" "); } int compare(const void *a,const void *b) { return strcmp(*( char** )a ,*( char** )b); } 使用折半查找的示例： /* **功能：使用折半法查找关键字，使用提供的bsearch()库函数进行查找 **函数：void* bsearch (const void*, const void*, int, int, int (*)(const void*, const void*)); **参数：匹配参数，数组，数组的长度，数组元素内存大小，比较函数 **注释：只有先排序，才有查找 ，参数的类型要一致 */ #include #include int compare(const void *a,const void *b); int main(void) { //int num[4] = {3,4,1,2}; char **foundp = NULL; char *str[3]; char *key = "about"; str[0] = "bit"; str[1] = "cout"; str[2] = "about";//字符串赋值 int i; for(i = 0;i < 3; i++) { printf("%s ",str[i]); } printf(" "); qsort(str ,3 ,sizeof(str[0]) ,compare);//快速排序 for(i = 0;i < 3; i++) { printf("%s ",str[i]); } printf(" "); foundp = (char*)bsearch(&key,str,3,sizeof(str[0]),compare);//折半查找 ，&key和str的类型必须一致 if(foundp) printf("%s ",*foundp); else printf("NOT FOUND! "); } int compare(const void *a,const void *b) { return strcmp(*( char** )a ,*( char** )b); }
充分利用好提供的库函数，能省不少事，“站在巨人的肩膀上才能看到更远”！