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

Отображение

Дек.

Особенностью деков является то, что запись и удаление ячеек может производиться с двух концов дека (рис.11). В английской аббревиатуре дек записывается следующим образом - DEQ (Double Ended Queue - Очередь с двумя концами). Дек так же можно рассматривать и в виде двух стеков, соединенных нижними границами.

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

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

Отображение - функция, которая определена на множестве элементов одного типа main_type (тип области определения функции) и принимает значения из множества элементов другого типа – another_type (тип области значений). Тогда можно записать M(d)=r - отображение M ставит в соответствие элемент d типа main_type из области определения элементу r типа another_type из области значений.

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

Хотя динамика и не является отличительной чертой языка Паскаль, все же существует возможность создавать динамические объекты и оперировать с ними. Динамический объект представляет собой область памяти без идентификатора.

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

Рис. 12 - Графическое представление структуры данных

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

Плюсы динамических структур:

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

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

Динамические структуры тоже имеют свои минусы:

· отсутствие наглядности программы – вызывает трудности при создании особо крупных структур.

· работа с указателями требует, более высокой квалификации от программиста;

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

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

Практически любой АТД может быть эффективным образом представлен как на массиве, так и на файле или на динамической структуре, но чаще всего конкретное представление обусловлено особенностью доступа к элементам рассматриваемого абстрактного типа.