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

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