Двунаправленный список стр.64

//Двунаправленный список стр.64

#include "exception.cpp"
template <class Item>
class DoubleLinkedList
{
struct Element
{
Item inf;
Element *next;
Element *prev;
Element (Item x):inf(x), next(0), prev(0)
{}
};
Element *head;
Element *tail;
int size;
//возвращает указатель на элемент списка с номером index
Element *Find (int index)
{
if ((index<1)||(index>size))
{
return NULL;
}
else
{
Element *cur=head;
for (int i=1;i<index;i++)
{
cur=cur->next;
}
return cur;
}
}
public:
DoubleLinkedList():head(0), tail(0), size(0) //конструктор
{}
~DoubleLinkedList() //деструктор
{ while (!Empty())
{ Remove(1);}
}
bool Empty() //проверяет список на пустоту
{returnhead==0;}
int GetLength() //возвращает количество элементов в списке
{return size;}
//возвращает значение элемента списка по его номеру
Item Get(int index)
{
if ((index<1)||(index>size))
{
throw DoubleListException("Exception: get - double-linked list error");
}
else
{
Element *r=Find(index);
Item i=r->inf;
return i;
}
}
//осуществляет вставку элемента со значением data слева от элемента с позицией index
void InsertLeft(int index, Item data)
{
if ((index<1)||(index>size+1))
{
throw DoubleListException("Exception: insert - double-linked list error");
}
else
{
Element *newPtr=new Element(data);
size=GetLength()+1; //увеличивает размерность списка
//устанавливаем указатель на элемент списка с заданным номером
Element *cur=Find(index);
//если этот указатель NULL, то список был пуст, поэтому новый элемент будет и первым и последним
if (cur==NULL) //см. рис. 5.11
{
head=newPtr;
tail=newPtr;
}
else
//иначе производим вставку в непустой список, при этом есть два случая: 1 - частный случай (вставка перед первым элементом списка), 2 - общий случай
{
newPtr->next=cur;
newPtr->prev=cur->prev;
cur->prev=newPtr;
if (cur==head)
{head=newPtr;} //случай 1
else
{
newPtr->prev->next=newPtr; //случай 2
}
}
}
}
//осуществляет вставку элемента со значением data слева от элемента с позицией index
void insertRight (int index, Item data)
{
if ((index<1&&head!=NULL)||(index>size+1))
{ cout<<"Exception: insert - double-linked list error"<<endl; }
else
{
Element *newPtr=new Element(data);
size=GetLength()+1; //увеличиваем размерность списка
//устанавливаем указатель на элемент списка с заданным номером
Element *cur=Find(index);
//если этот указатель NULL, то список был пуст, поэтому новый элемент будет и первым и последним
if (cur==NULL)
{
head=newPtr;
tail=newPtr;
}
else
//иначе производим вставку в непустой список, при этом есть два случая: 1 - вставка после последнего элемента списка, 2 - вставка в середину списка
{
newPtr->new=cur->next;
newPtr->prev=cur;
cur->next=newPtr;
if (cur==tail)
{
tail=newPtr; //случай 1
}
else
{ newPtr->new->prev=newPtr; } //случай 2
}
}
}
//осуществляет удаление элемента с номером index из списка
//выделяем четыре случая: 1 - после удаления список становится пустым, 2 - удаляем первый элемент, 3 - удаляем последний элемент, 4 - общий случай
void Remove(int index)
{
if ((index<1)||(index>size))
{
cout<<"Exception: remove - double-linked lisst error");
}
else
{
//устанавливаем указатель на заданный элемент
Element *cur=Find(index);
--size; // уменьшаем размерность списка
if (size==0) //случай 1
{
head = NULL;
tail = NULL;
}
else if (cur==head) //случай 2
{
head=head->next;
head->prev=NULL;
}
else if (cur==tail) //случай 3
{
tail=tail->prev;
tail->next=NULL;
}
else //общий случай, см.рис.5.14
{
cur->prev->next=cur->next;
cur->next->prev=cur->prev;
}
cut->next=NULL;
cur->prev=NULL;
delete cur;
}
}
//вывод элементов списка в глобальный поток out в прямом порядке
void PrintLeftToRight()
{
for (Element *cur = head; cur!=NULL; cur=cur->next)
{ out<<cur->inf<<' '; }
out << endl;
}
//вывод элементов списка в глобальный поток out в обратном порядке
void PrintRightToLeft()
{
for (Element *cur=tail; cur!=NULL; cur=cur->prev)
{
out<<cur->inf<<' ';
}
out<<endl;
}
};

/* Замечание: Класс DoubleListException помещён в отдельный файл exception.cpp и выглядит следующим образом:
#include "exception"
#include "string"
using namespace std;
class DoubleListException: public exception
{
public:
DoubleListException (const string & message = ""): exception (message.c_str())
{}
}; */