Чтение онлайн

на главную - закладки

Жанры

Linux программирование в примерах
Шрифт:

}

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.5. Обход дерева:

twalk

Функция

twalk
объявлена в
<search.h>
следующим образом:

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

void twalk(const void *root,

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

const int depth));

Первый параметр является корнем дерева (не указателем на корень). Второй является указателем на функцию обратного вызова, которая вызывается с тремя аргументами, указателем на исследуемую вершину дерева; типом перечисления, указывающим, как осуществляется обход данной вершины; и целого, обозначающего глубину текущей вершины (корень находится на глубине 0, как объяснялось ранее).

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

nftw
(см. раздел 8.4.3.2 «Функция обратного вызова
nftw
»). Там функция обратного вызова вызывается для каждого объекта в файловой системе. Здесь функция обратного вызова вызывается для каждого объекта, хранящегося в дереве.

Есть несколько способов прохождения, или «обхода», двоичного дерева:

• Левая вершина, родительская вершина, правая вершина.

• Родительская вершина, левая вершина, правая вершина.

• Левая вершина, правая вершина, родительская вершина.

Функция GLIBC

twalk
использует второй способ: сначала родительская вершина, затем левая, затем правая. Каждый раз при встрече с вершиной говорят, что она посещается. [159] В ходе посещения порожденной вершины функция должна посетить и родительскую. Соответственно, значения типа
VISIT
указывают, на какой стадии произошла встреча с этой вершиной:

preorder
До посещения порожденных.

159

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

postorder
После посещения первой, но до посещения второй порожденной вершины.

endorder
После посещения обеих порожденных.

leaf
Эта вершина является концевой, не имеющей порожденных вершин.

ЗАМЕЧАНИЕ. Использованная здесь терминология не соответствует точно той, которая используется в формальных руководствах по структурированию данных. Там используются термины inorder, preorder и postorder для обозначения соответствующих трех перечисленных ранее способов прохождения дерева. Таким образом,

twalk
использует прохождение по типу
preorder
, но использует именованные константы preorder и т.д. для обозначения того, на какой стадии была посещена вершина. Это может сбивать с толку.

Поделиться:
Популярные книги

Краткая история этики

Гусейнов Абдусалам
Научно-образовательная:
философия
5.83
рейтинг книги
Краткая история этики

Развилки новейшей истории России

Чубайс Анатолий
Детективы:
триллеры
6.25
рейтинг книги
Развилки новейшей истории России

Метатель

Тарасов Ник
1. Метатель
Фантастика:
боевая фантастика
попаданцы
рпг
фэнтези
фантастика: прочее
постапокалипсис
4.80
рейтинг книги
Метатель

История украинского народа. Автобиография

Грушевський Михайло Сергійович
Документальная литература:
биографии и мемуары
5.00
рейтинг книги
История украинского народа. Автобиография

Печать пожирателя 2

Соломенный Илья
2. Пожиратель
Фантастика:
городское фэнтези
попаданцы
аниме
сказочная фантастика
5.00
рейтинг книги
Печать пожирателя 2

Газлайтер. Том 28

Володин Григорий Григорьевич
28. История Телепата
Фантастика:
боевая фантастика
аниме
попаданцы
5.60
рейтинг книги
Газлайтер. Том 28

Паладин из прошлого тысячелетия

Еслер Андрей
1. Соприкосновение миров
Фантастика:
боевая фантастика
попаданцы
6.67
рейтинг книги
Паладин из прошлого тысячелетия

Этот мир не выдержит меня. Том 4

Майнер Максим
Первый простолюдин в Академии
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Этот мир не выдержит меня. Том 4

TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security)

Фейт Сидни М.
Компьютеры и Интернет:
ос и сети
5.00
рейтинг книги
TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security)

Мир InterBase. Архитектура, администрирование и разработка приложений баз данных в InterBase/FireBird/Yaffil

Востриков С М
Компьютеры и Интернет:
базы данных
программирование
5.00
рейтинг книги
Мир InterBase. Архитектура, администрирование и разработка приложений баз данных в InterBase/FireBird/Yaffil

Письма

Уайльд Оскар
Символы времени
Документальная литература:
биографии и мемуары
5.00
рейтинг книги
Письма

Террор и демократия в эпоху Сталина. Социальная динамика репрессий

Голдман Венди З.
История сталинизма
Научно-образовательная:
история
5.00
рейтинг книги
Террор и демократия в эпоху Сталина. Социальная динамика репрессий

Законы Рода. Том 9

Мельник Андрей
9. Граф Берестьев
Фантастика:
городское фэнтези
попаданцы
аниме
дорама
фэнтези
фантастика: прочее
5.00
рейтинг книги
Законы Рода. Том 9

Личник

Валериев Игорь
3. Ермак
Фантастика:
альтернативная история
6.33
рейтинг книги
Личник