C语言—qsort()与bsearch()

Myth丶恋晨 2022-05-21 22:11 207阅读 0赞

## C语言—qsort()与bsearch() ##

### qsort函数在一个数组中以升序的方式对数据进行排序。由于它是和类型无关的，所以你可以使用qsort排序任意类型的数据，只是数组中元素的长度是固定的。 ###

### bsearch函数在一个已经排好序的数组中用二分法查找一个特定的元素。如果数组尚未排序，其结果是未定义的。 ###

### qsort()与bsearch()都包含在 < stdlib.h >头文件中 ###

--------------------

## 1.qsort() ##

**函数原型：** void qsort(void \*base,size\_t n\_elements, size\_t el\_size,  
int (*compare)(void const*  , void const \*) );  
第一个参数指向需要排序的数组，第二个参数表示数组中元素的数目，第三个参数指定每个元素的长度(以字符为单位)，第四个参数是一个**函数指针**，对需要排序的元素类型进行比较。  
下面举个例子：

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    int n;
    
    typedef struct{
        char key[10];
        int data;
    }Record;
    
    int Compare(void const *a,void const *b)
    {
        return strcmp( ((Record *)a)->key, ((Record *)b)->key);
    }
    
    int n_compare(void const *a,void const *b)
    {
        return ((Record *)a)->data - ((Record *)b)->data;
    }
    
    void Input(Record array[])
    {
        printf("请输入数据个数：");
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
            printf("key:");
            scanf("%s",array[i].key);
            printf("data:");
            scanf("%d",&array[i].data);
        }
    }
    
    void Print(Record array[])
    {
        for(int i = 0; i < n; i++)
        {
            printf("key:%s   ",array[i].key);
            printf("data:%d\n",array[i].data);
        }
    }
    
    int main()
    {
        Record array[50];
        Input(array);
        qsort(array,n,sizeof(Record),n_compare);
        Print(array);
        return 0;
    }

**第四个参数(比较函数)返回值为整形：当a > b 时返回正数，当a = b 时返回0 , 当 a < b 时返回负数。qsort函数根据a ,b 成员元素的值进行比较来对数组元素进行排序。**  
同理：**待排序元素类型也可以是其他任意类型。**

--------------------

## 2.bsearch() ##

bsearch函数在一个已经排好序的数组中用二分法查找一个特定的元素。如果数组尚未排序，其结果是未定义的。  
**函数原型：** void bsearch(void const \*key,void const \*base, size\_t n\_elements,  
size\_t el\_size, int (*compare)(void const*  , void const \* ) );  
第一个参数指向你需要查找的值，第二个参数指向查找所在的数组，第三个参数指定数组中元素的数目，第四个参数是每个元素的长度(以字符为单位)。最后一个参数是和qsort中相同的指向比较函数的指针。bsearch函数返回一个指向查找到的数组元素的指针。如果查找的值不存在则返回一个null指针。  
下面是一个例子：

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    int n;
    
    typedef struct{
        char key[10];
        int data;
    }Record;
    
    int Compare(void const *a,void const *b)
    {
        return strcmp( ((Record *)a)->key, ((Record *)b)->key);
    }
    
    int n_compare(void const *a,void const *b)
    {
        return ((Record *)a)->data - ((Record *)b)->data;
    }
    
    void Input(Record array[])
    {
        printf("请输入数据个数：");
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
            printf("key:");
            scanf("%s",array[i].key);
            printf("data:");
            scanf("%d",&array[i].data);
        }
    }
    
    int main()
    {
        Record array[50];
        Record key;
        Record *ans;
        Input(array);
        printf("要查找：");
        scanf("%d",&key.data);
        qsort(array,n,sizeof(Record),n_compare);
        ans = (Record *)bsearch(&key,array,n,sizeof(Record),n_compare);
        if(ans == NULL)
        {
            printf("所查找的值不存在！\n");
            return 0;
        } 
        printf("%s   %d",ans->key,ans->data);
        return 0;
    }

**因为要求数组有序，所以在查找前还需调用qsort()进行排序。因为返回值是void \*类型，即空指针类型，所以在赋值时需要强制类型转换。**