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

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

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

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

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

Описание простейшего элемента структуры выглядит следующим образом:

Type

PComp = ^Comp;

Comp = record

D:<тип данных>;

Link: PComp;

end;

Для дальнейшего рассмотрения представим отдельную компоненту в виде:

Рассмотрим основные правила работы с динамическими структурами.