Вперед Назад Содержание

15. Поиск и Сортировка

Эта глава описывает функции для поиска и сортировки массивов произвольных объектов. Вы определяете соответствующую функцию сравнения, которую нужно применить как аргумент, наряду с размером объектов в массиве и общим числом элементов.

15.1 Определение Функции Сравнения

Чтобы использовать библиотечные функции сортировки массива, Вы должны описать, как сравнить элементы массива.

Чтобы сделать это, Вы обеспечиваете функцию сравнения, для сравнения двух элементов массива. Библиотека вызовет эту функцию, передавая как указатели на аргументы два элемента массива, которые нужно сравнить. Ваша функция сравнения должна возвратить значение как strcmp (см. Раздел 5.5 [Сравнение СТРОКИ/МАССИВА]): отрицательное, если первый аргумент - "меньше" чем второй, нуль, если они "равны", и положительное если первый аргумент "больше".

Вот пример функции сравнения, которая работает с массивом чисел типа double:

                int
                compare_doubles (const double *a, const double *b)
                {
                        return (int) (*a - *b);
                }
Заглавный файл " stdlib.h " определяет имя для типа данных функций сравнения. Этот тип - расширение GNU.

    int comparison_fn_t (const void *, const void *);

15.2 Функция Поиска в Массиве

Чтобы искать в сортируемом массиве элемент, соответствующий ключу, используйте bsearch функцию. Прототип для этой функции находится в заглавном файле " stdlib.h ".

    void * bsearch (const void *key, const void *array, size_t  count, size_t size, comparison_fn_t compare)
Bsearch функция ищет в сортируемом массиве объект, который является эквивалентным key. Массив содержит count элементов, каждый из которых имеет байты размера sise.

Возвращаемое значение - указатель на соответствующий элемент массива, или пустой указатель, если никакое соответствие не найдено. Если массив содержит больше чем один подходящий элемент, неопределено который же возвращается.

Эта функция получила имя из предположения, что она выполнена, используя двоичный алгоритм поиска.

15.3 Функция Сортировки Массива

Для сортировки массива, используюя произвольную функцию сравнения, используйте qsort функцию. Прототип для этой функции находится в " stdlib.h ".

    void qsort (void *array, size_t count, size_t size, comparison_fn_t compare)
Qsort функция сортирует заланный массив. Массив содержит count элементов, каждый из которых имеет размер size.

Функция compare используется, чтобы выполнить сравнение на элементах массива. Эта функция вызывается с двумя аргументами указателями и должна возвратить целое число меньше , равное, или больше нуля, если первый аргумент меньше , равен, или больше чем второй аргумент.

Предупреждение: если, два объекта сравниваются как равные, их порядок после сортировки, непредсказуем. То есть сортировка не устойчива. Она может делать различие, когда сравнение рассматривает только часть элементов. А также, два элемента с тем же самым ключом сортировки могут отличиться в других отношениях.

Вот простой пример сортировки массива double значений в числовом порядке используя функцию сравнения, определенную выше (см. Раздел 15.1 [Функции Сравнения]):

        {
                double *array;
                int size;
                . . .
                qsort(array,size,sizeof(double),compare_doubles);
        }
Qsort функция получила имя из предположения, что она была первоначально выполнена, используя алгоритм "быстрой сортировки".

15.4 Пример Поиска и Сортировки

Вот пример, показывающий использование qsort и bsearch с массивом структур. Объекты в массиве сортируются, сравнивнением их name полей функцией strcmp.

                #include <stdlib.h>
                #include <stdio.h>
                #include <string.h>
                struct critter
                {
                        const char *name;
                        const char *species;
                };
                struct critter muppets[] =
                {
                        {"Kermit", "frog"},
                        {"Piggy", "pig"},
                        {"Gonzo", "whatever"},
                        {"Fozzie", "bear"},
                        {"Sam", "eagle"},
                        {"Robin", "frog"},
                        {"Animal", "animal"},
                        {"Camilla", "chicken"},
                        {"Sweetums", "monster"},
                        {"Dr. Strangepork", "pig"},
                        {"Link Hogthrob", "pig"},
                        {"Zoot", "human"},
                        {"Dr. Bunsen Honeydew", "human"},
                        {"Beaker", "human"},
                        {"Swedish Chef", "human"}
                };
                int count=sizeof(muppets)/sizeof(struct critter);
                int
                critter_cmp (const struct critter *c1,
                const struct critter *c2)
                {
                        return strcmp (c1->name, c2->name);
                }
                void
                print_critter (const struct critter *c)
                {
                        printf ("%s, the %s\n", c->name,
                c->species);
                }
                void
                find_critter (const char *name)
                {
                        struct critter target, *result;
                        target.name = name;
                        result = bsearch (&target, muppets, count,
                        sizeof (struct critter), critter_cmp);
                        if (result)
                                print_critter (result);
                        else
                                printf ("Couldn't find %s.\n", name);
                }
                int
                main (void)
                {
                        int i;
                        for (i = 0; i < count; i++)
                                print_critter (&muppets[i]);
                        printf ("\n");
                        qsort (muppets, count, sizeof (struct
                        critter), critter_cmp);
                        for (i = 0; i < count; i++)
                                print_critter (&muppets[i]);
                        printf ("\n");
                        find_critter ("Kermit");
                        find_critter ("Gonzo");
                        find_critter ("Janice");
                        return 0;
                }
Вывод этой программы:
                Kermit, the frog
                Piggy, the pig
                Gonzo, the whatever
                Fozzie, the bear
                Sam, the eagle
                Robin, the frog
                Animal, the animal
                Camilla, the chicken
                Sweetums, the monster
                Dr. Strangepork, the pig
                Link Hogthrob, the pig
                Zoot, the human
                Dr. Bunsen Honeydew, the human
                Beaker, the human
                Swedish Chef, the human
                Animal, the animal
                Beaker, the human
                Camilla, the chicken
                Dr. Bunsen Honeydew, the human
                Dr. Strangepork, the pig
                Fozzie, the bear
                Gonzo, the whatever
                Kermit, the frog
                Link Hogthrob, the pig
                Piggy, the pig
                Robin, the frog
                Sam, the eagle
                Swedish Chef, the human
                Sweetums, the monster
                Zoot, the human
                Kermit, the frog
                Gonzo, the whatever
                Couldn't find Janice.


Вперед Назад Содержание