qsort 与 bsearch 的魔力

ubuntuer

man qsort:
#include stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
                  int(*compar)(const void *, const void *));
参数说明如下：
base: 要排序的数组
nmemb: 数组中的元素数目  sizeof(array)/sizeof(array[0])
size: 每个数组元素占用内存空间，可使用sizeof(array[0])获得
compar: 比较两个数组元素的比较函数。本比较函数的第一个参数值小于、等于、大于第二参数值时，本比较函数的返回值应分别小于、等于、大于零。
函数：
int cmp(const void *a, const void *b)
如果a > b，返回>0
如果a == b, 返回0
如果a  b，返回0
这里的a和b的关系仅仅是逻辑上的，并不是值比较，所以排序的可以不仅仅是数字，还可以是字符。
bsearch函数声明如下：
void *bsearch(const void *key, const void *base, size_t *nelem,
size_t width, int(*fcmp)(const void *, const *));
参数的意思和qsort的差不多，区别在于：
1. qsort用来排序，bsearch用二分法来查找元素
2. bsearch中的base必须是升序排列的数组！！！
3. 如果数组里有重复的答案，则bsearch会返回其中一个的地址 （具体返回哪一个不确定）
4. bsearch有五个自变量，第一个是要找的东西，剩下的跟qsort一模一样
5. bsearch如果没找到所求则回传NULL ，否则回传该元素被找到的地址(void *)
c函数qsort()和bsearch()的用法
使用qsort()排序 并 用 bsearch（）搜索是一个比较常用的组合，使用方便快捷。
qsort 的函数原型是void __cdecl qsort ( void *base, size_t num, size_t width, int (__cdecl *comp)(const void *, const void* ) )
其中base是排序的一个集合数组，num是这个数组元素的个数，width是一个元素的大小，comp是一个比较函数。
比如：对一个长为1000的数组进行排序时，int a[1000]; 那么base应为a，num应为 1000，width应为 sizeof(int)，comp函数随自己的命名。
qsort(a,1000,sizeof(int ),comp);
其中comp函数应写为:
int comp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
是对一个二维数组的进行排序：
int a[1000][2]; 其中按照a[0]的大小进行一个整体的排序，其中a[1]必须和a[0]一起移动交换。
qsort(a,1000,sizeof(int)*2,comp);
int comp(const void *a,const void *b)
{
return ((int *)a)[0]-((int *)b)[0];
}
对字符串进行一个排序：
char a[1000][20];
qsort(a,1000,sizeof(char)*20,comp);
int comp(const void *a,const void *b
{
return strcmp((char *)a,(char *)b);
}
对一个结构体进行排序：
typedef struct str
{
char str1[11];
char str2[11];
}str,*stri;
str strin[100001]={0};
int compare(const void *a,const void *b)
{
return strcmp( ((str*)a)->str2 , ((str*)b)->str2 );
}
qsort(strin,total,sizeof(str),compare);
而关于bsearch() ,他和qsort的用法基本一样，只是他的返回值是一个指向找到的单位元素的一个指针，另外他多了一个参数，是一个指向查找元素的一个指针。
比如：从上面例子中的结构体数组中查找一个字符串：
str *locate;
char buffer[30]="abc";
locate=(str*)bsearch(buffer,strin,total,sizeof(str),com);
int com(const void *a,const void *b)
{
return strcmp( (char*)a, ((str*)b)->str2 );
}
可以大致比较两个函数的类似和差别。
eg1:
#include stdio.h>
#include stdlib.h>
#include unistd.h>
#include string.h>
#include assert.h>
static int
   cmpstringp(const void *p1, const void *p2)
  {
   /* The actual arguments to this function are "pointers to
      pointers to char", but strcmp() arguments are "pointers
      to char", hence the following cast plus dereference */
    return strcmp(* (char * const *) p1, * (char * const *) p2);
  }
  int
   main(int argc, char *argv[])
  {
   int j;
   assert(argc > 1);
   qsort(&argv[1], argc - 1, sizeof(char *), cmpstringp);
   
    for (j = 1; j  argc; j++)
               puts(argv[j]);
    exit(EXIT_SUCCESS);
  }
通过改变cmpstringp函数你就可以实现是升序还是降序排序了.
eg2:
   #include stdio.h>
       #include stdlib.h>
       #include string.h>
       struct mi {
            int nr;
            char *name;
       } months[] = {
            { 1, "jan" }, { 2, "feb" }, { 3, "mar" }, { 4, "apr" },
            { 5, "may" }, { 6, "jun" }, { 7, "jul" }, { 8, "aug" },
            { 9, "sep" }, {10, "oct" }, {11, "nov" }, {12, "dec" }
       };
       #define nr_of_months (sizeof(months)/sizeof(months[0]))
       static int compmi(const void *m1, const void *m2) {
            struct mi *mi1 = (struct mi *) m1;
            struct mi *mi2 = (struct mi *) m2;
            return strcmp(mi1->name, mi2->name);
       }
       int main(int argc, char **argv) {
            int i;
            qsort(months, nr_of_months, sizeof(struct mi), compmi);
            for (i = 1; i  argc; i++) {
                 struct mi key, *res;
                 key.name = argv;
                 res = bsearch(&key, months, nr_of_months,
                            sizeof(struct mi), compmi);
                 if (res == NULL)
                      printf("’%s’: unknown month\n", argv);
                 else
                      printf("%s: month #%d\n", res->name, res->nr);
            }
            return 0;
       }


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76292/showart_1871804.html