Читаем Linux программирование в примерах полностью

Рис. 14.2. Вершины дерева и их указатели

Для упрощения использования возвращенного указателя вы могли бы рассмотреть определение макроса:

#define tree_data(ptr, type)(*(type**)(ptr))

...

struct employee *e;

void *vp;

vp = tfind(&key, root, emp_name_id_compare);

if (vp != NULL) { /* it's there, use it */

 e = tree_data(vp, struct employee);

 /* использование сведений в *e ... */

}

<p>14.4.5. Обход дерева: <code>twalk()</code></p>

Функция twalk() объявлена в следующим образом:

typedef enum { preorder, postorder, endorder, leaf } VISIT;

void twalk(const void *root,

 void (*action)(const void *nodep, const VISIT which,

const int depth));

Первый параметр является корнем дерева (не указателем на корень). Второй является указателем на функцию обратного вызова, которая вызывается с тремя аргументами, указателем на исследуемую вершину дерева; типом перечисления, указывающим, как осуществляется обход данной вершины; и целого, обозначающего глубину текущей вершины (корень находится на глубине 0, как объяснялось ранее).

Использование функции обратного вызова здесь такое же, как для nftw() (см. раздел 8.4.3.2 «Функция обратного вызова nftw()»). Там функция обратного вызова вызывается для каждого объекта в файловой системе. Здесь функция обратного вызова вызывается для каждого объекта, хранящегося в дереве.

Есть несколько способов прохождения, или «обхода», двоичного дерева:

• Левая вершина, родительская вершина, правая вершина.

• Родительская вершина, левая вершина, правая вершина.

• Левая вершина, правая вершина, родительская вершина.

Функция GLIBC twalk() использует второй способ: сначала родительская вершина, затем левая, затем правая. Каждый раз при встрече с вершиной говорят, что она посещается.[159] В ходе посещения порожденной вершины функция должна посетить и родительскую. Соответственно, значения типа VISIT указывают, на какой стадии произошла встреча с этой вершиной:

preorder   До посещения порожденных.

postorder  После посещения первой, но до посещения второй порожденной вершины.

endorder   После посещения обеих порожденных.

leaf Эта вершина является концевой, не имеющей порожденных вершин.

ЗАМЕЧАНИЕ. Использованная здесь терминология не соответствует точно той, которая используется в формальных руководствах по структурированию данных. Там используются термины inorder, preorder и postorder для обозначения соответствующих трех перечисленных ранее способов прохождения дерева. Таким образом, twalk() использует прохождение по типу preorder, но использует именованные константы preorder и т.д. для обозначения того, на какой стадии была посещена вершина. Это может сбивать с толку.

Следующая программа, ch14-tsearch.c, демонстрирует построение и обход дерева. Она повторно использует структуру struct employee и функцию emp_name_id_compare() из раздела 6.2 «Функции сортировки и поиска».

1  /* ch14-tsearch.c --- демонстрация управления деревом */

2

3  #include

4  #include

5  #include

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  /* фамилии совпадают, проверить имена */

Перейти на страницу:

Похожие книги

1С: Бухгалтерия 8 с нуля
1С: Бухгалтерия 8 с нуля

Книга содержит полное описание приемов и методов работы с программой 1С:Бухгалтерия 8. Рассматривается автоматизация всех основных участков бухгалтерии: учет наличных и безналичных денежных средств, основных средств и НМА, прихода и расхода товарно-материальных ценностей, зарплаты, производства. Описано, как вводить исходные данные, заполнять справочники и каталоги, работать с первичными документами, проводить их по учету, формировать разнообразные отчеты, выводить данные на печать, настраивать программу и использовать ее сервисные функции. Каждый урок содержит подробное описание рассматриваемой темы с детальным разбором и иллюстрированием всех этапов.Для широкого круга пользователей.

Алексей Анатольевич Гладкий

Программирование, программы, базы данных / Программное обеспечение / Бухучет и аудит / Финансы и бизнес / Книги по IT / Словари и Энциклопедии
1С: Управление торговлей 8.2
1С: Управление торговлей 8.2

Современные торговые предприятия предлагают своим клиентам широчайший ассортимент товаров, который исчисляется тысячами и десятками тысяч наименований. Причем многие позиции могут реализовываться на разных условиях: предоплата, отсрочка платежи, скидка, наценка, объем партии, и т.д. Клиенты зачастую делятся на категории – VIP-клиент, обычный клиент, постоянный клиент, мелкооптовый клиент, и т.д. Товарные позиции могут комплектоваться и разукомплектовываться, многие товары подлежат обязательной сертификации и гигиеническим исследованиям, некондиционные позиции необходимо списывать, на складах периодически должна проводиться инвентаризация, каждая компания должна иметь свою маркетинговую политику и т.д., вообщем – современное торговое предприятие представляет живой организм, находящийся в постоянном движении.Очевидно, что вся эта кипучая деятельность требует автоматизации. Для решения этой задачи существуют специальные программные средства, и в этой книге мы познакомим вам с самым популярным продуктом, предназначенным для автоматизации деятельности торгового предприятия – «1С Управление торговлей», которое реализовано на новейшей технологической платформе версии 1С 8.2.

Алексей Анатольевич Гладкий

Финансы / Программирование, программы, базы данных