Linux программирование в примерах, Роббинс Арнольд

Linux программирование в примерах

на обложку

Роббинс Арнольд

Шрифт:

К двоичным деревьям применяют следующие операции:

Ввод

Добавление к дереву нового элемента.

Поиск

Нахождение элемента в дереве.

Удаление

Удаление элемента из дерева.

Прохождение (traversal)

Осуществление какой-либо операции с каждым хранящимся в дереве элементом. Прохождение дерева называют также обходом дерева (tree walk). Есть разнообразные способы «посещения» хранящихся в дереве элементов. Обсуждаемые здесь функции реализуют лишь один из таких способов. Мы дополнительно расскажем об этом позже.

14.4.2. Функции управления деревьями

Только что описанные операции соответствуют следующим функциям:

#include <search.h> /* XSI */

void *tsearch(const void *key, void **rootp,

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

void *tfind(const void *key, const void **rootp,

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

void *tdelete(const void *key, void **rootp,

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

typedef enum { preorder, postorder, endorder, leaf } VISIT;

void twalk(const void *root,

void (*action)(const void *nodep, const VISIT which,

const int depth));

void tdestroy(void *root, void (*free_node)(void *nodep)); /* GLIBC*/

Эти функции были впервые определены для System V, а теперь формально стандартизованы POSIX. Они следуют структуре других, которые мы видели в разделе 6.2 «Функции сортировки и поиска»: использование указателей

void*

для указания на произвольные типы данных и предоставляемые пользователем функции сравнения для определения порядка. Как и для

qsort

bsearch

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

key

сравнивается со значением в вершине дерева.

14.4.3. Ввод элемента в дерево:

tsearch

Эти процедуры выделяют память для вершин дерева. Для их использования с несколькими деревьями нужно предоставить им указатель на переменную

void*

, в которую они заносят адрес корневой вершины. При создании нового дерева инициализируйте этот указатель в

NULL

void *root = NULL; /* Корень нового дерева */

void *val; /* Указатель на возвращенные данные */

extern int my_compare(const void*, const void*); /* Функция сравнения */

extern char key[], key2[]; /* Значения для ввода в дерево */

val = tsearch(key, &root, my_compare);

/* Ввести в дерево первый элемент */

/* ...заполнить key2 другим значением. НЕ изменять корень... */

val = tsearch(key2, &root, my_compare);

/* Ввести в дерево последующий элемент */

Как показано, в переменной

root

должен быть

NULL

лишь в первый раз, после чего нужно оставить ее как есть. При каждом последующем вызове

tsearch

использует ее для управления деревом.

Когда разыскиваемый

key

найден, как

tsearch

, так и

tfind

возвращают указатель на содержащую его вершину. Поведение функций различно, когда

key

не найден:

tfind

возвращает

NULL

, a

tsearch

вводит в дерево новое значение и возвращает указатель на него. Функции

tsearch

tfind

возвращают указатели на внутренние вершины дерева. Они могут использоваться в последующих вызовах в качестве значения root для работы с поддеревьями. Как мы вскоре увидим, значение key может быть указателем на произвольную структуру; он не ограничен символьной строкой, как можно было бы предположить из предыдущего примера.

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

malloc

ЗАМЕЧАНИЕ. Поскольку функции деревьев хранят указатели, тщательно позаботьтесь о том, чтобы не использовать

realloc

для значений, которые были использованы в качестве ключей!

realloc

может переместить данные, вернув новый указатель, но процедуры деревьев все равно сохранят висящие (dangling) указатели на старые данные.

14.4.4. Поиск по дереву и использование возвращенного указателя:

tfind

tsearch

Функции

tfind

tsearch

осуществляют поиск в двоичном дереве по данному ключу. Они принимают тот же самый набор аргументов: ключ для поиска

key

. указатель на корень дерева,

rootp

; и

compare

, указатель на функцию сравнения. Обе функции возвращают указатель на вершину, которая соответствует

key

Как именно использовать указатель, возвращенный

tfind

tsearch

? Во всяком случае, на что именно он указывает? Ответ заключается в том, что он указывает на вершину в дереве. Это внутренний тип; вы не можете увидеть, как он определен. Однако, POSIX гарантирует, что этот указатель может быть приведен к указателю на указатель на что бы то ни было, что вы используете в качестве ключа. Вот обрывочный код для демонстрации, а затем мы покажем, как это работает:

struct employee { /* Из главы 6 */

char lastname[30];

char firstname[30];

long emp_id;

time_t start_date;

};

/* emp_name_id_compare --- сравнение по имени, затем no ID */

int emp_name_id_compare(const void *e1p, const void *e2p) {

/* ...также из главы 6, полностью представлено позже... */