Программирование на языке высокого уровня. Марапулец Ю.В. - 61 стр.

      Если до начала работы с данными невозможно определить, сколько памяти потре-
буется для их хранения, память выделяется по мере необходимости отдельными блока-
ми, связанными друг с другом с помощью указателей. Такой способ организации данных
называется динамическими структурами данных, так как их размер изменяется во
время выполнения программы. Из динамических структур в программах чаще всего ис-
пользуются динамически расширяемые массивы, линейные списки, стеки, очереди и
бинарные деревья. Они различаются способами связи отдельных элементов и допусти-
мыми операциями. Динамическая структура может занимать несмежные участки опера-
тивной памяти.
      Динамические структуры широко применяют и для более эффективной работы с
данными, размер которых известен, особенно для решения задач сортировки, по-
скольку упорядочивание динамических структур не требует перестановки элементов,
а сводится к изменению указателей на эти элементы. Например, если в процессе вы-
полнения программы требуется многократно упорядочивать большой массив данных,
имеет смысл организовать его в виде линейного списка. При решении задач поиска
элемента в тех случаях, когда важна скорость, данные лучше всего представить в ви-
де бинарного дерева.
      Элемент любой динамической структуры данных представляет собой структуру
(struct), содержащую по крайней мере два поля: для хранения данных и для указателя.
Полей данных и указателей может быть несколько. Поля данных могут быть любого ти-
па: основного, составного или типа указатель. Описание простейшего элемента (компо-
ненты, узла) выглядит следующим образом:

struct X
{
        Data Value; // тип данных Data должен быть определен ранее
        X *p;
};

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

     2.9.1. Динамически расширяемые массивы

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

struct MASSIV
{
        int nElement;//текущее количество элементов в массиве
        int maxElement;//количество элементов, для которых выделена память
        int *mass;//массив данных
} massiv;

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

                                          61