41. Полустатическая структура данных очередь. Операции над структурой данных очередь.

Очередь – это такой последовательный список с переменной длиной включение элементов в который происходит с одной стороны а исключение из другой стороны списка.

Для организации очереди необходимо 2 указателя: начала и конца очереди

(1)

p1

p2(m)

В реальности очередь может иметь конечное число элементовР1 указатель начала (первый элемент), р2 указатель конца (на последний свободный элемент)Основные операции включение/исключение Исключение – состоит в чтении данных, местоположение которых определяется значение указателя на начало очереди, т.е. р1 путем передвижения его на следующий элемент очереди.Очередь пуста когда р1=р2Включение – элемент записывается по адресу конца очереди р2 и указатель р2 перемещается вправо на свободный элемент очереди. Но есть ограничения - это выход р2 за границу очереди, этого можно избежать при организации кольцевой очереди.В кольцевой очереди указатель конца очереди р2 переводится с последнего элемента m на 1ый элемент, если он пуст.

42. Полустатическая структура данных дек. Операции над структурой данных дек.Дек - это последовательный список, в котором как добавление, так и исключение элементов может происходить и с одной, и с другой стороны, т.е. очередь с 2-мя концами и началами Выделяют частный случай дека: с ограниченным входом(1 вход, 2 выхода) с ограниченным выходом (1 выход, 2 входа) Выполняются операции включение/исключение элементов. Операции выполняются аналогично операциям над очередью, но при этом одним из параметров доступа в деку должен быть признак того конца, с которого должна была выполняться соответствующая операция

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

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

2) логическая последовательность элементов задается в явном виде с помощью одного или нескольких указателей, хранящихся в самих элементах. Из-за отсутствия физической смежности элементов память, занимаемая структурой, не представляет собой непрерывную область, т.е. элементы динамической структуры могут быть разбросаны в памяти хаотичным образом. Следствием такой особенности является усложнение процедур доступа к элементам динамических структур по сравнению со статическими и полустатическими структурами.

Часто динамические структуры представляются в форме связных списков, поэтому их часто называют списковыми структурами, подразумевая под списком связный список.

Связный список - это такая структура, элементами которой служат записи с одним и тем же форматом, связанные друг с другом с помощью указателей, хранящихся в самих элементах,

Простейший связный список –односвязный список.