Динамические структуры данных

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

Элемент динамической структуры состоит из двух полей:

-информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура;

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

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

Достоинствами связного представления данных является следующее:

- размер структуры ограничивается только доступным объемом машинной памяти;

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

- большая гибкость структуры.

Вместе с тем связное представление не лишено и недостатков, основные из которых:

- на поля связок расходуется дополнительная память;

- доступ к элементам связной структуры может быть менее эффективным по времени.

Рассмотрим динамические структуры, наиболее часто используемые при решении прикладных задач, и их представление в памяти.

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

Структуры типа стек реализуются в виде специальным образом организованных областей ОЗУ компьютера либо в качестве самостоятельных блоков памяти. В стеке ячейки памяти (или регистры стековой памяти) соединяются друг с другом таким образом, что при занесении данных в первую ячейку содержимое всех остальных сдвигается в соседние ячейки вниз, а при считывании – содержимое сдвигается вверх по ячейкам (рис.8.6).

Структура стека и порядок ввода-вывода данных в нем.

Стек иногда называют магазин или очередь, функционирующая по принципу LIFO (Last-In-First-Out – "последним пришел - первым исключается").

Динамическая структураочередь отличается от стека только тем, что извлечение данных из нее производится в порядке «первым вошел – первым вышел». То есть очередь или очередьFIFO (First-In-First-Out – "первым пришел - первым исключается") – это такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка, которую называют концом или хвостом очереди, а исключение – с другой стороны, называемой началом или головой очереди (рис.8.7).

Структура очереди и порядок ввода-вывода данных.

Дек – особый вид очереди. Дек (от англ. deq – "doubleendedqueue", т.е. очередь с двумя концами) – это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Структура дека аналогична структуре FIFO очереди. Однако применительно к деку целесообразно говорить не о начале и конце, а о левом и правомконце.

Примером дека может быть терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.

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

Структура дерева.

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