Объектно-ориентированное программирование - Учебное пособие (А.А. Хусаинов)

4.4. параметризованный связный список

 

Связным списком называется последовательность элементов данных, связанных ссылками. Связные списки могут иметь одиночные или двойные связи.

В списке с одиночными связями каждый элемент содержит ссылку на следующий элемент данных. В списке с двойными связями каждый элемент содержит ссылки на предшествующий и последующий элементы. Хотя списки с одиночными связями встречаются достаточно часто, но списки с двойными связями распространены наиболее широко. Основную роль в этом играют следующие три фактора:

 

список с двойными связями можно читать в обоих направлениях: и от начала к концу, и от конца к началу. Список с одиночными связями можно читать только в одном направлении;

поврежденный список с двойными связями проще перестраивать, так как с каждым из членов списка ассоциированы две ссылки;

некоторые типы операций над списками (например, удаление) проще выполняются над списками с двойными связями.

 

Рассмотрим метод построения параметризованного списка с двойными связями. Список организовывается с помощью двух классов, первый из которых listob определяет природу элементов списка, а второй, dlist, реализует механизм списка с двойными связями. Первый из этих классов определяется следующим образом:

 

template <class DataT>

class listob                   // класс элемента списка

{

   public:

               DataT info;            // информационная часть

               listob <DataT> *next;  // указатель на следующий элемент

               listob <DataT> *prior; // указатель на предшествующий элемент

               listob() // конструктор

{

                           info = 0; next = prior = NULL;

};

               listob (DataT c) // конструктор

               {

                           info = c; next = prior = NULL;

};

listob <DataT> *getnext() { return next;}

listob <DataT> *getprior() { return prior;}

void getinfo (DataT& c) { c = info; }

void change (DataT c) { info = c;} // изменение элемента

friend ostream &operator << (ostream &stream, listob <DataT> o);

friend ostream &operator << (ostream &stream, listob <DataT> *o);

friend istream &operator >> (istream &stream, listob <DataT> &o);

};

// перегрузка операции << для объекта listob

template <class DataT>

ostream &operator << (ostream &stream, listob <DataT> o)

{

   stream << o.info << endl; return stream;

}

template <class DataT>

ostream &operator << (ostream &stream, listob <DataT> *o)

{

   stream << o -> info << endl; return stream;

}

// Перегрузка операции >>

template <class DataT>

istream &operator >> (istream &stream, listob <DataT> &o)

{

   cout << “Введите информацию:  ”;

   stream << o.info; return stream;

}

 

Оператор << перегружается как для объектов типа listob, так и для указателей на объекты этого типа. Это связано с тем, что при использовании связных списков широко распространена практика получения доступа к элементам списка через указатель. Поэтому оператор << полезно перегружать, с тем, чтобы он мог оперировать с переданным ему указателем на объект.

Механизм построения связного списка реализуется классом, приведенным ниже. Этот класс является производным от класса listob и оперирует с объектами класса listob.

 

template <class DataT> // параметризованный класс объекта списка

class dlist: public listob<DataT>

// класс списка - производный от класса узла

 

{

   listob<DataT> *start, *end;

// указатели на первый и последний элементы

 

public:

   dlist(){start=end=NULL;}                 // конструктор

   ~dlist();                                // деструктор

   void store(DataT c);                     // запись в список

   void remove(listob<DataT> *ob);          // удаление элемента

   void frwdlist();                     // чтение в прямом направлении

   void bkwdlist();                     // чтение в обратном направлении

   listob<DataT> *find(DataT c);            // поиск

   listob<DataT> *getstart(){return start;} // начало поиска

   listob<DataT> *getend(){return end;}     // указатель на конец списка

}

 

Поскольку каждый узел списка содержит указатели на следующий и предшествующий узлы, то список является двухсвязным. Объектами класса dlist будут двухсвязные списки. Каждый объект этого класса содержит указатель на начало и указатель на конец списка. Оба эти указателя являются указателями на объекты класса listob. При создании списка оба указателя инициализируются значением NULL. Класс dlist поддерживает целый ряд операций над двухсвязными списками, в том числе:

ввод нового элемента в список;

удаление элемента из списка;

просмотр списка в любом направлении (от начала к концу или от конца к началу);

поиск элемента в списке;

получение указателей на начало и на конец списка.

 

Разработаем подпрограммы, выполняющие эти операции и тестовую программу.

 

// dlist.cpp - parametrised class of the double connected list

#include <conio.h>

#include <iostream.h>

#include <stdlib.h>

template <class DataT> class listob;

template <class DataT>

ostream &operator << (operator &stream, listob<DataT> o)

{

   stream<<o.info<<endl; // вывод объекта

   return stream;

}

 

/* template <class DataT>

ostream &operator<<(ostream &stream, listob<DataT> *o)

{

   stream<<o->info<<endl; // вывод объекта по указателю

   return stream;

}*/

/* template <class DataT>

istream &operator>>(istream &stream, listob<DataT> &o)

{

   cout<<"Input data:  ";

   stream>>o.info; // ввод объекта

   return stream;

}

*/

 

template <class DataT> class listob // класс узла

{

public:

   DataT info;                    // информационная часть

   Listob<DataT> *next,           // указатель на следующий элемент

                 *prior;          // указатель на предшествующий элемент

   listob()

{

   info=0; next = NULL; prior=NULL; // конструктор

}

listob(DataT c)

{

   info=c; next=NULL; prior=NULL;   // конструктор

}

listob<DataT> *getnext(){return next;}

// чтение адреса следующего элемента

 

listob<DataT> *getprior(){return prior;}

//чтение адреса предшествующего элемента

 

void getinfo(DataT &c){c=info;} // чтение информации в аргумент

void change(DataT c){info=c;}   // изменение информации

 

friend ostream &operator<<(ostream &stream, listob<DataT> o);

// дружественные функции

//friend ostream &operator<<(ostream &stream, listob<DataT> *o);

// ввода - вывода

//friend istream &operator>>(istream &stream, listob<DataT> &o);

};

 

template <class DataT> // параметризованный класс объекта списка

class dlist: public listob<DataT>

// класс списка - производный от класса узла

 

{

   listob<DataT> *start, *end;

// указатели на первый и последний элементы

 

public:

   dlist(){start=end=NULL;}                 // конструктор

   ~dlist();                                // деструктор

   void store(DataT c);                     // запись в список

   void remove(listob<DataT> *ob);          // удаление элемента

   void frwdlist();                     // чтение в прямом направлении

   void bkwdlist();                     // чтение в обратном направлении

   listob<DataT> *find(DataT c);            // поиск

   listob<DataT> *getstart(){return start;} // начало поиска

   listob<DataT> *getend(){return end;}     // указатель на конец списка

}

template <class DataT> dlist<DataT>::~dlist

{

   listob<DataT> *p, *p1;       // деструктор

p=start;

while(p)

{

   p1=p->next; delete p; p=p1; // освобождение памяти, занятой

}                                                     // элементами списка

}

 

template <class DataT> void dlist<DataT>::store(DataT c)

{

   listob<DataT> *p;

   p= new listob<DataT>;       // запись нового элемента

   if(!p){cout<<"Error of memory allocation "; exit(1);}

   p->info=c;

   if(start==NULL)

// если список пуст, то создается список, состоящий из одного элемента

   {                       

               end=start=p;

}

else // иначе изменяем значения указателей

{

   p->prior=end; end->next=p; end=p;

}

}

 

template <class DataT>

void dlist<DataT>::remove(listob<DataT> *ob)

// удаление элемента списка

 

{

   if(ob->prior)                 // если не первый элемент

   {

               ob->prior->next=ob->next;

               if(ob->next)            // если не последний элемент

                           ob->next->prior=ob->prior;

               else                    // иначе удаляется последний

                           end=ob->prior;    // обновление указателя на конец списка

 

}

else // удаляется первый элемент списка, если список не пуст

{

   if(ob->next)

   {

               ob->next->prior = NULL;

               start=ob->next;

}

else            // иначе, т.е. если список пуст,

start=end=NULL; // установить начало и конец на 0

}

}

 

template <class DataT>

void dlist<DataT>::frwdlist()

// вывод элементов списка в прямом направлении

 

{

   listob<DataT> *temp;

   temp=start;

   while(temp)

   {

               cout<<temp->info<< " ";

               temp = temp -> getnext();

}

cout<<endl;

}

 

template <class DataT>

void dlist<DataT>::bkwdlist()

// вывод элементов списка в обратном направлении

 

{

   listob<DataT> *temp;

   temp=end;

   while(temp)

   {

               cout<<temp->info<< " ";

               temp = temp -> getprior();

}

cout<<endl;

}

 

template <class DataT>

listob<DataT> *dlist<DataT>::find(DataT c)

// поиск объекта, содержащего информацию, совпадающую с указанной

 

{                                                                      

   listob<DataT> *temp;                                  

   temp=start;

   while(temp)

   {

               if(c==temp->info) return temp; // совпадение найдено

               temp = temp->getnext();

}

return NULL;                          // совпадение не найдено

}

 

main()

{

   dlist<double> list;    // демонстрация списка элементов типа double

   double i;

   listob<double> *p;

   clrscr();

   list.store(1);         // запись элементов 1, 2, 3

   list.store(2);

   list.store(3);

   cout<<" Direct list";

   list.frwdlist();       // вывод в прямом направлении

   cout<<" reverse list";

   list.bkwdlist();       // вывод в обратном направлении

   cout<<endl;

   cout<<"Hand viewing of the list"; // ручной просмотр списка

   p=list.getstart();

   while(p)

   {

               p->getinfo(i); cout<<i<<" ";

               p=p->getnext();  // следующий элемент

}

cout<<endl<<endl;

cout<<" find of 2 ";

p=list.find(2);         // поиск элемента 2

if(p)

{

   p->getinfo(i);

   cout<<"we have find" <<i<<endl; // найден элемент i

}

cout<<endl;

 

p->getinfo(i);

cout<<"delete"<<i<<" ";

list.remove(p);           // удаление элемента

cout<<"list after deleting";

list.frwdlist();          // список после удаления

cout<<endl;

 

cout<<"insert the new 4"; // запись элемента 4

list.store(4);

cout<<" list after insert";

list.frwdlist();          // вывод в прямом направлении

cout<<endl;

p=list.find(1);           // поиск элемента 1

if(!p)

{

   cout<<"Error. No such element "; return 1; // если не найден, выйти

}

p->getinfo(i);               // чтение в i

cout<<"Change"<<i<<"to 5 "; // вывод значения i

p->change(5);                // изменение 1 на 5

cout<<"list after the change";

list.frwdlist();             // вывод в прямом направлении

cout<<"Reverse list":

list.bkwdlist();             // вывод в обратном направлении

cout<<endl;

 

getch();

return 0;

}

 

Результаты работы программы

 

Список в прямом направлении: 1 2 3

 

Список в обратном направлении: 3 2 1

 

Ручной просмотр списка: 1 2 3

 

Поиск числа 2 в списке

Число 2 было найдено

 

Удаление числа 2 из списка

Список после удаления: 1 3

 

Запись нового элемента 4 в список

Список после вставки нового элемента: 1 3 4

 

Заменим 1 на 5

Список после замены: 5 3 4

Просмотр полученного списка  в обратном порядке: 4 3 5