Следующая программа,
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
, что означает, что была посещена левая вершина, а правая еще не была посещена.
Используемые данные представляют собой список президентов, тоже из раздела 6.2 «Функции сортировки и поиска». Чтобы освежить вашу память, полями являются фамилия, имя, номер сотрудника и время начала работы в виде временной отметки в секундах с начала Эпохи:
$ <b>cat presdata.txt</b>
Bush George 43 980013600
