ется, поэтому функция get получает этот указатель через параметры и возвращает его новое значение.

Вспомним, что для структур определена операция присваивания, выполняющая поэлементное копирование, поэтому при занесении в очередь нет необходимости копировать отдельно каждое поле (см. строки, помеченные комментарием Копирование элемента , в функциях add и fi rst).

В этой программе для расширения знаний о стандартной библиотеке функций продемонстрирована работа с датами. Средства, необходимые для этого, определены в заголовочном файле <time.h>. Текущую дату и время можно получить с помощью функции time. Она возвращает ее в виде количества секунд, прошедших с полуночи 1 января 1970 года. Функция local time преобразует эту величину в стандартную структуру tm, определенную в том же заголовочном файле, и возвращает указатель на эту структуру. Поля структуры содержат все, что может потребоваться для работы с датами: год (точнее, количество лет, прошедших с 1900 года), месяц (от О до 11), день (от 1 до 31), час (от О до 23), минуту (0-59) и секунду (0-59). Ввод-вывод организован с помощью классов. Обратите внимание на использование метода get() класса i ostream в функциях get type и read dbase. Он необходим для считывания из входного потока признака конца строки с тем, чтобы следующий ввод производился из новой строки. Для хранения заявок из каждой очереди используются отдельные файлы.

ПРИМЕЧАНИЕ ---

В функции print, предназначенной для вывода отдельной заявки, использован манипулятор setiosflags, с помощью которого устанавливается выравнивание по левому краю. Для этого в манипулятор передается в качестве параметра константа left, определенная в классе ios (базовом для всех классов ввода-вывода). С помощью этой константы устанавливается соответствующий флаг состояния потока. Это, так сказать, информация для любознательных .

Задача 9.4. Бинарное дерево

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

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

1) ввод сведений о нарушении;

2) ввод сведений об оплате штрафа (удаление соответствующей записи о нарушении);

3) справка о нарушениях, совершенных на автомашине с заданным номером;

4) выход.

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

Каждый элемент (узел) дерева характеризуется уникальным ключом. Одинаковых номеров автомашин не бывает, поэтому логично использовать номера в качестве ключей. Кроме ключа, узел должен содержать две ссылки: на свое левое и правое поддерево. У всех узлов левого поддерева ключи меньше, чем ключ данного элемента, а у всех узлов правого поддерева - больше. В таком дереве, называемом деревом поиска, можно найти любой элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения ключа в каждом узле. Время поиска определяется высотой дерева, которая пропорциональна двоичному логарифму количества его элементов*.

Информационная часть каждого узла должна содержать ссылку на список нарушений. Опишем элемент списка нарушений (пгграф по-английски - fine ) и узел дерева поиска Node:

const int l time - 20. l type - 40. l number - 12:

Опишем общий алгоритм работы программы. При вводе нового нарушения запрашивается номер автомашины и выполняется поиск в базе. Если такая автомашина уже фигурирует в базе, в список ее нарушений добавляется новое, а если нет, то создаются новый узел дерева и первый элемент списка нарушений. При вводе информации об уплате штрафа выполняется поиск заданной автомашины, а затем - поиск соответствующего нарушения. При этом запрашивается

Сравните с линейным списком, в котором время поиска пропорционально количеству его элементов.

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

Как и в предыдущих примерах, после описания интерфейса программы, используемых структур данных и общего алгоритма следует разбить ее на функщ1И и определить интерфейс каждой из них.

Программа начинает работу с формирования двоичного дерева в динамической памяти из файла базы нарушений. Назовем функцию чтения read dbase. Интерфейс функции прост: она получает файл, из которого следует считывать информацию, а возвращает указатель на корень сформированного дерева:

Node* read dbase(char* filename): Наличие файла не обязательно - ведь надо же иметь возможность начать работать с пустой базой, не говоря уже о греющей душу автолюбителя вероятности гибели базы вследствие (не)преднамеренной порчи диска. При отсутствии файла выдается предупреждающее сообщение и возвращается нулевой указатель. Для реализации первого пункта меню (ввод сведений о нарушении) необходимо выполнить два отдельных действия: ввести нужную информацию и занести ее в дерево. Вводимые сведения удобно представить в виде структуры: struct Data { Исходные данные

char number[l number]: Номер автомашины

char time[l time]: Время нарушения

char type[l type]: Вид нарушения

float price: Размер штрафа

Функция с незамысловатым именем input будет запрашивать ввод этих данных, проверять их корректность и возвращать их в вызывающую функцию. Задумаемся, в каких еще случаях, кроме формирования нового нарушения, может потребоваться ввод данных? Он необходим и для второго, и для третьего пунктов меню, но набор сведений отличается: если для внесения данных в базу требуется вся информация (номер автомашины, время и вид нарушения, размер штрафа), то для удаления оплаченного штрафа необходимы только номер автомашины и время нарушения. Для получения справки вводится только номер машины. Чтобы ввод был сосредоточен в одной функции, опишем режим ее работы в виде перечисления и будем передавать этот режим в качестве параметра:

enum Action {INSERT. DEL. INFO}:

Data inputCAction action):

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

в функцию структуру Data. Функция возвращает указатель на созданный корень дерева:

Node * first(Data data): Занесение остальных узлов совместим с поиском, так как в обоих случаях требуется осуществлять спуск по дереву. Назовем функцию searchinsert. Для того чтобы ее можно было использовать и при удалении узла из дерева, нам пришлось расширить ее интерфейс, добавив туда, кроме указателя на корень дерева, заносимых/ искомых данных и режима работы, указатель на родителя узла и признак, к левому или правому поддереву родителя принадлеж1гг искомый узел. Функция возвращает указатель на найденный/вставленный узел:

enum Dir {LEFT. RIGHT}:

Node* search insert(Node* root, const Data& data. Action action. Dir& dir. Node*& parent): Признак типа Di r передается в вызывающую функцию по ссылке, а указатель на родительский узел - по адресу, чтобы можно было передать наружу их значения.

ВНИМАНИЕ!--

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

Функция удаления записи об одном нарушении removefine получает в качестве параметра указатель на узел, из списка которого следует удалить запись, а также время нарушения, которое служит ключом списка. Время для единообразия передается в составе структуры Data. Функция удаляет запись из списка или выдает информацию о том, что запись не найдена, и возвращает признак, по которому можно определить, пуст ли список нарушений:

int remove fine(Node* p. const Data& data): Если список пуст, необходимо удалить соответствующий узел дерева. Для этого служит функция remove node:

Node* remove node(Node* root. Node* p. Node* parent. Dir dir): Ради этой функции мы и вводили в состав параметров функции поиска searchinsert указатель на родительский узел и признак левого или правого поддерева, поскольку надо куда-то привязать поддеревья удаляемого узла. Удалить можно любой узел, в том числе и корневой, поэтому функция removenode должна возвращать указатель на корень дерева на тот случай, если он изменится.

Для получения справки о нарушениях, совершенных на автомашине с заданным номером, служит простая функция printnode с соответствующим узлом дерева в качестве параметра:

void print node(const Node& node):

По окончании работы с базой она выводится в файл, для этого служит функция write dbase. Ей передается файл, в который будет выводиться информация, и указатель на корень дерева:

void write dbase(ofstream f. const Node* root);

Почему мы в данном случае передаем в функцию не имя файла, а уже открытый выходной поток, мы объясним позже, при анализе соответствующего алгоритма. Разбиение программы на функции и спецификация их интерфейсов - процесс итеративный, поскольку сразу обычно не удается учесть все детали и тонкости. Однако мы от дущи рекомендуем вам уделять этому этапу как можно больше вни-MannnS поскольку чем четче разделена программа на независимые части, тем меньше времени потребует ее отладка.

Приведем текст программы, а затем дадим необходимые пояснения по алгоритмам работы ее функций.

#include <fstream.h> #i ncl ude <stdlib.h> #include <string.h> #include <time.h> #include <iomanip.h>

const char* filename dbase : enum Action {INSERT. DEL. INFO}: enum Dir {LEFT. RIGHT}:

const int l time - 20. l type = 40. l number - 12:

struct Fine { char time[l time]; char typed type]; float price: Fine* next:

struct Node { cha г number[1 number]: Fine* beg: Node* left: Node* right:

struct Data { char number[l number]: char time[l time]: char type[l type]: float price:

Штраф (элемент списка) Время нарушения Вид нарушения Размер штрафа

Указатель на следующий элемент

Узел дерева

Номер автомашины

Указатель на начало списка нарушений Указатель на левое поддерево Указатель на правое поддерево

Исходные данные

Номер автомашины

Время нарушения

Вид нарушения

Размер штрафа

Node*

Node*

Data

void

void

Node*

void

Node*

Node*

Node*

descent(Node* p): first(Data data): input(Action action): menuO:

print node(const NodeS node): print dbase(Node* p): read dbase(char* filename): read fine(ifstream f. Data& data): remove fine(Node* p. const Data& data): remove fines(Node* p):

remove node(Node* root. Node* p. Node* parent. Dir dir): remove tree(Node* p):

search insert(Node* root, const Data& data. Action action, Dir& dir. Node*& parent): void write dbase(ofstream f. const Node* root): void write node(ofstream f. const Node& node):

............................. Главная функция

int main(){ Node* p. *parent:

Node* root - read dbase(filename): ofstream fout:

Ввод сведений о нарушении

Хотя, положа руку на сердце, мы сами не всегда следуем своим советам.

Dir dir: while (true) {

switch (roenuO) {

case 1:

if (!root) root - first(input(INSERT)):

else search insert(root. input(INSERT), INSERT, dir. parent):

break:

case 2: Ввод сведений об оплате штрафа

if (!root) { cout База пуста endl: break: }

Data data = input(DEL):

if (!(p search insert(root, data. DEL, dir. parent)))

cout Сведения об а/м отсутствуют endl: else

if (remove fine(p, data) = 2) Удалены все нарушения

root = remove node(root, p. parent, dir); break;

case 3: Справка

if (. root) { cout База пуста endl; break; }

if (!(p = search insert(root. input(INFO). INFO, dir, parent)))

cout Сведения отсутствуют endl; else print node(*p): break;