Связные списки допускают гибкие методы доступа к элементам данных, поскольку каждый элемент данных содержит ссылку на следующий элемент данных в цепочке. Кроме того, операция извлечение элемента из связных списков не приводит к его удалению из списка и потере данных.
Связные списки могут иметь одиночные и двойные связи. В списке с одиночными связями каждый элемент содержит ссылку на следующий элемент данных. В списке с двойными связями каждый элемент содержит ссылки на предыдущий и последующий элементы.
Списки с двойными ссылками представляют собой динамические структуры данных, которые могут растягиваться или сжиматься в процессе выполнения программы. При удалении или добавлении элементов ссылки соответствующим образом перестраиваются.
// Программа 3
// Параметризованный класс связного списка с двойными
// ссылками
// Описание шаблона класса списка с двойными связями
template <class DataT> class listob {
public:
DataT info; //информация
listob<DataT> *next; //указатель на след. объект
listob<DataT> *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);
};
// Перегрузка << для объекта listob
template <class DataT>
ostream &operator<<(ostream &stream,listob<DataT> o)
{
stream << o.info << endl;
return stream;
}
// Перегрузка << для указателя на объект типа listob
template <class DataT>
ostream &operator<<(ostream &stream,listob<DataT> *o)
{
stream << o->info << endl;
return stream;
}
// Перегрузка >> для ccылки на объект типа listob
template <class DataT>
istream &operator>>(istream &stream,listob<DataT> &o)
{
cout << "Введите информацию: " ;
stream >> o.info;
return stream;
}
//Класс, реализующий связнный список
template <class DataT> class dllist : public listob<DataT> {
listob<DataT> *start, *end; //*next, *prior
public:
dllist() { start = end = NULL; }
~dllist() ;
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; }
};
// Деструктор dllist
template <class DataT> dllist<DataT> :: ~dllist()
{
listob<DataT> *p, *p1;
p = start;
while (p) {
p1 = p->next;
delete p;
p = p1;
}
}
Класс dllist поддерживает целый ряд операций над списком с двойными ссылками:
— ввод нового элемента списка — функция store();
— удаление элемента из списка — функция remove();
— просмотр списка в любом направлении — функции frwdlist() от начала к концу и bkwdlist() от конца к началу
— поиск в списке конкретного элемента — функция find();
— получение указателей на начало и коней списка
//Добавление нового элемента
template <class DataT> void dllist<DataT> :: store(DataT c)
{
listob<DataT> *p;
p = new listob<DataT>;
if (!p) {
cout << "Ошибка выделения памяти\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
dllist<DataT> :: remove(dllist<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;
}
}
// Просмотр списка от начала к концу
template <class DataT> void dllist<DataT> :: frwdlist()
{
listob<DataT> *temp;
temp = start;
while (temp) {
cout << temp->info << " ";
temp = temp->getnext();
}
cout << endl;
}
// Просмотр списка от конца к началу
template <class DataT> void dllist<DataT> :: bkwdlist()
{
listob<DataT> *temp;
temp = end;
while (temp) {
cout << temp->info << " ";
temp = temp->getprior();
}
cout << endl;
}
// Поиск объекта, содержащего информацию, совпадающую с
// указанной
template <class DataT> listob<DataT>
*dllist<DataT> :: find(DataT c)
{
listob<DataT> *temp;
temp = start;
while (temp) {
if (c == temp->info) return temp;
temp = temp->getnext();
}
return NULL;
}
