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
Carter James 39 222631200
Данные сортируются на основе сначала фамилии, затем имени, а затем старшинства. При запуске[160] программа выдает следующий результат:
$ ch14-tsearch < presdata.txt
Depth: 1. Employee:
Bush, George 41 Fri Jan 20 13:00:00 1989
Depth: 0. Employee:
Bush, George 43 Sat Jan 20 13:00:00 2001
Depth: 2. Employee:
Carter, James 39 Thu Jan 20 13:00:00 1977
Depth: 1. Employee:
Clinton, William 42 Wed Jan 20 13:00:00 1993
Depth: 2. Employee:
Reagan, Ronald 40 Tue Jan 20 13:00:00 1981