main.cpp

#include <fstream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <clocale>

using namespace std;

char* filename = "dbase.txt";
enum Action { INSERT, DEL, INFO };
enum Dir { LEFT, RIGHT };
const int l_time = 20, l_FIO = 40, l_Punct_nazn = 12;
struct Fine {//--------------Çàÿâêà (ýëåìåíò ñïèñêà)
    char time[l_time];//Âðåìÿ âûëåòà
    char FIO[l_FIO];//Ôàìèëèÿ è èíèöèàëû ïàññàæèðà
    float nomer;//Íîìåð ðåéñà
    Fine* next;//Óêàçàòåëü íà ñëåäóþùèé ýëåìåíò
};

struct Node {//-----------------Óçåë äåðåâà
char Punct_nazn[l_Punct_nazn];//Ïóíêò íàçíà÷åíèÿ
Fine* beg;//Óêàçàòåëü íà íà÷àëî ñïèñêà íàðóøåíèé
Node* left;//Óêàçàòåëü íà ëåâîå ïîääåðåâî
Node* right;//Óêàçàòåëü íà ïðàâîå ïîääåðåâî
};

struct Data {//-----------------Èñõîäíûå äàííûå
char Punct_nazn[l_Punct_nazn];//Ïóíêò íàçíà÷åíèÿ
char time[l_time];//Âðåìÿ âûëåòà
char FIO[l_FIO];//Ôàìèëèÿ è èíèöèàëû ïàññàæèðà
float nomer;//Íîìåð ðåéñà
};

Node *descent( Node* p );
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() { //-----------------------------Ãëàâíàÿ ôóíêöèÿ--------------------
	setlocale(LC_ALL, "Rus");
	Node* p, *parent;
	Node* root = read_dbase( filename );
	ofstream fout;
	Dir dir;
	while ( true ) {
		switch ( menu() ) {
			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:{// Âûâîä âñåõ çàÿâîê
				ifstream f( filename, ios::in);
                string a,b,c,n;
                float d; int i=1;
                if(!(f>>a)){
                     cout<<"Íåò äàííûõ\n";
                     goto label1;
                }
                while(1){
                  f>>b>>c>>d>>n;
                  cout<<"-----------Çàÿâêà ¹"<<i<<"--------------\n";
                  cout<<"\n  Ïóíêò íàçíà÷åíèÿ: "<<a<<endl<<"  Äàòà âûëåòà: "<<b<<endl<<"  FIO: "<<c<<endl<<"  Íîìåð ðåéñà: "<<d<<"\n\n";
                  if(!(f>>a)) break; i++;
                }
                label1:
                f.close();
 				break;
			}
			case 4:	// Âûõîä
				fout.open( filename );
 				if ( !fout.is_open() ) {
 					cout << "Îøèáêà îòêðûòèÿ ôàéëà " << filename; return 1;
				}
 				write_dbase( fout, root );
 				return 0;
			case 5: print_dbase( root ); break;			// Îòëàäêà
			default: cout << " Íàäî ââîäèòü ÷èñëî îò 1 äî 4" << endl; break;
		}
	}
}

Node* descent( Node* p ) {// -----------------------------Ñïóñê ïî äåðåâó
Node* prev, *y = p->right;
if ( !y->left)
   y->left=p->left;// 1
else {
   do {
        prev = y; y = y->left;}// 2
   while( y->left);
   y->left= p->left;// 3
   prev->left= y->right;// 4
   y->right= p->right;// 5
}
return y;
}

Node* first( Data data ) {// -------------Ôîðìèðîâàíèå êîðíåâîãî ýëåìåíòà äåðåâà
// Ñîçäàíèå çàïèñè î çàÿâêå:
   Fine* beg = new Fine;
   strncpy( beg->time,data.time, l_time );
   strncpy( beg->FIO,data.FIO, l_FIO );
   beg->nomer= data.nomer;
   beg->next= 0;// Ñîçäàíèå ïåðâîãî óçëà äåðåâà:
   Node* root = new Node;
   strncpy( root->Punct_nazn,data.Punct_nazn, l_Punct_nazn );
   root->beg= beg;root->left=root->right= 0;
   return root;
}

Data input( Action action ) { // ---------------------------------Ââîä çàÿâêè
   Data data;
   char buf[10], temp1[3], temp2[3];
   int day, month, hour, min;
   cout << "Ââåäèòå ïóíêò íàçíà÷åíèÿ" << endl;
   cin.getline( data.Punct_nazn, l_Punct_nazn ); if ( action == INFO ) return data;
   do { cout << "Ââåäèòå æåëàåìóþ äàòó âûëåòà â ôîðìàòå ÄÄ.ÌÌ.ÃÃ:" << endl; cin >> buf;
       strncpy( temp1, 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, " " );
   cin.get();
   if ( action == DEL ) return data;
       cout << "Ââåäèòå ôàìèëèþ è èíèöèàëû ïàññàæèðà FIO" << endl; cin.getline( data.FIO, l_FIO );
   do { cout << "Ââåäèòå íîìåð ðåéñà:" << endl; cin >> buf;
   }while ( !( data.nomer = ( float )atof( buf ) ) );
   cin.get();
   return data;
}

int menu() {// -------------------------------------------Âûâîä ìåíþ
   char buf[10];
   int option;
   do { cout << "1 - Äîáàâëåíèå çàÿâêè" << endl; cout << "2 - Âûâîä è óäàëåíèå çàÿâêè" << endl; cout << "3 - Âûâîä âñåõ çàÿâîê" << endl;
      cout << "4 - Âûõîä" << endl;
      cin >> buf; option = atoi( buf );
   } while ( !option );
   cin.get();
   return option;
}

void print_node( const Node& node ) { // --------Âûâîä íà ýêðàí ñâåäåíèé î çàÿâêå cout << "Íîìåð : " << node.Punct_nazn << endl;
   Fine* pf = node.beg;
   while ( pf ) {
      cout << "FIO: " << pf->FIO<< endl; cout << "Äàòà: " <<pf->time;
      cout << " Íîìåð ðåéñà: " << pf->nomer<< endl;
      pf = pf->next;
   }
}

void print_dbase( Node *p ) {// --------------------Âûâîä íà ýêðàí âñåãî äåðåâà
   if ( p ) {
      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);
     if ( !f ) { cout << "Íåò ôàéëà " << filename << endl; return NULL; }
     f.getline( data.Punct_nazn, l_Punct_nazn );// Ïóíêò íàçí
     if( f.eof( ) ) { cout << "Ïóñòîé ôàéë ( 0 áàéò )" << endl; return NULL; }
     read_fine( f, data );  // Ïåðâàÿ çàÿâêà
     Node* root = first( data );  // Ôîðìèðîâàíèå êîðíÿ äåðåâà
     while ( !read_fine( f, data ) )  // Ïîñëåäóþùèå çàÿâêè
         search_insert( root, data, INSERT, dir, parent );  // Ôîðìèðîâàíèå äåðåâà:
     while ( f.getline( data.Punct_nazn, l_Punct_nazn ) ) {// Ïóíêò íàçíà÷åíèÿ
         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.FIO, l_FIO );
   f >> data.nomer;
   f.get();
   return 0;
}

// ---------------------------------------------------Óäàëåíèå çàÿâêè èç ñïèñêà
int remove_fine( Node* p, const Data& data ) {
   Fine* prev, *pf = p->beg;
   bool found = false;
   while ( pf && !found ) {// Öèêë ïî ñïèñêó çàÿâîêê
       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* remove_node( Node* root, Node* p, Node* parent, Dir dir ) {
    Node *y;// Óçåë, çàìåíÿþùèé óäàëÿåìûé
   if ( !p->left)
      y = p->right;// 11
   else if ( !p->right)
      y = p->left;// 12
        else
           y = descent( p );// 13
   if ( p == root ) root = y;// 14
   else { // 15
      if ( dir == LEFT )
          parent->left= y;
      else
          parent->right= y;
   }
   delete p;// 16
   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 ( p && !found ) {// Öèêë ïîèñêà ïî äåðåâó
      cmp= strcmp( data.Punct_nazn, p->Punct_nazn);// Ñðàâíåíèå êëþ÷åé
      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->FIO,data.FIO, l_FIO );
   pf->nomer= data.nomer;
   pf->next= 0;
   if ( !found ) { // Ñîçäàíèå íîâîãî óçëà:
      p = new Node;
      strncpy( p->Punct_nazn,data.Punct_nazn, l_Punct_nazn );
      p->beg= pf; p->left=p->right= 0;
      if (dir == LEFT)
          parent->left= p;// Ïðèñîåä. ê ëåâîìó ïîääåðåâó ïðåäêà
      else parent->right= p;// Ïðèñîåäèíåíèå ê ïðàâîìó ïîääåðåâó ïðåäêà
   }
   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.Punct_nazn << endl;
   Fine* pf= node.beg;
   while( pf ) {
      f <<pf->time<< endl <<pf->FIO<< endl <<pf->nomer<< endl;
      pf = pf->next;
   }
   f << "="<< endl;// Ïðèçíàê îêîí÷àíèÿ ñâåäåíèé î çàÿâêå
}