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
. Помните, что приведение одного типа указателя к другому не изменяют значения (паттерна битов); оно меняет лишь способ интерпретации компилятором значения для анализа типов.
3. '
*((struct employee**)vp)
' разыменовывает вновь созданный
struct employee**
, возвращая годный к употреблению указатель
struct employee*
.
4. '
е = *((struct employee**)vp)'
сохраняет это значение в
е
для непосредственного использования позже.
Идея проиллюстрирована на рис. 14.2.
Рис. 14.2. Вершины дерева и их указатели
Для упрощения использования возвращенного указателя вы могли бы рассмотреть определение макроса:
Первый параметр является корнем дерева (не указателем на корень). Второй является указателем на функцию обратного вызова, которая вызывается с тремя аргументами, указателем на исследуемую вершину дерева; типом перечисления, указывающим, как осуществляется обход данной вершины; и целого, обозначающего глубину текущей вершины (корень находится на глубине 0, как объяснялось ранее).
Использование функции обратного вызова здесь такое же, как для
nftw
(см. раздел 8.4.3.2 «Функция обратного вызова
nftw
»). Там функция обратного вызова вызывается для каждого объекта в файловой системе. Здесь функция обратного вызова вызывается для каждого объекта, хранящегося в дереве.
Есть несколько способов прохождения, или «обхода», двоичного дерева: