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

Рассмотрим метод построения параметризованного списка с двойными связями. Список организовывается с помощью двух классов, первый из которых 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.

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.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\n"; 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 2\n";

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 element\n"; return 1; // если не найден, выйти

}

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

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