Шрифт:
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 «Функции сортировки и поиска». Чтобы освежить вашу память, полями являются фамилия, имя, номер сотрудника и время начала работы в виде временной отметки в секундах с начала Эпохи:
$ cat presdata.txt
Bush George 43 980013600
Clinton William 42 727552800
Bush George 41 601322400
Reagan Ronald 40 348861600