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

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

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

160

Этот вывод для часового пояса U.S. Eastern Time zone — Примеч. автора.

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

14.4.6. Удаление вершины дерева и удаление дерева:

tdelete

и

tdestroy

Наконец, вы можете удалить элементы из дерева и, на системах GLIBC, удалить само дерево целиком:

void *tdelete(const void *key, void **rootp,

int (*compare)(const void*, const void*));

/* Расширение GLIBC, в POSIX нет: */

void tdestroy(void *root, void (*free_node)(void *nodep));

Аргументы для

tdelete

те же, что и для

tsearch

: ключ, адрес корня дерева и функция сравнения. Если в дереве найден данный элемент, он удаляется, и

tdelete

возвращает указатель на родительскую вершину. В противном случае возвращается

NULL

. С этим поведением следует обращаться в своем коде осмотрительно, если вам нужен первоначальный удаляемый элемент, например, для освобождения занимаемой им памяти.

struct employee *е, key; /* Объявления переменных */

void *vp, *root;

/* ...заполнить ключ для удаляемого из дерева элемента... */

vp = tfind(&key, root, emp_name_id_compare); /* Найти удаляемый элемент */

if (vp != NULL) {

 e = *((struct employee**)vp); /* Преобразовать указатель */

 free(e); /* Освободить память */

}

(void)tdelete(&key, &root, emp_name_id_compare); /* Теперь удалить его из дерева */