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

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

Жанры

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

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

Шрифт:

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 и т.д. для обозначения того, на какой стадии была посещена вершина. Это может сбивать с толку.

Следующая программа,

ch14-tsearch.c
, демонстрирует построение и обход дерева. Она повторно использует структуру
struct employee
и функцию
emp_name_id_compare
из раздела 6.2 «Функции сортировки и поиска».

1 /* ch14-tsearch.c --- демонстрация управления деревом */

2

3 #include <stdio.h>

4 #include <search.h>

5 #include <time.h>

6

7 struct employee {

8 char lastname[30];

9 char firstname[30];

10 long emp_id;

11 time_t start_date;

12 };

13

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

15

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

17 {

18 const struct employee *e1, *e2;

19 int last, first;

20

21 e1 = (const struct employee*)e1p;

22 e2 = (const struct employee*)e2p;

23

24 if ((last = strcmp(e1->lastname, e2->lastname)) != 0)

25 return last;

26

27 /* фамилии совпадают, проверить имена */

28 if ((first = strcmp(e1->firstname, e2->firstname)) != 0)

29 return first;

30

31 /* имена совпадают, проверить ID */

32 if (e1->emp_id < e2->emp_id)

33 return -1;

34 else if (e1->emp_id == e2->emp_id)

35 return 0;

36 else

37 return 1;

38 }

39

40 /* print_emp --- вывод структуры employee во время обхода дерева */

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

Эволюционер из трущоб. Том 5

Панарин Антон
5. Эволюционер из трущоб
Фантастика:
попаданцы
аниме
фэнтези
фантастика: прочее
5.00
рейтинг книги
Эволюционер из трущоб. Том 5

Мечник Вернувшийся 1000 лет спустя. Том 2

Ткачев Андрей Юрьевич
2. Вернувшийся мечник
Фантастика:
аниме
фэнтези
попаданцы
5.00
рейтинг книги
Мечник Вернувшийся 1000 лет спустя. Том 2

Московское золото и нежная попа комсомолки. Часть Пятая

Хренов Алексей
5. Летчик Леха
Фантастика:
попаданцы
5.00
рейтинг книги
Московское золото и нежная попа комсомолки. Часть Пятая

Магия чистых душ

Шах Ольга
Любовные романы:
любовно-фантастические романы
5.40
рейтинг книги
Магия чистых душ

Товарищ "Чума" 6

lanpirot
6. Товарищ "Чума"
Фантастика:
городское фэнтези
попаданцы
альтернативная история
5.00
рейтинг книги
Товарищ Чума 6

Первый среди равных. Книга VIII

Бор Жорж
8. Первый среди Равных
Фантастика:
аниме
фантастика: прочее
эпическая фантастика
попаданцы
5.00
рейтинг книги
Первый среди равных. Книга VIII

Наследник

Кулаков Алексей Иванович
1. Рюрикова кровь
Фантастика:
научная фантастика
попаданцы
альтернативная история
8.69
рейтинг книги
Наследник

Меняя маски

Метельский Николай Александрович
1. Унесенный ветром
Фантастика:
боевая фантастика
попаданцы
9.22
рейтинг книги
Меняя маски

Ваше Сиятельство 7

Моури Эрли
7. Ваше Сиятельство
Фантастика:
боевая фантастика
аниме
5.00
рейтинг книги
Ваше Сиятельство 7

Третий Генерал: Тома I-II

Зот Бакалавр
1. Третий Генерал
Фантастика:
городское фэнтези
попаданцы
аниме
сказочная фантастика
5.00
рейтинг книги
Третий Генерал: Тома I-II

(Не)зачёт, Дарья Сергеевна!

Рам Янка
8. Самбисты
Любовные романы:
современные любовные романы
5.00
рейтинг книги
(Не)зачёт, Дарья Сергеевна!

Третий. Том 4

INDIGO
Вселенная EVE Online
Фантастика:
боевая фантастика
космическая фантастика
попаданцы
5.00
рейтинг книги
Третий. Том 4

Вперед в прошлое 7

Ратманов Денис
7. Вперед в прошлое
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Вперед в прошлое 7

Тринадцатый

NikL
1. Видящий смерть
Фантастика:
фэнтези
попаданцы
аниме
6.80
рейтинг книги
Тринадцатый