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

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

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

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 «Функции сортировки и поиска». Чтобы освежить вашу память, полями являются фамилия, имя, номер сотрудника и время начала работы в виде временной отметки в секундах с начала Эпохи:

$ cat presdata.txt

Bush George 43 980013600

Clinton William 42 727552800

Bush George 41 601322400

Reagan Ronald 40 348861600