Понятие динамической структуры данных. Стек. Очередь. Кольцевая очередь. Очередь с приоритетами. Бинарное дерево

Динамические структуры данных – это структуры данных, память под которые выделяется и освобождается по мере необходимости.

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

Динамическая структура данных характеризуется тем что:

· она не имеет имени;

· ей выделяется память в процессе выполнения программы;

· количество элементов структуры может не фиксироваться;

· размерность структуры может меняться в процессе выполнения программы;

· в процессе выполнения программы может меняться характер взаимосвязи между элементами структуры.

Необходимость в динамических структурах данных обычно возникает в следующих случаях.

· Используются переменные, имеющие довольно большой размер (например, массивы большой размерности), необходимые в одних частях программы и совершенно не нужные в других.

· В процессе работы программы нужен массив, список или иная структура, размер которой изменяется в широких пределах и трудно предсказуем.

· Когда размер данных, обрабатываемых в программе, превышает объем сегмента данных.

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

Необходимость в динамических структурах данных обычно возникает в следующих случаях.

· Используются переменные, имеющие довольно большой размер (например, массивы большой размерности), необходимые в одних частях программы и совершенно не нужные в других.

· В процессе работы программы нужен массив, список или иная структура, размер которой изменяется в широких пределах и трудно предсказуем.

· Когда размер данных, обрабатываемых в программе, превышает объем сегмента данных.

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

Достоинства связного представления данных – в возможности обеспечения значительной изменчивости структур:

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

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

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

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

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

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

Порядок работы с динамическими структурами данных следующий:

1. создать (отвести место в динамической памяти);

2. работать при помощи указателя;

3. удалить (освободить занятое структурой место).

К таким структурам относят:

· однонаправленные (односвязные) списки;

· двунаправленные (двусвязные) списки;

· циклические списки;

· стек;

· дек;

· очередь;

· бинарные деревья.