Способы построения и представления деревьев

     2. Практическая часть 
 

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

     Алгоритм работы программы:

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

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

#include <fstream.h>

    #include <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 type[l_type];        // Вид нарушения

     float price;               //Размер штрафа

     Fine* next;                 //Указатель на след.элемент 

     Struct Node {              //Узел дерева

     char namber[l_number];  //Номер автомашины

     fine*beg; //Указатель на начало поиска нарушений

     Node*left; //Указатель на левое поддерево

     Node right; //Указатель на правое поддерево

     }; 

     struct Data { Исходные данные

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

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

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

      float  price;                            // Размер штрафа

     };

     Node*  descent(Node* р);

     Node*  first(Data data);

      Data    input(Action action):

      int     menu();

     void    print_node(const Node& node);

     void   print_dbase(Node* p);

     Node*  read_dbase(char* filename);

     int     read_fine(ifstream f. Data& data);

     int     remove_fine(Node* p, const Data& data):

     void    remove_fines(Node* p);

     Node*  remove_node(Node* root. Node* p. Node* parent. Dir dir); Node*  remove_tree(Node* p);

     Node*  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 (menu()) {

     case 1: // Ввод сведений о нарушена

     if (!root) root = first(inputUNSERT));

     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;

     case 4: // Выход

     tout.open(filename);

     if (!fout.i s_open()) {

     cout << "Ошибка открытия файла " << filename << endl; return 1;

     }

     write_dbase(fout, root);

     return 0; 

     case 5: // Отладка

     print_dbase(root);

     break:

     default:

     cout << " Надо вводить число от 1 до 4" << endl;

       break;

        }

     }

     return 0;

     }

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

     Node* descent(Node* p) {

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

     if (!y->left) y->left = p->left: // 1

     else {

     do { prev = у; у = y->left; } // 2

     while(y->left);

     y->left     = p->left; // 3

     prev->left  = y->right; // 4

     y->right     = p->right: // 5

     }

     return y;

     }

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

     Node* firstCData 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->number, data.number, Ijiumber);

     root->beg  = beg;

     root->left = root->right= 0;

     return root;

     }

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

     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(templ, buf. 2); strncpy(temp2, &buf[3], 2);

     day = atoi(temp1): 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 (!(hour >= 0 && hour < 24 && min >= 0 && min < 60 )); 

     strcat(data.time. buf);

     cin.get();

     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.get();

     return data;

     }

     // ------------------------------------------------вывод меню

     int menu() {

     char buf[10];

     int option;

     do {

        cout <<”========================” <<endl;

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

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

        cout <<”3- Справка” <<endl;

        cout <<”4- выход” <<endl;

        cout <<”========================” <<endl; 

     cin >>buf;     option = atoi(buf);

     }

     While (!option);

     cin.get();

      return option;

     }

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

     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 *р) {

     if (р) {

      print_node(*p);

     print_dbase (p->left);

      print_dbase (p->right);

     }

     }

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

     Node * read_dbase (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 << "Пустой файл (0 байт)" << 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);