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 allocationn"; 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<<"nDirect list";

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

cout<<"nreverse 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 2n";

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<<"n";

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

cout<<"list after deleting";

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

cout<<endl;

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

list.store(4);

cout<<"nlist after insert";

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

cout<<endl;

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

if(!p)

{

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

}

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

cout<<"Change"<<i<<"to 5n"; // вывод значения 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