и нумбер два. сам класс для списка и класс-контейнер, из кот. состоит список
// Файл cBaseList.h
// Шаблонный класс cBaseList для управления двухсвязным списком
// Из учебного курса А. Деона
#ifndef cBaseList_h // защита от повторной компиляции
#include "cNode.h" // cNode
template < typename INFO >
class cBaseList
{public:
typedef unsigned long ULONG;
typedef cNode < INFO, cBaseList < INFO > > NODE;
cBaseList( void ) : First(NULL), Last(NULL), LastNumber(0),
Before(NULL), After(NULL) {}
~cBaseList( void ) { Delete(); } // удалить список
void Print( void ); // распечатка списка
void PrintN( void );
public:
void Delete( void );//удалить список из динамической памяти
// распечатка списка
cBaseList < INFO > & operator + ( INFO& ); // добавить узел
inline void* FirstIter( void ) { return (void*) First; }
inline void* LastIter( void ) { return (void*) Last; }
inline INFO* InfoIter( void* p ){ return & ((NODE*)p)->Info;}
inline void* NextIter( void* p ) // адрес следующего узла
{ return (void*)((NODE*)p)->Next; }
inline void* PrevIter( void* p ) // адрес предыдущего узла
{ return (void*)((NODE*)p)->Prev; }
inline ULONG NumberIter( void* p ) // номер текущего узла
{ return ((NODE*)p)->Number;}
inline void ChangeWithIter( void* pi, void* pk )//с номерами
{ ChangeWith( (NODE*) pi, (NODE*) pk ); }
inline void ChangeNoIter( void* pi, void* pk )// без номеров
{ ChangeNo( (NODE*) pi, (NODE*) pk ); }
protected:
inline NODE* GetFirst( void ) { return First; }
inline INFO* GetFirstInfo( void ) { return & First->Info; }
inline NODE* GetLast ( void ) { return Last; }
inline INFO* GetLastInfo( void ) { return & Last->Info; }
inline ULONG GetLastNumber( void ) { return LastNumber; }
inline INFO* GetInfo( NODE* p ) { return & p->Info; }
inline NODE* GetNext( NODE* p ) { return p->Next; }
inline void SetNext( NODE* p, NODE* r ) { p->Next = r; }
inline NODE* GetPrev( NODE* p ) { return p->Prev; }
inline void SetPrev( NODE* p, NODE* r ) { p->Prev = r; }
inline ULONG GetNumber(void* p){ return ((NODE*) p)->Number;}
inline void SetNumber( NODE* p, ULONG n ) { p->Number = n; }
inline NODE* Get_hN( NODE* p ) { return p->hN; }
inline void Set_hN( NODE* p, NODE* r ) { p->hN = r; }
inline NODE* Get_hP( NODE* p ) { return p->hP; }
inline void Set_hP( NODE* p, NODE* r ) { p->hP = r; }
inline void SetLRU( NODE* p );
inline NODE* GetLeft( NODE* p ) { return p->Left; }
inline void SetLeft( NODE* p, NODE* r ) { p->Left = r; }
inline NODE* GetRight( NODE* p ) { return p->Right; }
inline void SetRight( NODE* p, NODE* r ) { p->Right = r; }
inline NODE* GetUp( NODE* p ) { return p->Up; }
inline void SetUp( NODE* p, NODE* r ) { p->Up = r; }
inline char GetState( NODE* p ) { return p->State; }
inline void SetState( NODE* p, char ch ) { p->State = ch; }
void SetBA( void ); // установить узлы Before и After
void FreeBA( void ); // снять узлы Before и After
void Replace( NODE* pb, NODE* pn ); // преместить узел
void ChangeSimple( NODE* pi, NODE* pk ); // простой обмен
void ChangeWith( NODE* pi, NODE* pk ); // обмен c номерами
void ChangeNo( NODE* pi, NODE* pk ); // обмен без номеров
void ChangeN( NODE* pi, NODE* pk ); // обмен без номеров
protected:
NODE* First; // адрес начального узла
NODE* Last; // адрес последнего узла
ULONG LastNumber; // номер последнего узла
NODE* Before; // адрес вспомогательного узла перед First
NODE* After; // адрес вспомогательного узла после Last
};
// --------------------------------------------------------------
template < typename INFO >
void
cBaseList < INFO > :: Delete( void )
{ if( Before ) // есть дополнительное начало списка
{ First->Prev = NULL;
delete Before;
Before = NULL;
}
if( After ) // есть дополнительное окончание списка
{ Last->Next = NULL;
delete After;
After = NULL;
}
while( Last ) // реверсивный цикл узлов списка
{ NODE* d = Last; // указатель удаляемого узла
Last = Last->Prev; // предпоследний узел
delete d; // удалить узел из динамической памяти
}
First = NULL;
Last = NULL;
LastNumber = 0;
}
// --------------------------------------------------------------
template< typename INFO >
cBaseList < INFO > &
cBaseList < INFO > :: operator + ( INFO& inf )
{ NODE* p = new NODE; // создать узел
p->Info = inf; // загрузить информацию в узел
if( !First ) First = p; // список пуст
else
{ Last->Next = p;
p->Prev = Last;
}
Last = p;
p->Number = ++LastNumber;
return *this; // адресный идентификатор объекта
}
// --------------------------------------------------------------
template < typename INFO >
void
cBaseList < INFO > :: Print( void )
{ printf( "\n" ); // новая строка
NODE* p = First; // начало списка
while( p != After ) // цикл узлов
{ printf( "%4d", p->Info ); // информация узла
p = p->Next; // следующий узел
}
printf( "\n" ); // новая строка
}
// --------------------------------------------------------------
template < typename INFO >
void
cBaseList < INFO > :: PrintN( void )
{ printf( "\n" ); // новая строка
NODE* p = First; // начало списка
while( p != After ) // цикл узлов
{ printf( "%4d", p->Info ); // информация узла
p = p->Next; // следующий узел
}
printf( "\n" ); // новая строка
p = First; // начало списка
while( p != After ) // цикл узлов
{ printf( "%4d", p->Number ); // номер узла
p = p->Next; // следующий узел
}
printf( "\n" ); // новая строка
}
// --------------------------------------------------------------
template < typename INFO >
void
cBaseList < INFO > :: SetBA( void )
{ if( !Before )
{ Before = new NODE; // для эффективности перестановок
First->Prev = Before; // поставить перед началом списка
Before->Next = First;
}
if( !After )
{ After = new NODE; // для эффективности перестановок
Last->Next = After; // поставить после окончания списка
After->Prev = Last;
}
}
// --------------------------------------------------------------
template < typename INFO >
void
cBaseList < INFO > :: FreeBA( void )
{ if( Before )
{ First = Before->Next;// восстановить начало общего списка
First->Prev = NULL;
delete Before;
Before = NULL;
}
if( After )
{ Last = After->Prev; // восстановить конец общего списка
Last->Next = NULL;
delete After;
After = NULL;
}
}
// --------------------------------------------------------------
template < typename INFO >
void
cBaseList < INFO > :: Replace( NODE* pb, NODE* pn )
{
pn->Prev->Next = pn->Next; // исключить узел pn из списка
pn->Next->Prev = pn->Prev;
pb->Prev->Next = pn; // вставить узел pn перед узлом pb
pn->Prev = pb->Prev;
pn->Next = pb;
pb->Prev = pn;
First = Before->Next;
Last = After->Prev;
}
// --------------------------------------------------------------
