Поиск и сортировка
Поиск и сортировка данных, располагающихся в оперативной памяти, – типичная и очень важная часть многих приложений, качество реализации которой во многом определяет технические характеристики программной системы в целом.
Стандарт POSIX-2001 предлагает несколько способов поиска в таблицах разных форматов.
Бинарный поиск (см. листинг 9.13) является самым быстрым среди методов, основанных на сравнении ключей. Он применим к предварительно отсортированным одномерным массивам.
#include <stdlib.h> void *bsearch (const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));
Листинг 9.13. Описание функции бинарного поиска bsearch(). (html, txt)
Функция bsearch() предназначена для выполнения бинарного поиска в соответствии с алгоритмом, описанным Д. Кнутом (см. [4] в дополнительной литературе, пункт 6.2.1, алгоритм B).
Функция bsearch() возвращает указатель внутрь массива на искомые данные или NULL в случае неудачи поиска. Предварительно массив должен быть отсортирован в возрастающем порядке согласно предоставленной функции сравнения compar().
Аргумент key указывает на объект данных, разыскиваемый в массиве (ключ поиска); base указывает на начало (первый элемент) массива; nel задает количество элементов в массиве; width специфицирует размер элемента в массиве.
Аргумент compar() – это функция сравнения, аргументами которой служат два указателя на сравниваемые объекты – ключ и элемент массива. В соответствии с тем, какое целое число она возвращает: меньшее нуля, равное нулю или большее нуля, ключ считается меньшим, равным или большим по отношению к элементу массива.
Для сортировки массивов целесообразно пользоваться функцией qsort() (см. листинг 9.14), реализующей метод быстрой сортировки (называемый также методом обменной сортировки с разделением, см. [4] в дополнительной литературе, пункт 5.2.2, алгоритм Q). Ее аргументы имеют тот же смысл, что и одноименные аргументы функции bsearch().
#include <stdlib.h> void qsort (void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));
Листинг 9.14. Описание функции быстрой сортировки qsort(). (html, txt)
Рассмотрим пример последовательного применения функций qsort() и bsearch() (см. листинг 9.15). Здесь в роли элементов массива выступают указатели на цепочки символов, которые размещены в области StringSpace; тот же тип имеет и ключ поиска. Критерием сравнения служит алфавитная упорядоченность указуемых цепочек.
Листинг 9.15. Пример применения функций быстрой сортировки и бинарного поиска. (html, txt)
Отметим, что при сортировке будут перемещаться элементы массива PtsTable [] – указатели на цепочки символов, но, конечно, не сами цепочки.
Если на компьютере, которым в данный момент пользуется автор, измерить время выполнения приведенной программы посредством утилиты time с опцией -p, результаты будут выглядеть следующим образом (см. листинг 9.16).
Листинг 9.16. Возможные результаты выполнения программы, применяющей функции быстрой сортировки и бинарного поиска. (html, txt)
Читателю предлагается сравнить эти результаты с экспериментально полученными собственными (и с гордостью убедиться, что его компьютер гораздо мощнее), а также оценить зависимость длительности быстрой сортировки и бинарного поиска от размера массива (и подтвердить теоретические оценки из [4]).
Стандартом POSIX-2001, помимо бинарного, предусматривается еще несколько способов поиска – последовательный, с помощью хэш-таблиц и бинарных деревьев. Соответствующие описания сосредоточены в заголовочном файле <search.h>.
В идейном плане самым простым является последовательный поиск. Он может производиться с вставкой (функция lsearch()) или без таковой (lfind()) (см. листинг 9.17).
#include <search.h>
void *lsearch (const void *key, void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));
void *lfind (const void *key, const void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));
Листинг 9.17. Описание функций последовательного поиска. (html, txt)
Функции, реализующие последовательный поиск, по способу вызова напоминают bsearch(), только аргумент nelp является указателем на число элементов в массиве, которое функция lsearch() может увеличить на единицу (если искомого элемента в массиве не было, его добавляют в конец).
Разумеется, для последовательного поиска не требуется, чтобы массив был предварительно отсортирован. Упрощены и требования к функции сравнения compar(): в случае неравенства ее результат должен быть отличен от нуля.
В качестве иллюстрации применения функций последовательного поиска рассмотрим программу, генерирующую случайные цепочки символов до первого повторения (см. листинг 9.18).
Листинг 9.18. Пример применения последовательного поиска с вставкой. (html, txt)
Указатели на порождаемые случайные цепочки помещаются в массив PtsTable [] функцией lsearch(). В этой связи обратим внимание на нескольку вычурную организацию цикла for в функции main(). По сути здесь две переменные цикла – pss и nelst. Первая продвигается стандартным образом, в заголовке цикла, но проверяется на выход за допустимые границы в его теле; вторая, напротив, стандартно проверяется, но нестандартно продвигается (в результате вызова lsearch()).
Возможные результаты выполнения этой программы показаны на листинге 9.19.
Листинг 9.19. Возможные результаты выполнения программы, применяющей функцию последовательного поиска с вставкой. (html, txt)
При экспериментах с приведенной программой следует соблюдать определенную осторожность, поскольку время ее работы квадратично зависит от величины TAB_SIZE.
Листинг 9.16. Возможные результаты выполнения программы, применяющей функции быстрой сортировки и бинарного поиска.
Читателю предлагается сравнить эти результаты с экспериментально полученными собственными (и с гордостью убедиться, что его компьютер гораздо мощнее), а также оценить зависимость длительности быстрой сортировки и бинарного поиска от размера массива (и подтвердить теоретические оценки из [4]).
Стандартом POSIX-2001, помимо бинарного, предусматривается еще несколько способов поиска – последовательный, с помощью хэш-таблиц и бинарных деревьев. Соответствующие описания сосредоточены в заголовочном файле <search.h>.
В идейном плане самым простым является последовательный поиск. Он может производиться с вставкой (функция lsearch()) или без таковой (lfind()) (см. листинг 9.17).
#include <search.h>
void *lsearch (const void *key, void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));
void *lfind (const void *key, const void *base, size_t *nelp, size_t width, int (*compar) (const void *, const void *));
Листинг 9.17. Описание функций последовательного поиска.
Функции, реализующие последовательный поиск, по способу вызова напоминают bsearch(), только аргумент nelp является указателем на число элементов в массиве, которое функция lsearch() может увеличить на единицу (если искомого элемента в массиве не было, его добавляют в конец). Разумеется, для последовательного поиска не требуется, чтобы массив был предварительно отсортирован. Упрощены и требования к функции сравнения compar(): в случае неравенства ее результат должен быть отличен от нуля.
В качестве иллюстрации применения функций последовательного поиска рассмотрим программу, генерирующую случайные цепочки символов до первого повторения (см. листинг 9.18).
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа генерирует случайные цепочки символов до первого */ /* повторения (или до исчерпания отведенного пространства). */ /* Для выявления повторения применяется */ /* последовательный поиск с вставкой */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <search.h> #include <stdio.h> #include <stdlib.h> #include <string.h>
/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 200000
/* Число элементов в таблице указателей на цепочки символов */ #define TAB_SIZE 20000
/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 7
/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];
/* Массив указателей на цепочки символов */ static char *PtsTable [TAB_SIZE];
/* * * * * * * * * * */ /* Функция сравнения */ /* * * * * * * * * * */ static int str_compar (const void *pkey, const void *pelem) { return strcoll (*((char **) pkey), *((char **) pelem)); }
/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }
/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Поиск первого повтора в последовательности */ /* случайных цепочек символов */ /* * * * * * * * * * * * * * * * * * * * * * * * */ int main (int argc, char *argv []) { char *pss; /* Указатель на свободное место */ /* в области StringSpace */ char **res; /* Результат поиска с вставкой */ size_t nelst; /* Число занятых элементов */ /* в массиве указателей */ size_t onelst; /* Число элементов в массиве */ /* до поиска с вставкой */ for (pss = StringSpace, nelst = 0; nelst < TAB_SIZE; pss += STRING_SIZE) { if (((pss + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "%s: Исчерпано пространство " "цепочек\n", argv [0]); return (1); }
str_rnd (pss, STRING_SIZE);
onelst = nelst; res = (char **) lsearch (&pss, PtsTable, &nelst, sizeof (PtsTable [0]), str_compar); if (onelst == nelst) { /* Искомая цепочка уже была порождена ранее */ printf ("Для случайных цепочек длины %d\n" "первое совпадение получено на цепочке " "%s\n", STRING_SIZE, pss); printf ("Первый раз цепочка была порождена " "под номером %d,\n" "второй – под номером " "%d\n", (res – PtsTable) / sizeof (PtsTable [0]) + 1, nelst + 1); return 0; } } /* for */
printf ("Из %d случайных цепочек длины %d все " "оказались уникальными\n", TAB_SIZE, STRING_SIZE);
return 0; }
Листинг 9.18. Пример применения последовательного поиска с вставкой.
Указатели на порождаемые случайные цепочки помещаются в массив PtsTable [] функцией lsearch(). В этой связи обратим внимание на нескольку вычурную организацию цикла for в функции main(). По сути здесь две переменные цикла – pss и nelst. Первая продвигается стандартным образом, в заголовке цикла, но проверяется на выход за допустимые границы в его теле; вторая, напротив, стандартно проверяется, но нестандартно продвигается (в результате вызова lsearch()).
Возможные результаты выполнения этой программы показаны на листинге 9.19.
Для случайных цепочек длины 7 первое совпадение получено на цепочке GLPCSX Первый раз цепочка была порождена под номером 2548, второй - под номером 12530 real 34.80 user 13.70 sys 0.03
Листинг 9.19. Возможные результаты выполнения программы, применяющей функцию последовательного поиска с вставкой.
При экспериментах с приведенной программой следует соблюдать определенную осторожность, поскольку время ее работы квадратично зависит от величины TAB_SIZE.
Управление хэш-таблицами поиска производится в соответствии с алгоритмом, описанным Д. Кнутом (см. [4] в дополнительной литературе, раздел 6.4, алгоритм D). Предоставляются функции для создания (hcreate()) и ликвидации (hdestroy()) хэш-таблиц, а также для выполнения в них поиска (hsearch()), быть может, с вставкой (см. листинг 9.20). Сразу отметим, что в каждый момент времени может быть активна только одна хэш-таблица.
#include <search.h>
int hcreate (size_t nel);
void hdestroy (void);
ENTRY *hsearch (ENTRY item, ACTION action);
Пример 9.20. Описание функций управления хэш-таблицами поиска.
Предполагается, что элементы таблицы поиска имеют тип ENTRY, определенный так, как показано на листинге 9.21.
typedef struct entry { char *key; /* Ключ поиска */ void *data; /* Дополнительные данные, */ /* ассоциированные с ключом */ } ENTRY;
Листинг 9.21. Описание типа ENTRY.
Функция hcreate() резервирует достаточное количество памяти для таблицы и должна вызываться перед обращением к hsearch(). Значением аргумента nel является ожидаемое максимальное количество элементов в таблице. Это число можно взять с запасом, чтобы уменьшить среднее время поиска.
Нормальный для hcreate() результат отличен от нуля.
Функция hdestroy() ликвидирует таблицу поиска. За вызовом этой функции может следовать новое обращение к функции создания таблицы hcreate().
Функция hsearch() возвращает указатель внутрь таблицы на искомые данные. Аргумент item – это структура типа ENTRY, содержащая два указателя: item.key указывает на сравниваемый ключ (функцией сравнения при поиске в хэш-таблице служит strcmp()), а item.data – на любые дополнительные данные, ассоциированные с этим ключом.
Аргумент action имеет тип ACTION, определенный так, как показано на листинге 9.22. Он задает способ действий в случае неудачного поиска: значение ENTER предписывает производить поиск с вставкой, то есть в случае неудачи искомый элемент следует поместить в таблицу; значение FIND предписывает в случае неудачи вернуть пустой указатель NULL. Пустой указатель возвращается и тогда, когда значение аргумента action равно ENTER, и таблица заполнена.
enum { FIND, ENTER } ACTION;
Листинг 9.22. Определение типа ACTION.
В качестве примера применения функций, управляющих хэш-таблицами поиска, рассмотрим программу, которая помещает в хэш-таблицу заданное число элементов с указателями на случайные цепочки символов, а затем выполняет в этой таблице поиск новых случайных цепочек, пока он не окажется успешным (см. листинг 9.23).
/* * * * * * * * * * * * * * * * * * * * */ /* Программа помещает в хэш-таблицу */ /* заданное число элементов с указателями*/ /* на случайные цепочки символов, */ /* а затем выполняет в этой таблице */ /* поиск новых случайных цепочек, */ /* пока он не окажется успешным */ /* * * * * * * * * * * * * * * * * * * * */
#include <search.h> #include <stdlib.h> #include <stdio.h>
/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 10000000
/* Число элементов, помещаемых в хэш-таблицу */ #define TAB_NEL 1000000
/* Размер хэш-таблицы */ #define TAB_SIZE (2 * TAB_NEL)
/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 10
/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];
/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }
/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Заполнение хэш-таблицы, поиск повтора в */ /* последовательности случайных цепочек символов */ /* * * * * * * * * * * * * * * * * * * * * * * * */ int main (int argc, char *argv []) { ENTRY item; /* Искомый элемент */ char sbuf [STRING_SIZE]; /* Буфер для формирования */ /* случайных цепочек */ double ntr; /* Номер найденной */ /* случайной цепочки */ size_t i;
if (hcreate (TAB_SIZE) == 0) { fprintf (stderr, "%s: Не удалось создать хэш-таблицу" " размера %d\n", argv [0], TAB_SIZE); return (1); }
item.data = NULL; /* Нет ассоциированных данных */ /* Заполним таблицу */ for (item.key = StringSpace, i = 0; i < TAB_NEL; item.key += STRING_SIZE, i++) { if (((item.key + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "%s: Исчерпано пространство " "цепочек\n", argv [0]); return (2); }
str_rnd (item.key, STRING_SIZE);
if (hsearch (item, ENTER) == NULL) { fprintf (stderr, "%s: Переполнена хэш-таблица\n", argv [0]); return (3); } } /* for */
/* Будем формировать и искать новые случайные цепочки */ item.key = sbuf; ntr = 0; do { str_rnd (item.key, STRING_SIZE); ntr++; } while (hsearch (item, FIND) == NULL); printf ("Удалось найти %g-ю по счету случайную цепочку %s\n", ntr, item.key);
hdestroy ();
return 0; }
Листинг 9.23. Пример применения функций, управляющих хэш-таблицами поиска.
Обратим внимание на то, что размер хэш-таблицы выбран вдвое большим по сравнению с реально используемым числом элементов; это уменьшает число коллизий (случаев совпадения хэш-кодов разных ключей) и ускоряет их разрешение. При небольшом числе коллизий время поиска одного элемента в хэш-таблице ограничено константой (не зависит от количества элементов в таблице). Это значит, что время работы приведенной программы должно быть пропорционально размеру таблицы, то есть по порядку величины оно меньше, чем для рассмотренной выше комбинации быстрой сортировки и бинарного поиска (убирается множитель, равный логарифму числа элементов). Сделанный вывод подтверждается результатами измерения времени работы программы (см. листинг 9.24).
Удалось найти 168221-ю по счету случайную цепочку VBBDZTNMZ real 9.61 user 9.36 sys 0.25
Листинг 9.24. Возможные результаты выполнения программы, применяющей функции управления хэш-таблицами поиска.
Читателю предлагается измерить время работы этой программы на своем компьютере, сравнить его с аналогичным временем для быстрой сортировки и бинарного поиска, а также оценить зависимость среднего времени поиска от размера таблицы (и подтвердить теоретические оценки из [4]).
Бинарные деревья поиска – замечательное средство, позволяющее эффективно (за время, логарифмически зависящее от числа элементов) осуществлять операций поиска с вставкой (функция tsearch()) и без таковой (tfind()), удаления (tdelete()) и, кроме того, выполнять обход всех элементов (функция twalk()) (см. листинг 9.25). Функции реализуют алгоритмы T и D, описанные в пункте 6.2.2 книги Д. Кнута [4].
#include <search.h>
void *tsearch (const void *key, void **rootp, int (*compar) (const void *, const void *));
void *tfind (const void *key, void *const *rootp, int (*compar) (const void *, const void *));
void *tdelete (const void *restrict key, void **restrict rootp, int (*compar) (const void *, const void *));
void twalk (const void *root, void (*action) (const void *, VISIT, int));
Листинг 9.25. Описание функций управления бинарными деревьями поиска.
Функция tsearch() используется для построения дерева и доступа к нему. Аргумент key является указателем на искомые данные (ключ). Если в дереве есть узел, первым полем которого является ссылка на данные, равные искомым, то результатом функции служит указатель на этот узел. В противном случае в дерево вставляется вновь созданный узел со ссылкой на искомые данные и возвращается указатель на него. Отметим, что копируются только указатели, поэтому прикладная программа сама должна позаботиться о хранении данных.
Аргумент rootp указывает на переменную, которая является указателем на корень дерева. Ее значение, равное NULL, специфицирует пустое дерево; в этом случае в результате выполнения функции tsearch() переменная устанавливается равной указателю на единственный узел – корень вновь созданного дерева.
Подобно функции tsearch(), функция tfind() осуществляет поиск по ключу, возвращая в случае успеха указатель на соответствующий узел. Однако в случае неудачного поиска функция tfind() возвращает пустой указатель NULL.
Функция tdelete(), как и tfind(), сначала производит поиск, но не останавливается на этом, а удаляет найденный узел из бинарного дерева. Результатом tdelete() служит указатель на вышележащий по сравнению с удаляемым узел или NULL, если поиск оказался неудачным.
Функция twalk() осуществляет обход бинарного дерева в глубину, слева направо (дерево строится функцией tsearch() так, что, в соответствии с функцией сравнения compar(), все узлы левого поддерева предшествуют его корню, который, в свою очередь, предшествует узлам правого поддерева). Аргумент root указывает на корень обрабатываемого (под)дерева (любой узел может быть использован в качестве корня для обхода соответствующего поддерева).
Очевидно, в процессе обхода все неконцевые узлы посещаются трижды (при спуске в левое поддерево, при переходе из левого поддерева в правое и при возвращении из правого поддерева), а концевые (листья) – один раз.
Эти посещения обозначаются величинами типа VISIT с исключительно неудачными именами (см. листинг 9.26).
enum { preorder, postorder, endorder, leaf } VISIT;
Листинг 9.26. Определение типа VISIT.
Имена неудачны, потому что они совпадают с названиями разных способов обхода деревьев (см., например, [3] в дополнительной литературе, пункт 2.3.1). В частности, порядок обхода, реализуемый функцией twalk(), называется в [3] прямым (по-английски – preorder). Остается надеяться, что читатель не даст себя запутать и уверенно скажет, что в данном контексте postorder – это второе посещение неконцевого узла бинарного дерева поиска, а не какой-то там обратный порядок обхода.
Аргумент action – это функция, которую twalk() вызывает при попадании в узел во время обхода. Она, в свою очередь, имеет три аргумента. Первым из них служит адрес текущего узла. Структура, на которую указывает этот аргумент, стандартом не специфицируется; оговаривается только, что указатель на узел можно привести к типу "указатель на указатель на хранимые данные" (то есть на данные, ассоциированные с узлом, и содержащие, в частности, ключ поиска). Второй аргумент вызываемой функции – это значение определенного выше типа VISIT. Напомним еще раз, что оно показывает, который раз (первый, второй или третий) осуществляется доступ к неконцевому узлу во время обхода дерева в глубину и слева направо или свидетельствует, что узел является концевым (листом). Третий аргумент – это уровень узла в дереве (в предположении, что корень имеет уровень 0).
Читатель наверняка уже догадался, что далее последует пример программы, строящей бинарное дерево поиска для случайных цепочек символов (см. листинг 9.27). Впрочем, приведенная программа делает и еще кое-что: подсчитывает число узлов и высоту дерева, распечатывает несколько первых по алфавиту цепочек из числа помещенных в дерево и, конечно, генерирует новые случайные цепочки, пока их поиск в дереве не окажется успешным. Для разнообразия узел с найденной цепочкой удаляется.
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа осуществляет поиск с вставкой в бинарном */ /* дереве, помещая в него заданное число элементов с */ /* указателями на случайные цепочки символов. */ /* Затем подсчитывается число узлов и высота дерева. */ /* Следующим действием является распечатка */
/* нескольких первых цепочек. */ /* После этого выполняется поиск новых случайных цепочек,*/ /* пока он не окажется успешным. */ /* Найденный элемент удаляется из дерева */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <search.h> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <setjmp.h>
/* Размер области для хранения цепочек символов */ #define SPACE_SIZE 10000000
/* Число элементов, помещаемых в дерево */ #define TREE_NEL 1000000
/* Длина одной цепочки символов */ /* (включая завершающий нулевой байт) */ #define STRING_SIZE 10
/* Область для хранения цепочек символов */ static char StringSpace [SPACE_SIZE];
/* Число узлов в бинарном дереве поиска */ static size_t node_count;
/* Максимальный уровень узла дерева */ static int max_level; /* Буфер для функций setjmp и longjmp */ static jmp_buf buf_env;
/* * * * * * * * * * * * * * * * * * * * * */ /* Формирование случайной цепочки символов */ /* * * * * * * * * * * * * * * * * * * * * */ static void str_rnd (char *buf, size_t str_siz) { for ( ; str_siz > 1; str_siz--) { *buf++ = 'A' + rand () % 26; } if (str_siz > 0) { *buf = 0; } }
/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Функция, которая вызывается при обходе дерева */ /* с целью подсчета числа узлов и высоты */ /* * * * * * * * * * * * * * * * * * * * * * * * */ static void tw_nnh (const void *pnode, VISIT nv, int level) { if (nv == preorder) { node_count++; } else if (nv == leaf) { node_count++; if (level > max_level) { max_level = level; } } }
/* * * * * * * * * * * * * * * * * * * * * * * * */ /* Функция, которая вызывается при обходе дерева */ /* с целью распечатки нескольких первых */ /* по алфавиту цепочек символов */ /* * * * * * * * * * * * * * * * * * * * * * * * */ static void tw_pfs (const void *pnode, VISIT nv, int level) { if (node_count <= 0) { /* Нужное число цепочек выведено,*/ /* прерываем обход дерева */ longjmp (buf_env, 1); } if ((nv == postorder) || (nv == leaf)) { printf ("%s\n", *((char **) pnode)); node_count--; } }
/* * * * * * * * * * * * * * * * * * */ /* Создание бинарного дерева поиска, */ /* определение его характеристик, */ /* поиск повтора в последовательности*/ /* случайных цепочек символов */ /* * * * * * * * * * * * * * * * * * */ int main (int argc, char *argv []) { void *root; /* Указатель на корень дерева */ char *key; /* Указатель на искомую */ /* цепочку символов */ char sbuf [STRING_SIZE]; /* Буфер для формирования */ /* случайных цепочек */ double ntr; /* Номер найденной случайной */ /* цепочки */ size_t i;
/* Создадим бинарное дерево поиска */ root = NULL; for (key = StringSpace, i = 0; i < TREE_NEL; key += STRING_SIZE, i++) { if (((key + STRING_SIZE) – (StringSpace + SPACE_SIZE)) > 0) { fprintf (stderr, "%s: Исчерпано пространство " "цепочек\n", argv [0]); return (1); }
str_rnd (key, STRING_SIZE);
if (tsearch (key, &root, (int (*) (const void *, const void *)) strcoll) == NULL) { fprintf (stderr, "%s: Поиск с вставкой в бинарное" " дерево " "завершился неудачей\n", argv [0]); return (2); } } /* for */
/* Подсчитаем число узлов и высоту созданного дерева */ node_count = 0; max_level = 0; twalk (root, tw_nnh); printf ("В дереве оказалось %d узлов\n", node_count); printf ("Его высота равна %d\n", max_level);
/* Распечатаем несколько первых (по алфавиту) цепочек, */ /* помещенных в созданное дерево */ node_count = 10; printf ("Первые %d по алфавиту цепочек в дереве:\n", node_count); if (setjmp (buf_env) == 0) { twalk (root, tw_pfs); }
/* Будем формировать и искать новые случайные цепочки */ ntr = 0; do { str_rnd (sbuf, STRING_SIZE); ntr++; } while (tdelete (sbuf, &root, (int (*) (const void *, const void *)) strcoll) == NULL); printf ("Удалось найти и удалить из дерева %g-ю по счету " "случайную цепочку %s\n", ntr, sbuf);
return 0; }
Листинг 9.27. Пример применения функций управления бинарными деревьями поиска.
Отметим гибкость бинарных деревьев поиска как структуры данных.
Не требуется заранее резервировать определенное пространство – деревья растут не более, чем это необходимо. При добавлении и удалении узлов деревья динамически перестраиваются без специального переупорядочения или массовых передвижек.
Обратим внимание на частичный обход дерева при распечатке нескольких первых по алфавиту цепочек, реализуемый с использованием механизма нелокальных переходов. Сама по себе функция twalk() ориентирована, разумеется, на полный обход (также представленный в программе).
Возможные результаты выполнения приведенной программы показаны на листинге 9.28.
В дереве оказалось 1000000 узлов Его высота равна 25 Первые 10 по алфавиту цепочек в дереве: AAAATNRAS AAACHCCLB AAACSJQBP AAADLHFAZ AAAFWLRXM AAAFXGQEC AAAGBMHHA AAAGFAXFI AAAHKLCWW AAAHLOSVQ Удалось найти и удалить из дерева 168221-ю по счету случайную цепочку VBBDZTNMZ real 20.24 user 20.25 sys 0.15
Листинг 9.28. Возможные результаты выполнения программы, применяющей функции управления бинарными деревьями поиска.
Отметим, что среди первых 1000000 случайных цепочек символов длины 10 повторов не оказалось. Дерево поиска получилось весьма сбалансированным, с высотой, лишь немногим большей двоичного логарифма от числа узлов. Приведенные данные о времени выполнения подтверждают высокую эффективность бинарных деревьев как инструмента поиска.
Полноты ради упомянем еще о двух функциях, описанных в заголовочном файле <search.h>: insque() и remque() (см. листинг 9.29). Они предназначены для выполнения операций над очередями, реализованными как двусвязанные списки.
#include <search.h>
void insque (void *element, void *pred);
void remque (void *element);
Листинг 9.29. Описание функций, выполняющих операции над очередями.
Функция insque() осуществляет вставку элемента, на который указывает аргумент element, после элемента pred. В качестве элемента должна выступать структура, первые два поля которой являются указателями на структуры того же типа – соответственно, следующий и предыдущий элементы очереди.
Наличие и назначение других полей определяются нуждами приложения. Имя структурного типа и двух первых полей не стандартизуются.
Функция remque() удаляет заданный элемент из очереди.
Очередь может быть линейной или циклической. В первом случае она ограничена пустыми указателями, во втором крайние указатели должны быть зациклены. Вставка первого элемента в линейную очередь осуществляется вызовом insque (&element, NULL); при инициализации циклической очереди о ссылках должно позаботиться приложение (см. листинг 9.30).
#include <search.h>
. . . struct qelem { struct qelem *q_forw; struct qelem *q_back; char *data; . . . };
struct qelem element1; struct qelem element2;
. . . element1.q_forw = &element1; element1.q_back = &element1;
insque (&element2, &element1);
. . .
Листинг 9.30. Пример инициализации циклической очереди и вставки в нее второго элемента.
Трудно сказать, есть ли смысл в стандартизации функций, исходный текст которых занимает пару строк...
Из тех же соображений полноты вернемся к теме сортировки и упомянем служебную программу tsort:
tsort [файл]
выполняющую топологическую сортировку элементов заданного файла (или стандартного ввода, если файл не указан), выдавая результаты на стандартный вывод. Подобная сортировка полезна, в частности, при создании библиотек объектных файлов, чтобы выполнять редактирование внешних связей за один проход.
Исходными данными для утилиты tsort служат содержащиеся в файле пары элементов (непустых цепочек символов), разделенных пробелами. Частичная упорядоченность задается парами различных элементов. Пара одинаковых элементов означает лишь наличие элемента и никакой упорядоченности не задает.
Например, если применить утилиту tsort к файлу, содержащему строки, показанные на листинге 9.31, то можно получить результат, приведенный на листинге 9.32.
a b c d d e f g e f h h
Листинг 9.31. Пример исходных данных для служебной программы tsort.
a c h b d e f g
Листинг 9.32. Возможный результат применения служебной программы tsort.
