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

Тема в разделе "C и С++ FAQ", создана пользователем konstahntin, 18 дек 2010.

Статус темы:
Закрыта.
  1. konstahntin

    konstahntin Гость

    Помогите, пожалуйста, не могу исправить ошибки в проге. Заранее спасибо!

    Задание:

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


    Код (C++):
    //----------------------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;
    }
     
  2. ierofant

    ierofant Гость

    А с кодировкой комментариев, что за беспредел?
     
  3. konstahntin

    konstahntin Гость

    :sorry:

    Добавлено:
    Извиняюсь, что то с кодировкой напутал, вот! Помогите, очень нужно!


    Код (C++):
    //----------------------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;
    }
     
Загрузка...
Похожие Темы - Шаблон иерархической структуры
  1. proteam
    Ответов:
    7
    Просмотров:
    106
  2. joomlavi
    Ответов:
    0
    Просмотров:
    429
  3. Ruslan280
    Ответов:
    17
    Просмотров:
    1.270
  4. Shandrik
    Ответов:
    7
    Просмотров:
    549
  5. R4z0R
    Ответов:
    2
    Просмотров:
    534
Статус темы:
Закрыта.

Поделиться этой страницей