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

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

Функция 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 во время обхода дерева */
 41
 42 void print_emp(const void *nodep, const VISIT which, const int depth)
 43 {
 44 struct employee *e = *((struct employee**)nodep);
 45
 46 switch (which) {
 47 case leaf:
 48 case postorder:
 49 printf("Depth: %d. Employee: \n", depth);
 50 printf("\t%s, %s\t%d\t%s\n", e->lastname, e->firstname,
 51 e->emp_id, ctime(&e->start_date));
 52 break;
 53 default:
 54 break;
 55 }
 56 }

Строки 7–12 определяют struct employee, а строки 14–38 определяют emp_name_id_compare.

Строки 40–56 определяют print_emp, функцию обратного вызова, которая выводит struct employee наряду с глубиной дерева в текущей вершине. Обратите внимание на магическое приведение типа в строке 44 для получения указателя на сохраненные данные.

 58 /* main --- демонстрация хранения данных в двоичном дереве */
 59
 60 int main(void)
 61 {
 62 #define NPRES 10
 63 struct employee presidents[NPRES];
 64 int i, npres;
 65 char buf[BUFSIZ];
 66 void *root = NULL;
 67
 68 /* Очень простой код для чтения данных: */
 69 for (npres = 0; npres < NPRES && fgets(buf, BUFSIZ, stdin) != NULL;
 70 npres++) {
 71 sscanf(buf, "%s %s %ld %ld\n",
 72 presidents[npres].lastname,
 73 presidents[npres].firstname,
 74 &presidents[npres].emp_id,
 75 &presidents[npres].start_date);
 76 }
 77
 78 for (i = 0; i < npres; i++)
 79 (void)tsearch(&presidents[i], &root, emp_name_id_compare);
 80
 81 twalk(root, print_emp);
 82 return 0;
 83 }

Целью вывода дерева является вывод содержащихся в нем элементов в отсортированном порядке. Помните, что twalk посещает промежуточные вершины по три раза и что левая вершина меньше родительской, тогда как правая больше. Таким образом, оператор switch выводит сведения о вершине, лишь если which равно leaf, является концевой вершиной, или postorder, что означает, что была посещена левая вершина, а правая еще не была посещена.