Шаблон иерархической структуры данных в памяти

//----------------------classes.h------------------
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <stdio.h>
#include <windows.h>
#include <fstream.h>
 
char* rus (char*);  // âûâîä êèðèëëè÷åñêîãî øðèôòà
void Report (int);  // îò÷åò îá îáíàðóæåííûõ îøèáêàõ
//-----------------------------------------
template <class T, int N>
class List
{
    int kol;            //  êîëè÷åñòâî ýëåìåíòîâ â ñïèñêå  
public:
    
    class Elem      // âëîæåííûé êëàññ
    {
    public:
        friend class List;
        T *data;    
        int size;
        Elem *next;  // óêàçàòåëü íà ñëåäóþùèé ýëåìåíò ñïèñêà
 
        Elem () { data= new T[N+1]; data[0]=NULL; size=0; next=NULL;}   // êîíñòðóêòîð
        ~Elem() { delete []data; size=0; next=NULL;}                // äåñòðóêòîð
    };
    
    Elem *first, *last; // ãðàíèöû ñïèñêà
 
    List () { first=last=NULL; kol=0;}  // êîíñòðóêòîð ñïèñêà 
    List (List *t) { first= t.first; last= t.last; kol= t.kol;} 
    ~List () { this->delList(); }       // äåñòðóêòîð ñïèñêà
    //------------------------
    void split (Elem *p)        // ðàçáèåíèå ýëåìåíòà ñïèñêà ïðè ïåðåïîëíåíèè
    {
        if (p->size < N) return;        // åñëè ðàçáèåíèå íå òðåáóåòñÿ
                          
        Elem *a= new Elem;      // ñîçäàåì íîâûé ýëåìåíò ñïèñêà
        a->next= p->next;
        p->next= a;         
        for(int i=0;i<N/2;i++)
        {
            a->data[i] = p->data[i+N/2];    // ïåðåïèñûâàåì ïîëîâèíó óêàçàòåëåé
            p->data[i+N/2] = NULL;  // óäàëÿåì èç ñòàðîãî
        }
        a->size= p->size= N/2;
        p->data[N/2] = NULL;
        a->data[N/2] = NULL;
        kol++;                  // óâåëè÷èâàåì âíóòðåí. ñ÷åò÷èê ñïèñêà   
        if(last==p) last=a; // åñëè ïîñëåäíèé
    }
    //------------------------
    long count (Elem *end)  // ïîäñ÷åò êîë-âà îáúåêòîâ äî óêàçàííîãî ýëåìåíòà ñïèñêà
    {
        Elem *p=first;
        for(long n=0; p!=NULL && p!=end; n+=p->size, p=p->next);
        return n;
    }
    //------------------------
    void info ()        // èíôîðìàöèÿ î ñòðóêòóðå 
    {
        long n1= count(last) + (first?(last->size):0);
        double fill = ((kol==0 || n1==0)? 0.0 : (100.0*n1)/(kol*N));    
                        // ïîäñ÷åò ïðîöåíòà çàïîëíåíèÿ     
        system("cls");
        cout << rus("-----------Èíôîðìàöèÿ î ñòðóêòóðå---------\n");
        cout << rus("Êîëè÷åñòâî ýëåìåíòîâ â ñïèñêå:  ") << kol << endl;
        cout << rus("Êîëè÷åñòâî ñòðîê â ñïèñêå:    ") << n1 << endl;
        cout << rus("Ïðîöåíò çàïîëíåíèÿ ñòðóêòóðû: ") << fill << "%\n";
        cout <<"-------------------------------------------------------------" << endl;
    }
    //------------------------
    void add (T val)    // äîáàâëåíèå ñòðîê
    {
        if (first == NULL)  // åñëè ñïèñîê ïóñò – äîáàâëÿåì çíà÷åíèå ïåðâûì
        {
            Elem *ph= new Elem;
            ph->next= NULL;
            kol=1;
            ph->data[0]= val;
            ph->size++;
            first= last= ph;
            return;
        }
        Elem *p= last;          // èíà÷å â êîíåö
        p->data[p->size] = val;
        p->size++;
        split (p);
    }
    //------------------------
    void insOrd (T val)     // âñòàâêà ñ ñîõðàíåíèåì ïîðÿäêà
    {
        if (first == NULL)
        {
            Elem *ph=new Elem;
            first= last= ph;
            ph->next=NULL;
            kol=1;
            ph->data[0]= val;
            ph->size++;
            return;
        }
        int i,k;
        Elem *q= first;         // ïîèñê ìåñòà âñòàâêè
        for(;q->next!=NULL && (q->data[q->size-1] <= val); q=q->next);
        for(i=0; i< q->size && q->data[i] != NULL && (q->data[i] <= val); i++);
        for(k=q->size; k>i; k--)
            q->data[k] = q->data[k-1];      // ðàçäâèæêà ãðàíèö
 
        q->data[i]= val;
        q->size++;      // óâåëè÷èòü ñ÷åò÷èê êîë-âà óêàçàòåëåé
        split(q);       // ïðîâåðèòü íà ïåðåïîëíåíèå
    }
 
 
//------------------------
void insLog (T val, int n)  // âñòàâêà ïî ëîãè÷åñêîìó íîìåðó
    {   
        if (first->data[0] == NULL) throw 0;        // ñïèñîê ïóñò
        long cnt = count(last) + last->size;
 
        if (n<0 || n>cnt-1 || cnt<=0) throw 6;      // íåêîððåêòíûé ËÍ
        int j;
        Elem *q= first;
        while(q!=NULL)
        {
            if(n<q->size) break;    
            n-=q->size;            
            q= q->next;            
        }
        if(q==NULL) throw 6;
 
        for(j= q->size; j>n; j--)
            q->data[j] = q->data[j-1];          // ðàçäâèæêà ãðàíèö
 
        q->data[n]= val;              
        q->size++;
        split(q);
    }
    //------------------------
    void delDataLog (int n)     // óäàëåíèå ïî ËÍ
    {
        if (first->data[0] == NULL) throw 1;        // ñïèñîê ïóñò
        long cnt = count(last) + last->size;
        if (n<0 || n>cnt-1)  throw 6;           // íåêîððåêòíûé ËÍ
        
        int i;
        Elem *q= first;
        while(q!=NULL)
        {
            if(n < q->size) break;        
            n-=q->size;                  
            q=q->next;                  
            }
        if(q==NULL) return;
        for(i=n; i < q->size - 1; i++) q->data[i]= q->data[i+1];    // «ñäâèæêà» ãðàíèö
        q->size--;      // óìåíüøèòü êîë-âî óêàçàòåëåé â òåê. ýëåìåíòå  ñïèñêà
    }
    //------------------------
    void ShowDataLog (int num)      // âûâîä ïî ËÍ
    {
        if (first->data[0] == NULL) throw 2;        // ñïèñîê ïóñò
        long cnt = count(last) + last->size;
        int n=num;
 
        if (n<0 || n>cnt-1) throw 6;            // íåêîððåêòíûé ËÍ
        Elem *q= first;
        while(q!=NULL)
        {
            if(n < q->size) break;
            n -= q->size;                  
            q = q->next;
            }
        if(q == NULL)  return;
        cout << rus("Çàïðîøåííûé ýëåìåíò íàéäåí: ") << q->data[n] << endl;
        cout << rus("Íàæìèòå '1', åñëè õîòèòå óäàëèòü åãî...") << endl;
        if ('1' == getch()) delDataLog (num);       // óäàëèòü íàéäåííûé ýëåìåíò
    }
    //------------------------
    void delList ()     // î÷èùåíèå âñåãî ñïèñêà
    {
        if(first==NULL) return;     // ñïèñîê ïóñò
        Elem *pt=first;         // íà÷èíàÿ ñ ïåðâîãî ýëåìåíòà
        while(pt)
        {
            first= first->next;
            delete pt;      // óäàëèòü òåóùèé
            pt= first;      // çàïîìíèòü ñëåäóþùèé
        }
        first= last= NULL;      // îáíóëèòü âñ¸
        kol= 0;
    }
    //-------------------------
    void sort ()    // ñîðòèðîâêà ñïèñêà
    {
        if (first == NULL) throw 3; // ñïèñîê ïóñò
        int i,j=0;
        long s = count(last) + (last->size);
        T *mas = new T[s + 1];  // ñîçäàòü ìàññèâ äëÿ õðàíåíèÿ óêàçàòåëé
        if (!mas) throw 7;      // íå õâàòèëî ïàìÿòè!
        Elem *pt= first;
        while(pt!=NULL)
        {
            for( i=0; pt->data[i]!=NULL && j<s; i++ )  
                mas[j++] = pt->data[i];
            pt= pt->next;
        }
        mas[j] = NULL;
        delList();      // î÷èùåíèå ñïèñêà
        for(i=0; mas[i] != NULL; i++)  insOrd (mas[i]); // óïîðÿä. âñòàâêà
        delete []mas;
    }
    //------------------------
    void save_bin (char *path)      // ñîõðàíåíèå â áèíàðíûé ôàéë
    {
        ofstream out(path, ios::binary);    // ñâÿçûâàíèå ñ óêàçàííûì ôàéëîì
        if(!out)                    // ôàéë íåäîñòóïåí
        {
            out.close();    
            throw 5;                
        }
        Elem *ph= first;
        long number = count(last) + last->size;
        out.write((char*)&number, sizeof(long));    // çàïèñàòü îáùåå êîë-âî ñòðîê
 
        while(ph)
        {
            for (int i=0; ph->data[i]!=NULL; i++)
                out.write ((char*)&ph->data[i], sizeof(T)); // …ñàìè ñòðîêè
            ph= ph->next;
        }
        out.close ();       // îáîðâàòü ñâÿçü ñ ôàéëîì
    }
    //---------------------------------
    void load_bin (char* path)      // çàãðóçêà èç áèíàðíîãî ôàéëà
    {
        ifstream in(path, ios::binary|ios::nocreate);   // ñâÿçü ñ ôàéëîì
        if (!in)
        {
            in.close();
            remove (path);              // ôàéë íå ñóùåñòâóåò
            throw 5;
        }
        T obj;
        long number;
        in.read((char*)&number, sizeof(long));  // ïðî÷èòàòü êîë-âî ñòðîê
        for(long i=0; i<number; i++)
        {
            in.read ((char*)&obj, sizeof(T));   // ïðî÷èòàòü ñàìè ñòðîêè
            add (obj);              // äîáàâèòü â ñïèñîê
        }
        in.close();                 // îáîðâàòü ñâÿçü ñ ïîòîêîì
    }
    //---------------------------------
    void balance ()
    {
        if (!first) throw 4;
        save_bin ("tmp");       // çàïèñàòü ñïèñîê â ïðîìåæóòî÷íûé ôàéë(ÏÔ)
        delList ();         // î÷èñòêà ñïèñêà
        load_bin ("tmp");       // çàãðóçèòü èç ÏÔ
        remove ("tmp");     // óäàëèòü ÏÔ
    }
};
//-----------------END OF LIST---------
 
//-------------Digit.h--------------------------
#include <iostream.h>
#include <string.h>
 
class Digit     // êëàññ ñîáñòâåííîé ðàçðàáîòêè
{
    friend ostream& operator<<(ostream& , Digit& );  // âûâîä â ïîòîê
friend istream& operator>>(istream& , Digit& );  // ââîä(÷òåíèå) èç ïîòîêà
    friend void List<Digit,8>::save_bin(char*);
    friend void List<Digit,8>::load_bin(char*);
    char *str;
public:
    // ëîãè÷åñêèå áèíàðíûå îïåðàöèè
    int operator< (const Digit& a) { return (strcmp(str, a.str)<0?1:0);}
    int operator<=(const Digit& a) { return (strcmp(str, a.str)<=0?1:0);}
    int operator==(const int) {return (str==NULL);}
    int operator!=(const int) {return (str!=NULL);}
    Digit operator=(const int) { return Digit();}
    
    Digit () { str = NULL;}     // êîíñòðóêòîð
    ~Digit () { if(str) delete []str;}  // äåñòðóêòîð
    //------------------
    Digit (char *a)         // êîíñòðóêòîð ñ ïàðàìåòðàìè
    {
         str = new char[strlen(a)+1];
             strcpy (str,a);
    }
    //------------------
    Digit (Digit& OLD)   // êîíñòðóêòîð êîïèðîâàíèÿ
    { 
        str= new char[strlen(OLD.str)+1];
        strcpy (str,OLD.str);
    }
    //------------------
    Digit& operator=(const Digit& a)    // ïåðåîïðåä. îïåðàöèÿ ïðèñâàèâàíèÿ
    {
        str=new char[strlen(a.str)+1];
        strcpy(str, a.str);
        return *this;
    }
}; 
//------------End of DigiT-----------------
//--------------------------
//---friend Digit functions
ostream& operator<<(ostream& os, Digit& a)
{
    os << a.str;
    return os;
}
//--------------------------------------
istream& operator>>(istream& is, Digit& a)
{
    char *s= new char[80];
    is >> s;
 
    a.str = new char[strlen(s)+1];
    strcpy (a.str, s);
 
    delete []s;
    return is;
}
//--------------------------------------
void List <Digit,8>::save_bin(char* path)
{
    ofstream ofile(path,ios::binary|ios::out); 
    if (!ofile)
    {
        ofile.close();
        throw 5;
    }
    Elem *pt=first; 
    long kol = count(last)+last->size;
    ofile.write((char*)&kol,sizeof(kol));
    while(pt)
    {
        for(int i=0; pt->data[i]!=NULL && i<pt->size; i++)
        {
            ofile.write((pt->data[i]).str, strlen((pt->data[i]).str));
            ofile.write(" ",1);
        }   
        pt=pt->next;
    }
    ofile.close();          
}
 
 
//--------------------------------------
void List <Digit,8>::load_bin(char* path)
{
    ifstream in(path,ios::in|ios::binary);
    if (!in)
    {
        in.close();
        remove (path);
        throw 5;
    }
    Digit *t;
    char *m=new char[80];
    long kol;
    in.read((char*)&kol,sizeof(long));
    for (int i=0; i < kol; i++)
    {
        in >> m;
            t = new Digit(m); 
            add(*t);
    }
    delete []m;
    in.close();
}
 
//----------------func.cpp---------------
#include "classes.h"
 
char* rus(char* msg)        
{
    char* s= new char[strlen(msg)+1];
    CharToOem (msg,s);      // ýòà ô-ÿ îáåñïå÷èâàåò âûâîä êèðèëëèöû
    return s;
}
//--------------------------------
void Report (int code)          // âûâîä îò÷åòà îá îøèáêàõ
{
    char *error[] = { "Ñïèñîê ïóñò. Íåò ýëåìåíòîâ äëÿ âñòàâêè",
              "Ñïèñîê ïóñò. Íåò ýëåìåíòîâ äëÿ ïðîñìîòðà.", 
              "Ñïèñîê ïóñò. Íåò ýëåìåíòîâ äëÿ óäàëåíèÿ.",
              "Ñïèñîê ïóñò. Ñîðòèðîâêà íåâîçìîæíà",
              "Ñïèñîê ïóñò. Áàëàíñèðîâêà íåâîçìîæíà ",
              "Íå ìîãó îòêðûòü ôàéë",
              "Íåâåðíûé ËÍ",
              "Íåõâàòêà ïàìÿòè",
              NULL
            };
    cout << rus( error[code] ) << endl;
    getch ();
}
 
 
 
 
 
 
 
 
 
 
//---------------demo.cpp ( ñîäåðæèò main )--------------
#include "classes.h"
#include "digit.h"
 
#define MODE
//---------------
int main ()
{
#ifdef MODE             // òèï äàííûõ - int
    List <int,10> L;
    List <int,10>::Elem *p;
    int val;
#else                   // òèï äàííûõ - Digit
    List <Digit,8> L;
    List <Digit,8>::Elem *p;
    //char *val=  new char[30];
    Digit val;
#endif
 
    char *name= new char[50];
    int num=0, cnt=0, exit=0, k=0;
    while(1)
    {
        try
        {
        //---------TRY BLOCK--------------
        cnt = L.count(L.last) + ((L.first!=NULL)?((L.last)->size) : 0); // îáùåå êîë-âî ñòðîê
 
        system("cls");
        cout << rus("1.  Ïîêàçàòü ñïèñîê\n2.  Äîáàâèòü ïî ËÍ\n3.  Óäàëèòü ïî ËÍ\n");
        cout << rus("4.  Óäàëèòü ïî ËÍ\n5.  Óäàëèòü âåñü ñïèñîê\n");
        cout << rus("6.  Ñîõðàíåíèå â áèíàðíûé ôàéë\n");
cout << rus("7.  Çàãðóçêà èç áèíàðíîãî ôàéëà.\n");
        cout << rus("8.  Áàëàíñèðîâêà\n9.  Ñîðòèðîâêà\nF1. Èíôîðìàöèÿ î ñòðóêòóðå\n");
        cout << "------ " << rus("[Esc] - ÂÛÕÎÄ") << " ------" << endl;
 
        switch( getch() )
        {
        case '1':   if(!L.first)
                {
                    cout << rus("Ñïèñîê ïóñò. Ââåäèòå data: ");
                    cin >> val;
                    L.add (val);
                }   
                p = L.first;
 
                exit=0;
                while (!exit)
                {
                    system("cls");
                    k = L.count(p);
            
                    cout << rus("êîë-âî: ") << p->size << "\n" << endl ;
                    for(int j=0; j < p->size; j++) 
                        cout << "[" << j+k << "]= " << p->data[j] << endl;
                    cout << endl;
                    cout << rus("<Insert> - äîáàâëåíèå    ");
cout << rus("<Home> - â íà÷àëî");
                    cout << rus("<F1> - èíôîðìàöèÿ\n");
cout << rus("<Space> - ê ñëåäóþùåìó  ");
                    cout << rus("<End>-â êîíåö   <Esc> - ãëàâíîå ìåíþ\n");
                    cout << endl;
                    
                    switch( getch() )
                    {
                    case 71:    p = L.first; break; // Home
                    case 79:    p = L.last; break;  // End
                    case 27:    exit = 1; break;    // Esc
                    case 32:    if(p->next) p = p->next; break; // Space
                    case 59:    L.info(); getch(); break;   // F1
 
                    case 82:    cout << rus("Ââåäèòå data: ");  // Insert
                            cin >> val;
                            L.add (val);    
                            break;  
                    }
                }   
                break;
        
        case '2':   if (cnt == 0) throw 0;
                cout << rus("Ââåäèòå data: ");
                cin >> val;
                cout << rus("\Äîñòóïíûå ËÍ 0...") << cnt-1 << endl;
                cout << rus("\nÂâåäèòå ËÍ (-1 äëÿ âûõîäà): ");
                cin >> num;
                if (num <0 || num > cnt-1) break;
                L.insLog (val,num);
                break;  
        
        case '3':   if (cnt == 0) throw 1;
                cout << rus("\n Äîñòóïíûå ËÍ 0...") << cnt-1 << endl;
                cout << rus("\nÂâåäèòå ËÍ (-1 äëÿ âûõîäà): ");
                cin >> num; 
                L.delDataLog (num); 
                break;
        
        case '4':   if (cnt==0) throw 2;
                cout << rus("Ââåäèòå ËÍ: ");
                cin >> num;
                L.ShowDataLog (num);
                break;
 
        case '5':   L.delList(); cout << rus("Ñïèñîê óäàëåí!") << endl; getch(); break;
        
        case '6':   cout << rus("Óêàæèòå ôàéë äëÿ çàïèñè: ");
                cin >> name;
                L.save_bin (name);
                break;
 
        case '7':   cout << rus("Óêàæèòå ôàéë äëÿ ÷òåíèÿ: ");
                cin >> name;
                if (L.first)
                {
                    cout << rus("Ñïèñîê íå ïóñò.");
cout << rus(" Óäàëèòü ñòàðûé ñïèñîê? (äà-'1')") << endl;
                    if ('1' == getch()) 
                    {
                        cout << rus("Ñïèñîê óäàëåí!") << endl;  
                        L.delList ();
                        getch();
                    }
                }
                L.load_bin (name);
                break;
 
        case '8':   L.balance (); break;
        case '9':   L.sort (); break;
        case 59:    L.info (); getch(); break;
 
        case 27:     delete []name; return 1;
        }
        //-------END of Try Block----------
        }
        catch (const int code) { Report (code); }
    }
    return 0;
}