1. Теоретический раздел

Разработать алгоритм работы с динамической структурой данных – двунаправленный список: элементы добавляются в начало списка, а удаляются с конца списка. Элементы списка – символы.

Для ускорения многих операций целесообразно применять переходы между элементами списка в обоих направлениях. Это реализуется с помощью двунаправленных списков, которые являются сложной динамической структурой.

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

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

(Ниже представлен рисунок двунаправленного списка[6])

Для описания алгоритмов этих основных операций используется следующее объявление:

struct list { //структура данных

int index; //информационное поле

double a; //информационное поле

list *front, //адресное поле

*back; //адресное поле

};

. . . . . . . . . .

list *Head; //указатель на первый элемент списка

list *End; //указатель на последний элемент списка

. . . . . . . . . .

list *p; //указатель на текущий элемент списка

Операции двунаправленного списка схожи с одноправленным списком. Так как двунаправленный список более гибкий, чем однонаправленный, то при включении элемента в список, нужно использовать указатель как на элемент, за которым происходит включение, так и указатель на элемент, перед которым происходит включение. При исключении элемента из списка нужно использовать как указатель на сам исключаемый элемент, так и указатели на предшествующий или следующий за исключаемым элементы. Но так как элемент двунаправленного списка имеет два указателя, то при выполнении операций включения/исключения элемента надо изменять больше связей, чем в однонаправленном списке.

Рассмотрим основные операции, осуществляемые с двунаправленными списками.

Создание двунаправленного списка[6]

Для того, чтобы создать двунаправленный список, нужно создать сначала первый элемент списка и последний, а затем при помощи функции добавить к нему остальные элементы.

Head = new list; //выделяем память под первый элемент

Head->back = NULL; //обнуление адресного поля

End = new list; //выделяем память под последний элемент

End->front = NULL; //обнуление адресного поля

double f;

printf("Введите вещественное число: ");

scanf_s("%lf", &f);

p = new list; //выделяем память под текущий элемент

p->a = f; //заносим данные в переменную "а" текущего элемента

p->front = End; //в указатель "front" записываем адрес элемента "End"

p-> back = Head;//в указатель "back" записываем адрес элемента "Head"

Head->front = p; //для указателя первого элемента записываем адрес текущего элемента "р".

End->back = p; // для указателя последнего элемента записываем адрес текущего элемента "р".