Читать книгу 📗 "Linux программирование в примерах - Роббинс Арнольд"
struct employee { /* Из главы 6 */ char lastname[30]; char firstname[30]; long emp_id; time_t start_date;};/* emp_name_id_compare --- сравнение по имени, затем no ID */int emp_name_id_compare(const void *e1p, const void *e2p) { /* ...также из главы 6, полностью представлено позже... */}struct employee key = { ... };void *vp, *root;struct employee *e;/* ...заполнение данными... */vp = tfind(&key, root, emp_name_id_compare);if (vp != NULL) { /* it's there, use it */ e = *((struct employee**)vp); /* Получить хранящиеся в дереве данные */ /* использование данных в *е ... */}Как можно указатель на вершину использовать как указатель на указатель данных? Рассмотрим, как была бы реализована вершина двоичного дерева. В каждой вершине хранится по крайней мере указатель на элемент данных пользователя и указатели на потенциальные порожденные вершины справа и слева. Поэтому она должна выглядеть примерно так.
struct binary_tree { void *user_data; /* Указатель на данные пользователя */ struct binary_tree *left; /* Порожденная вершина слева или NULL */ struct binary_tree *right; /* Порожденная вершина справа или NULL *//* ...здесь возможны другие поля... */} node;С и C++ гарантируют, что поля внутри структуры располагаются в порядке возрастания адресов. Таким образом, выражение '
&node.left < &node.right&node == &node.user_dataСледовательно, концептуально '
е = *((struct employee**)vp);1.
vpvoid*void*2. '
(struct employee**)vpstruct employee3. '
*((struct employee**)vp)struct employee**struct employee*4. '
е = *((struct employee**)vp)'еИдея проиллюстрирована на рис. 14.2.
Рис. 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 ... */}14.4.5. Обход дерева:
twalk()Функция
twalk()<search.h>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()nftw()Есть несколько способов прохождения, или «обхода», двоичного дерева:
• Левая вершина, родительская вершина, правая вершина.
• Родительская вершина, левая вершина, правая вершина.
• Левая вершина, правая вершина, родительская вершина.
Функция GLIBC
twalk()VISITpreorder postorder endorder leafЗАМЕЧАНИЕ. Использованная здесь терминология не соответствует точно той, которая используется в формальных руководствах по структурированию данных. Там используются термины inorder, preorder и postorder для обозначения соответствующих трех перечисленных ранее способов прохождения дерева. Таким образом,
twalk()preorder
