10.1.4. Реализация линейного списка с помощью связанного двунаправленного списка

Связанный двунаправленный список состоит из элементов, каждый из которых, кроме первого и последнего, связан с помощью указателей со следующим и предыдущим элементами. В последнем элементе указатель на следующий элемент имеет значения 0, а в первом элементе имеет значения 0 указатель на предыдущий элемент. Для работы с двунаправленным списком удобно использовать два внешних указателя – на первый и последний элементы. По сравнению с однонаправленным связанным списком, в двунаправленном списке эффективнее выполняются операции: прохождение списка в двух направлениях, удаление элемента в заданной позиции, добавление и удаление элемента перед заданным элементом. Двунаправленные списки часто используются для сортировки (методом вставки) и удаления дубликатов.

В языке С++ элемент связанного двунаправленного списка – это структура из трех полей: поля, содержащего значение элемента и двух служебных полей-указателей. Пример объявления типа элемента связанного двунаправленного списка целых чисел:

struct element

{

int info ;

element *prev;

element *next;

};

Пример программы, выполняющей операции над линейным связанным двунапрвленным списком:

#include <iostream.h>

#include <conio.h>

//Добавление элемента x в конец списка

void insertend(element * &begin, element * &end, int x);

//Вывод списка от конца к началу

void print(element* end);

//Удаление элемента в позиции p (при условии, что список не //пуст)

void delp(element * & begin, element * &end, element * p);

void main()

{

element* begin,* end;

int x;

begin= end=0;

cout<<"x ";

cin>>x;

inserend (begin, end, x);

print(end);

cout<<" x ";

cin>>x;

inserend (begin, end, x);

print(end);

delp(begin, end, end); //удаление последнего элемента

print(end);

getch();

}

void insertend(element * &begin, element * &end, int x)

{

element * node;

//Выделение памяти для добавляемого элемента

node=new element;

//Заполнение элемента

node->info=x;

node->next=0;

node->prev= end;

//Включение элемента в список

if(begin ==0)

begin = end =node;

else

{

end ->next=node;

end =node; }

}

void delp(element * &begin, element * &end, element * p)

{ //список не должен быть пустым

if (begin == end) //элемент единственный

{

begin = end =0;

delete p; //освобождение памяти

return;

}

if (p== begin) //первый элемент

{

begin = begin ->next;

begin ->prev=0;

delete p; //освобождение памяти

return;

}

if(p== end) //элемент последний

{

end = end ->prev;

end -> next=0;

delete p;/ освобождение памяти

return;

}

//Элемент посередине

p->next->prev=p->prev;

p->prev->next= p->next; }

delete p; //освобождение памяти

return;

}

void print(element* end)

{

element* node;

if {end==0)

cout<<”list is empty”<<endl;

else

{

node= end;

while (node!=0)

{

cout<<node->info<<' ';

node=node->prev;

}

cout<<endl;

}

}

10.2. Деревья

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