Эта глава описывает функции для поиска и сортировки массивов произвольных объектов. Вы определяете соответствующую функцию сравнения, которую нужно применить как аргумент, наряду с размером объектов в массиве и общим числом элементов.
Чтобы использовать библиотечные функции сортировки массива, Вы должны описать, как сравнить элементы массива.
Чтобы сделать это, Вы обеспечиваете функцию сравнения, для сравнения двух элементов массива. Библиотека вызовет эту функцию, передавая как указатели на аргументы два элемента массива, которые нужно сравнить. Ваша функция сравнения должна возвратить значение как strcmp (см. Раздел 5.5 [Сравнение СТРОКИ/МАССИВА]): отрицательное, если первый аргумент - "меньше" чем второй, нуль, если они "равны", и положительное если первый аргумент "больше".
Вот пример функции сравнения, которая работает с массивом чисел типа double:
int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}
int comparison_fn_t (const void *, const void *);
Чтобы искать в сортируемом массиве элемент, соответствующий ключу, используйте bsearch функцию. Прототип для этой функции находится в заглавном файле " stdlib.h ".
void * bsearch (const void *key, const void *array, size_t count, size_t size, comparison_fn_t compare)
Возвращаемое значение - указатель на соответствующий элемент массива, или пустой указатель, если никакое соответствие не найдено. Если массив содержит больше чем один подходящий элемент, неопределено который же возвращается.
Эта функция получила имя из предположения, что она выполнена, используя двоичный алгоритм поиска.
Для сортировки массива, используюя произвольную функцию сравнения, используйте qsort функцию. Прототип для этой функции находится в " stdlib.h ".
void qsort (void *array, size_t count, size_t size, comparison_fn_t compare)
Функция compare используется, чтобы выполнить сравнение на элементах массива. Эта функция вызывается с двумя аргументами указателями и должна возвратить целое число меньше , равное, или больше нуля, если первый аргумент меньше , равен, или больше чем второй аргумент.
Предупреждение: если, два объекта сравниваются как равные, их порядок после сортировки, непредсказуем. То есть сортировка не устойчива. Она может делать различие, когда сравнение рассматривает только часть элементов. А также, два элемента с тем же самым ключом сортировки могут отличиться в других отношениях.
Вот простой пример сортировки массива double значений в числовом порядке используя функцию сравнения, определенную выше (см. Раздел 15.1 [Функции Сравнения]):
{
double *array;
int size;
. . .
qsort(array,size,sizeof(double),compare_doubles);
}
Вот пример, показывающий использование 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.