Помогите, пожалуйста, не могу исправить ошибки в проге. Заранее спасибо!
Задание:
Шаблон структуры данных – односвязный список, содержащий статический массив указателей на объекты. Последовательность указателей в каждом массиве ограничена NULL. При переполнении текущего массива указателей создается новый элемент списка, в который переписывается половина указателей из текущего. Для заданной двухуровневой структуры данных, содержащей указатели на объекты (или сами объекты) - параметры шаблона, разработать полный набор операций (добавление, включение и извлечение по логическому номеру, сортировка, включение с сохранением порядка, загрузка и сохранение объектов в бинарном файле, балансировка.
Задание:
Шаблон структуры данных – односвязный список, содержащий статический массив указателей на объекты. Последовательность указателей в каждом массиве ограничена 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;
}