сится в корень дерева с помощью функции f i rst, затем организуется цикл по всем остальным нарушениям данной автомашины, если они есть. Нарушения добавляются в список с помощью функции search insert.

Далее аналогичные действия производятся для всех остальных автомашин. Конечно, можно было бы не искать требуемый узел и конец списка нарушений заново для каждого нарушения из списка, а хранить соответствующие указатели, но это потребовало бы дополнительного кода и не дало бы существенного выигрыша во времени, так как база считывается всего один раз до начала работы.

Наверно, вы обратили внимание на то, что в меню четыре пзкта, а в операторе switch главной функции пять вариантов выбора. Последний вариант не входит в интерфейс пользователя, он может понадобиться программисту при отладке или сопровождении программы. Для удобства отладки была написана рекурсивная функция вывода всей базы printdbase. Она аналогична функции вывода базы в файл.

Функция поиска с включением searchinsert исчерпывающе, на наш взгляд, документирована в программе. Кроме того, описание аналогичной функции приведено в Учебнике на с. 125, поэтому мы не будем рассматривать ее подробно.

Лучше обратим наше внимание на более интересную функцию rerovenode, которая удаляет узел из дерева.

Процесс удаления можно разбить на этапы:

□ найти узел, который будет поставлен на место удаляемого;

□ реорганизовать дерево так, чтобы не нарушились его свойства;

□ присоединить новый узел к узлу-предку удаляемого узла;

□ освободить память из-под удаляемого узла.

Удаление узла происходит по-разному в зависимости от его расположения в дереве. Если узел является листом, то есть не имеет потомков, достаточно обнулить соответствующий указатель узла-предка (рис. 9.1). Если узел имеет только одного потомка, то этот потомок ставится на место удаляемого узла, а в остальном дерево не изменяется (рис. 9.2). Хуже всего, когда у узла есть оба потомка, но и здесь есть простой особый случай: если у его правого потомка нет левого потомка, удаляемый узел заменяется своим правым потомком, а левый потомок удаляемого узла подключается вместо отсутствующего левого потомка. Согласимся, что звучит не очень понятно, поэтому рассмотрите этот случай на рис. 9.3.

В общем же случае на место удаляемого узла помещается самый левый лист его правого поддерева (или наоборот - самый правый лист его левого поддерева). Это не нарушает свойств дерева поиска. Этот случай иллюстрируется на рис. 9.4.

Рис. 9.2. Удаление узла с одним потомком

Рис. 9.3. Удаление узла с двумя потомками

Рис. 9.1. Удаление узла, не имеющего потомков

Рис. 9.4. Удаление узла (общий случай)

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

Рассмотрим реализацию этого алгоритма в программе remove node. В функцию передается указатель на удаляемый узел р. Сначала находим указатель на узел у, который должен заменить удаляемый.

Если у узла р нет левого поддерева, на его место будет поставлена вершина (возможно, пустая) его правого поддерева (оператор И).

Иначе, если у узла р нет правого поддерева, на его место будет поставлена вершина его левого поддерева (оператор 12).

В противном случае оба поддерева узла существуют, и для определения заменяющего узла вызывается вспомогательная функция descent, выполняющая спуск по дереву.

В этой функции прежде всего проверяется особый случай, описанный выше (оператор 1). Если же условие отсутствия левого потомка у правого потомка удаляемого узла не выполняется, организуется цикл (оператор 2), на каждой итерации ко1Х)рого указатель на текущий узел запоминается в переменной prev, а указатель у смещается вниз и влево по дереву до того момента, пока не станет ссылаться на узел, не имеющий левого потомка, - он-то нам и нужен!

В операторе 3 к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла (оператор 5), требуется пристроить его собственное правое поддерево. Мы присоединяем его к левому поддереву предка заменяющего узла у (оператор 4), поскольку этот узел перейдет на новое место.

Функция descent возвращает указатель на узел, заменяющий удаляемый. Если мы удаляем корень дерева, надо обновить указатель на корень (оператор 14), иначе - присоединить этот указатель к соответствующему поддереву предка удаляемого узла (оператор 15).

После того как узел удален из дерева, освобождается занимаемая им память (опе- ратор 16).

ПРИМЕЧАНИЕ -

Для дерева большой размерности глубина рекурсии может быть весьма значительной, что может привести к переполнению стека. Более безопасно, хотя и более сложно, реализовы-вать рекурсию самостоятельно с помощью структуры данных *стек .

Как вы могли убедиться, работа с динамическими структурами данных требует внимания и тщательности. Однако можно заметить, что в различных задачах изменяется только информационная часть компонент, а принципы работы со стеком, очередью или списком остаются неизменными, поэтому фактически функции для работы с каждой из этих структур пишутся и отлаживаются один раз. Разработчики языка тоже заметили этот факт и включили в стандартную библиотеку С++ так называемые шаблоны, реализующие основные динамические структуры данных. Во второй части практикума мы рассмотрим применение этих шаблонов. Для их понимания вам придется изучить многие средства и возможности С++, но предпринятые усилия быстро себя окупят.

Давайте повторим наиболее важные моменты этого семинара.

1. Динамическими структурами данных называются блоки в динамической памяти, связанные друг с другом с помощью указателей.

2. Динамические структуры различаются способами связи отдельных элементов и допустимыми операциями над ними.

3. Элемент любой динамической структуры данных состоит из информационных полей и полей указателей.

4. Наиболее распространенными структурами являются линейный список (од-носвязный или двусвязный), стек, очередь и бинарное дерево.

5. Для стека определены операции помещения элемента в вершину и выборки элемента из вершины.

6. Для очереди определены операции помещения элемента в конец очереди и выборка элемента из ее начала.

7. Допускается вставлять и удалять элементы в произвольное место линейного списка.

8. Бинарное дерево состоит из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья. На каждый узел имеется ровно одна ссылка.

9. Каждый узел дерева характеризуется уникальным ключом.

10. Допускается вставлять и удалять элементы в произвольное место дерева.

И. Если для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева - больше, то такое дерево называется деревом поиска. В дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения ключа в каждом узле, что гораздо эффективнее поиска в списке.

12. Динамические структуры в некоторых случаях более эффективно реализовы-вать с помощью массивов (см. Учебник, с. 126).

Задания

Задания этого семинара соответствуют приведенным в Учебнике на с. 165.

Вариант 1

Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке.

Сведения о каждом автобусе включают:

□ номер автобуса;

□ фамилию и инициалы подателя;

□ номер маршрута. Программа должна обеспечивать:

□ начальное формирование данных обо всех автобусах в парке в виде списка;

□ при выезде каждого автобуса из парка вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся в парке, и записывает эти данные в список автобусов, находящихся на маршруте;

□ при въезде каждого автобуса в парк вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся на маршруте, и записывает эти данные в список автобусов, находящихся в парке;

□ по запросу выдаются сведения об автобусах, находящихся в парке, или об автобусах, находящихся на маршруте.

Вариант 2

Составить программу, которая содержит текущую информацию о книгах в библиотеке.

Сведения о книгах включают:

□ номер УДК;

□ фамилию и инициалы автора;

□ название;

□ год издания;

□ количество экземпляров данной книги в библиотеке. Программа должна обеспечивать:

□ начальное формирование данных обо всех книгах в библиотеке в виде двоичного дерева;

□ добавление данных о книгах, вновь поступающих в библиотеку;

□ удаление данных о списываемых книгах;

□ по запросу выдаются сведения о наличии книг в библиотеке, упорядоченные по годам издания.

Вариант 3

Составить программу, которая содержит текущую информацию о заявках на авиабилеты.

Каждая заявка включает:

□ пункт назначения;

□ номер рейса;

□ фамилию и инициалы пассажира;

□ желаемую дату вылета. Программа должна обеспечивать:

□ хранение всех заявок в виде списка;

□ добавление заявок в список;

□ удаление заявок;

□ вывод заявок по заданному номеру рейса и дате вылета;

□ вывод всех заявок.

Вариант 4

Составить программу, которая содержит текущую информацию о заявках на авиабилеты.

Каждая заявка включает:

□ пункт назначения;

□ номер рейса;

□ фамилию и инициалы пассажира;

□ желаемую дату вылета; Программа должна обеспечивать:

□ хранение всех заявок в виде двоичного дерева;

□ добавление и удаление заявок;

□ по заданному номеру рейса и дате вылета вывод заявок с их последующим удалением;

□ вывод всех заявок.

Вариант 5

Составить программу, которая содержит текущую информацию о книгах в библиотеке.

Сведения о книгах включают:

□ номер УДК;

□ фамилию и инициалы автора;

□ название;

□ год издания;

□ количество экземпляров данной книги в библиотеке. Программа должна обеспечивать:

□ начальное формирование данных обо всех книгах в библиотеке в виде списка;

□ при выдаче каждой книги на руки вводится номер УДК, и программа уменьшает значение количества книг на единицу или выдает сообщение о том, что требуемой книги в библиотеке нет или требуемая книга находится на руках;

□ при возвращении каждой книги ввод1тся номер УДК, и программа увеличивает значение количества книг на единицу;

□ по запросу выдаются сведения о наличии книг в библиотеке.

Вариант 6

Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке.

Сведения о каждом автобусе включают:

□ номер автобуса;