Книга: Linux программирование в примерах
14.4.4. Поиск по дереву и использование возвращенного указателя: tfind() и tsearch()
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. Вершины дерева и их указатели
Для упрощения использования возвращенного указателя вы могли бы рассмотреть определение макроса:
#define tree_data(ptr, type)(*(type**)(ptr))
...
struct employee *e;
void *vp;
vp = tfind(&key, root, emp_name_id_compare);
if (vp != NULL) { /* it's there, use it */
e = tree_data(vp, struct employee);
/* использование сведений в *e ... */
}
- 14.4.1. Введение в двоичные деревья
- 14.4.2. Функции управления деревьями
- 14.4.3. Ввод элемента в дерево: tsearch()
- 14.4.4. Поиск по дереву и использование возвращенного указателя: tfind() и tsearch()
- 14.4.5. Обход дерева: twalk()
- 14.4.6. Удаление вершины дерева и удаление дерева: tdelete() и tdestroy()
- 14.4. Расширенный поиск с помощью двоичных деревьев
- Восстановление с использованием инструмента gbak
- Типы страниц и их использование
- Использование констант
- Использование переменной окружения ISC_PATH
- Использование сервера Yaffil внутри процесса
- Использование CAST() с типами дата
- Использование типов содержимого и столбцов
- Вызов хранимых процедур InterBase с использованием стандартного синтаксиса ODBC
- Использование кнопки Автосумма
- 24.7. Использование программы-твикера
- Использование отдельных процессоров XSLT