case 4: fout.open(fi1ename): if (!fout.is open()) { cout Ошибка открытия файла

wri te dbase(fout. root); return 0:

Выход

filename endl: return 1:

Надо вводить число от 1 до 4 endl:

case 5:

print dbase(root):

break: default:

cout

break:

return 0:

-------------------......----Спуск no дереву

Node* descent(Node* p)*{

Node* prev, *y = p->right:

if (!y->left) y->left - p->left:

else {

do { prev - y: у - y->left: } while(y->left): y->left - p->left: prev->left = y->right: y->right p->right:

return y:

-..... Формирование корневого элемента дерева

Node* first(Data data) {

Создание записи о нарушении:

Fine* beg = new Fine:

strncpy(beg->time. data.time, l time):

strncpy(beg->type, data.type, l type):

beg->price = data.price:

beg->next 0:

Создание первого узла дерева:

Node* root - new Node:

strncpy(root->nurrt)er. data.nuntoer. l number):

root->beg = beg:

root->1eft - root->right - 0:

return root:

Отладка

3 4 5

-----.........................Ввод нарушения

Data input(Action action) { Data data:

char buf[10]. templ[3]. temp2[3]: int day, month, hour, min: cout Введите номер а/и endl: cin.getline(data.number. l number): if (action = INFO) return data:

do {

cout Введите дату нарушения в формате ДД.ММ.ГГ: endl cin buf:

strncpy(tempi, buf. 2): strncpy(temp2. &buf[3]. 2): day - atoi(tempi); month = atoi(temp2):

while (!(day > 0 && day < 32 && month > 0 && month < 13 )): strcpy(data.time. buf); strcat(data.time. ); do {

cout Введите время нарушения в формате ЧЧ:ММ : endl: cin buf:

strncpy(templ. buf. 2): strncpy(temp2. &buf[3], 2): hour atoi(tempi); min = atoi(temp2):

while (Khour >= 0 && hour < 24 && min >= 0 && min < 60 )):

strcat(data.time. buf): Cin.getO:

if (action ~ DEL) return data:

cout Введите тип нарушения type endl: cin.getline(data.type. l type):

do {

cout Введите размер штрафа: endl: cin buf:

while (!(data.price = (float)atof(buf))):

Cin.getO:

return data:

---..................-.....-......Вывод меню

int menuO {

Char buf[10]:

int option:

do { cout

endl:

cout 1 - Ввод сведений о нарушении endl:

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

cout 3 - Справка endl:

cout 4 - Выход endl:

cin buf; option = atoi(buf):

while (!option): cin.getO: return option;

........------Вывод Ma экран сведений об а/и

void print node(const Node& node) { cout Номер а/м: node.number endl: Fine* pf - node.beg; float summa - 0; while (pf) {

cout Вид нарушения: pf->type endl;

cout Дата и время: pf->time;

cout Размер штрафа: pf->price endl;

summa += pf->price:

pf = pf->next:

cout Общая сумма штрафов: summa endl;

---..............Вывод на экран всего дерева

void print dbase(Node *p) {

if (P) { print node(*p): print dbase (p->left): print dbase (p->right):

--.............---------Чтение базы из файла

Node * read dbas€ (char* filename) {

Node *parent:

Dir dir;

Data data;

ifstream f(filename, ios::in ios::nocreate);

if (!f) { cout Нет файла filename endl; return 0;}

f.getline(data.number. l number);

if(f.eof()) { cout Пустой файл (О байт) endl; return 0;} read fine(f, data); Первое нарушение

Node* root = first(data): Формирование корня дерева

while (!read fine(f, data)) Последующие нарушения search insert(root, data. INSERT, dir. parent);

Формирование дерева:

while (f.getline(data.number. l number)) { Номер а/м read fine(f. data): Первое нарушение

search insert(root, data, INSERT, dir, parent); while (!read fine(f, data)) Последующие нарушения search insert(root. data. INSERT, dir. parent);

return root:

.....- Чтение из файла информации о нарушении

int read fine(ifstream f, Data& data) { f.getline(data.time. l time):

if(data.time[0] ) return 1: Конец списка нарушений f.getline(data.type, l type); f data.price; f.getO:

return 0: Нарушение считано успешно

-------........ Удаление нарушения из списка

int remove fine(Node* р, const Data& data) {

Fine* prev, *pf = p->beg:

bool found - false:

while (pf && !found) { Цикл no списку нарушений if(!strcmp(pf->time. data.time))

found = true; Нарушение найдено

else { prev = pf;

pf pf->next; Переход к следующему элементу списка

if (!found) {

cout Сведения о нарушении отсутствуют. endl; return 1;

Номер а/м

if (pf = p->beg)

p->beg - pf->next; else

prev->next = pf->next; delete pf: Освобождение памяти из-под элемента

Удаление из начала списка Удаление из середины или конца списка

if (!p->beg) return 2; return 0:

Список пуст

.....-..................Удаление узла дерева

Node* refflOve node(Node* root. Node* p. Node* parent. Dir dir) {

Node *y: Узел, заменяющий удаляемый

if (!p->left) у - p->right:

else if (!p->right) у = p->left:

else у = descent(p):

if (p - root) root = y:

else {

if (dir = LEFT) parent->left = y: else parent->right = y:

delete p; return root:

.......................... Поиск с включением

Node* search insert(Node* root, const Data& data. Action action. Dir& dir. Node*& parent) { Node* p - root: Указатель на текущий элемент

bool found - false: Признак успешного поиска int cmp: Результат сравнения ключей

parent 0:

while (р && !found) { Цикл поиска по дереву cmp - strcmp(data.number. p->number): Сравнение ключей

if (!cmp) found - true: Нашли!

else { parent = p:

if (cmp < 0) { p = p->left: dir = LEFT: } Спуск влево else { p = p->right: dir - RIGHT: } Спуск вправо

if (action != INSERT) return p:

Создание записи о нарушении:

Fine* pf new Fine:

strncpy(pf->time, data.time. l time):

strncpy(pf->type. data.type. l type):

pf->price = data.price:

pf->next - 0:

if (Ifound) { Создание нового узла: p = new Node:

11 12 13 14 15

16

strncpy(p->number. data.number. l number):

p->beg = pf:

p->left = p->right - 0:

if (dir = LEFT) Присоединение к левому поддереву предка:

parent->left = р: else Присоединение к правому поддереву предка:

parent->right р:

else { Узел существует, добавление нарушения в список Fine* temp p->beg:

while (temp->next) temp = temp->next: Поиск конца списка temp->next pf:

return p:

.......-...............- Вывод базы в файл

void write dbase(ofstream f, const Node *p) {

if (P) { write node(f, *p): write dbase (f. p->left): write dbase (f. p->right):

................ Вывод в файл сведений об а/м

void write node(ofstream f. const Node& node) {

f node.number endl:

Fine* pf node.beg:

while(pf) {

f pf->time endl pf->type endl pf->price endl: pf - pf->next:

f = endl: Признак окончания сведений об а/м

Рассмотрим функцию записи дерева в файл wri tedbase. Поскольку дерево - структура рекурсивная, удобно будет сделать эту функцию рекурсивной. Для каждого поддерева в файл выводятся сведения о корне, затем о левом и правом поддереве. Именно из-за рекурсии мы открыли файл вне этой функции и передали в нее готовый к записи поток. Для вывода информации об одном узле используется вспомогательная функция wri tenode. Для простоты данные выводятся в текстовом виде в отдельные строки (в реальной системе пришлось бы их хитроумно зашифровать). Признаком окончания списка нарушений для одной автомашины служит символ Он используется при чтении базы из файла.

Функция чтения из файла readdbase весьма проста. В ней используется вспомогательная функция считывания записи об одном нарушении readf ine. Сначала вводится информация о номере первой автомашины и ее первом нарушении и зано-