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

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

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, полностью представлено позже... */

}

struct employee key = { ... };

void *vp, *root;

struct employee *e;

/* ...заполнение данными... */

vp = tfind(&key, root, emp_name_id_compare);

if (vp != NULL) { /* it's there, use it */

 e = *((struct employee**)vp); /* Получить хранящиеся в дереве данные */

 /* использование данных в *е ... */

}

Как можно указатель на вершину использовать как указатель на указатель данных? Рассмотрим, как была бы реализована вершина двоичного дерева. В каждой вершине хранится по крайней мере указатель на элемент данных пользователя и указатели на потенциальные порожденные вершины справа и слева. Поэтому она должна выглядеть примерно так.

struct binary_tree {

 void *user_data; /* Указатель на данные пользователя */

 struct binary_tree *left; /* Порожденная вершина слева или NULL */

 struct binary_tree *right; /* Порожденная вершина справа или NULL */

/* ...здесь возможны другие поля... */

} node;

С и C++ гарантируют, что поля внутри структуры располагаются в порядке возрастания адресов. Таким образом, выражение '

&node.left < &node.right

' истинно. Более того, адрес структуры является также адресом ее первого поля (другими словами, игнорируя проблемы типов, '

&node == &node.user_data

').

Следовательно, концептуально '

е = *((struct employee**)vp);

' означает:

1. 

vp

является

void*

, то есть общим указателем. Это адрес внутренней вершины дерева, но это также адрес части вершины (скорее всего, другого

void*

), которая указывает на данные пользователя.

2. '

(struct employee**)vp

' приводит адрес внутреннего указателя к нужному типу; он остается указателем на указатель, но в этот раз на

struct employee

. Помните, что приведение одного типа указателя к другому не изменяют значения (паттерна битов); оно меняет лишь способ интерпретации компилятором значения для анализа типов.