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

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

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

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

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

pnode = Anode; node = record

d: word; {информационная} s: string; {часть}

p: pnode; {указатель на следующий элемент} end;

ПРИМЕЧАНИЕ

Обратите внимание, что тип указателя pnode на запись node определен раньше, чем сама запись. Это не противоречит принципу «использование только после описания», поскольку для описания переменной типа pnode информации вполне достаточно.

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >