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

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

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

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

рации new или функции mallос (необходимый объем должен быть известен до

распределения памяти). В обоих случаях выделяется непрерывный участок па­

мяти.

Если до начала работы с данными невозможно определить, сколько памяти по­

требуется для их хранения, память выделяется по мере необходимости отдель­

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

организации данных называется динамическими структурами данных, посколь­

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

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

и бинарные деревья. Они различаются способами связи отдельных элементов и

допустимыми операциями. Динамическая структура может занимать несмежные

З^астки оперативной памяти.

Динамические структуры широко применяют и для более эффективной работы

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

поскольку упорядочивание динамических структур не требует перестановки эле­

ментов, а сводится к изменению указателей на эти элементы. Например, если

в процессе выполнения программы требуется многократно упорядочивать боль­

шой массив данных, имеет смысл организовать его в виде линейного списка. При

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

ше всего представить в виде бинарного дерева.

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

(в смысле struct), содержащую по крайней мере два поля: для хранения данных

и для указателя. Полей данных и указателей может быть несколько. Поля дан­

ных могут быть любого типа: основного, составного или типа указатель. Описа­

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

struct Node

{

Data d; // тип данных Data должен быть определен ранее

Node *р:

};:

Рассмотрим реализацию основных операций с динамическими структурами дан­

ных (в дальнейшем будет приведен пример реализации списка в виде шаблона

класса, см. с. 211).