14.4.3. Ввод элемента в дерево: tsearch()

14.4.3. Ввод элемента в дерево: tsearch()

Эти процедуры выделяют память для вершин дерева. Для их использования с несколькими деревьями нужно предоставить им указатель на переменную void*, в которую они заносят адрес корневой вершины. При создании нового дерева инициализируйте этот указатель в NULL:

void *root = NULL; /* Корень нового дерева */

void *val; /* Указатель на возвращенные данные */

extern int my_compare(const void*, const void*); /* Функция сравнения */

extern char key[], key2[]; /* Значения для ввода в дерево */

val = tsearch(key, &root, my_compare);

 /* Ввести в дерево первый элемент */

/* ...заполнить key2 другим значением. НЕ изменять корень... */

val = tsearch(key2, &root, my_compare);

 /* Ввести в дерево последующий элемент */

Как показано, в переменной root должен быть NULL лишь в первый раз, после чего нужно оставить ее как есть. При каждом последующем вызове tsearch() использует ее для управления деревом.

Когда разыскиваемый key найден, как tsearch(), так и tfind() возвращают указатель на содержащую его вершину. Поведение функций различно, когда key не найден: tfind() возвращает NULL, a tsearch() вводит в дерево новое значение и возвращает указатель на него. Функции tsearch() и tfind() возвращают указатели на внутренние вершины дерева. Они могут использоваться в последующих вызовах в качестве значения root для работы с поддеревьями. Как мы вскоре увидим, значение key может быть указателем на произвольную структуру; он не ограничен символьной строкой, как можно было бы предположить из предыдущего примера.

Эти процедуры сохраняют лишь указатели на данные, использующиеся в качестве ключей. Соответственно это ваше дело управлять памятью для хранения значений данных, обычно с помощью malloc().

ЗАМЕЧАНИЕ. Поскольку функции деревьев хранят указатели, тщательно позаботьтесь о том, чтобы не использовать realloc() для значений, которые были использованы в качестве ключей! realloc() может переместить данные, вернув новый указатель, но процедуры деревьев все равно сохранят висящие (dangling) указатели на старые данные.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

РЫНКИ: Убей дерево

Из книги Журнал «Компьютерра» № 36 от 3 октября 2006 года автора Журнал «Компьютерра»

РЫНКИ: Убей дерево Автор: Владимир ГуриевВ сентябре 2006 года стало известно сразу о нескольких инициативах крупных компаний на рынке электронных книг. Sony объявила о выходе Sony Reader и открытии магазина цифровых книг. Panasonic показал прототип своей электронной книги с цветным


Семантическое DOM-дерево

Из книги Разгони свой сайт автора Мациевский Николай

Семантическое DOM-дерево Логическим продолжением уже проведенных исследований CSS/DOM-производительности браузеров стало рассмотрение зависимости времени создания документа от числа тегов (узлов дерева). Раздельно были проанализированы случаи, когда DOM-дерево является


Дерево модели

Из книги КОМПАС-3D V10 на 100 % автора Кидрук Максим Иванович

Дерево модели Древовидное представление трехмерной модели (сборки или детали) в девятой версии претерпело значительные изменения. В частности, была добавлена возможность представления состава модели в виде структурированных разделов (рис. 1.72, а). При этом элементы


Wood (Дерево)

Из книги Photoshop. Лучшие фильтры автора Бондаренко Сергей

Wood (Дерево) Текстура дерева имеет большое значение при разработке дизайна. Рисунок поверхности среза дерева часто используется для декорирования объектов интерьера. Рисунок дерева наносится на предметы мебели, сделанные из ДСП, пластика и других материалов, бытовую


5.6 Всемирное дерево имен

Из книги TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) автора Фейт Сидни М

5.6 Всемирное дерево имен Имена Интернета структурированы как дерево (см. рис. 5.1). Каждому узлу дерева присвоена метка. Каждый узел дерева имеет имя, называемое именем домена (domain name). Имя домена для узла создается из меток, проходимых по пути от этого узла до вершины дерева.


20.5.1 Дерево SMI

Из книги Программирование на языке Пролог для искусственного интеллекта автора Братко Иван

20.5.1 Дерево SMI Вспомним, что первоначально SNMP предполагался как временное решение до выпуска стандартов управления ISO. На рис. 20.4 дерево администрирования/именования отражает первичные попытки согласования с ISO. Рис. 20.4. Дерево администрирования и именования SMIУзлы вверху


10.2. AVL-дерево: приближенно сбалансированное дерево

Из книги КОМПАС-3D для студентов и школьников. Черчение, информатика, геометрия автора Большаков Владимир

10.2. AVL-дерево: приближенно сбалансированное дерево AVL-дерево — это дерево, обладающее следующими свойствами:(1) Левое и правое поддеревья отличаются по глубине не более чем на 1.(2) Оба поддерева являются AVL-деревьями.Деревья, удовлетворяющие этому определению, могут быть


2.6. Дерево модели

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

2.6. Дерево модели Дерево построения документа — структурированный список («дерево») объектов, отражающий последовательность создания документа. Отображение значка «+» рядом с объектом означает, что он имеет подчиненные объекты. Чтобы развернуть их список, щелкните


Вставка в красно-черное дерево

Из книги Linux автора Стахнов Алексей Александрович

Вставка в красно-черное дерево Теперь, когда мы ознакомились с правилами, определяющими структуру красно-черного дерева, возникает вопрос, как их использовать для вставки нового узла в красно-черное дерево? Начнем со знакомой операции, и выполним поиск узла. Если он будет


Сортирующее дерево

Из книги Linux программирование в примерах автора Роббинс Арнольд

Сортирующее дерево Классическая структура данных, используемая для создания очереди по приоритету, известна под названием сортирующего дерева (или "кучи"). Сортирующее дерево (heap), на которое еще ссылаются как на частично упорядоченное полное двоичное дерево, - это


Вставка в сортирующее дерево

Из книги Разработка ядра Linux автора Лав Роберт

Вставка в сортирующее дерево Рассмотрим алгоритмы вставки и удаления. Вначале ознакомимся со вставкой. Чтобы вставить элемент в сортирующее дерево, мы добавляем его в конец этого дерева, в единственную позицию, которая соответствует требованию полноты (на рис. 5 этой


Глава 5 Дерево каталогов Linux

Из книги автора

Глава 5 Дерево каталогов Linux Эта глава полностью посвящена структуре и размещению каталогов и файлов в Linux. Поскольку для различных дистрибутивов структура может слегка отличаться, для определенности будем рассматривать дистрибутив Red Hat 7.1.Для того чтобы ориентироваться


Дерево исходных кодов ядра

Из книги автора

Дерево исходных кодов ядра Дерево исходных кодов ядра содержит ряд каталогов, большинство из которых также содержит подкаталоги. Каталоги, которые находятся в корне дерева исходных кодов, и их описание приведены в табл. 2.1.Таблица 2.1. Каталоги в корне дерева исходных


Дерево семейства процессов

Из книги автора

Дерево семейства процессов В операционной системе Linux существует четкая иерархия процессов. Все процессы являются потомками процесса init, значение идентификатора PID для которого равно 1. Ядро запускает процесс init на последнем шаге процедуры загрузки системы. Процесс init, в


Базисное дерево

Из книги автора

Базисное дерево Так как ядро должно проверять наличие страниц в страничном кэше перед тем, как запускать любую операцию страничного ввода-вывода, то этот поиск должен выполняться быстро. В противном случае затраты на поиск могут свести на нет все выгоды кэширования (по