Связным списком называется последовательность элементов данных, связанных ссылками. Связные списки могут иметь одиночные или двойные связи.
В списке с одиночными связями каждый элемент содержит ссылку на следующий элемент данных. В списке с двойными связями каждый элемент содержит ссылки на предшествующий и последующий элементы. Хотя списки с одиночными связями встречаются достаточно часто, но списки с двойными связями распространены наиболее широко. Основную роль в этом играют следующие три фактора:
· список с двойными связями можно читать в обоих направлениях: и от начала к концу, и от конца к началу. Список с одиночными связями можно читать только в одном направлении;
· поврежденный список с двойными связями проще перестраивать, так как с каждым из членов списка ассоциированы две ссылки;
· некоторые типы операций над списками (например, удаление) проще выполняются над списками с двойными связями.
Рассмотрим метод построения параметризованного списка с двойными связями. Список организовывается с помощью двух классов, первый из которых 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