8.3. Сортировка на основе бинарного дерева Статические и динамические данные.

Статические и динамические данные. В предыдущих главах были рассмотрены как элементарные типы данных (целые, вещественные, символьные), так и более сложные производные типы (массивы, указатели, объединения и структуры). Для объектов перечисленных основных типов при определении задаются диапазон изменения соответствующих им значений и размер выделяемой для них памяти. В силу этого такие объекты могут считаться статическими. Однако для решения ряда задач, возникающих при построении информационных систем, разработке баз данных, построении протоколов передачи данных в телекоммуникационных сетях и т. п., требуются информационные объекты с более сложной структурой. В процессе обработки этих информационных объектов могут изменяться не только значения объектов, но даже их конфигурация. Такие объекты (мы уже рассматривали их в §6.4) называют динамическими информационными структурами (см. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989.-С. 213). Следует заметить, что компоненты динамических информационных структур на нижних уровнях детализации представляют собой статические объекты, принадлежащие к одному из основных типов данных. Таким образом, основные типы данных используются для формирования более сложных информационных конструкций.

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

Исполняемую программу на языке Си после компиляции и загрузки в память условно можно разделить на 4 части: область команд, стек, область статических данных и область динамических данных. Область команд содержит машинные команды. Стек используется для временного хранения данных и адресов возврата при вызове функций. Область статических данных обеспечивает хранение значений переменных программы, а в области динамических данных размещаются при исполнении программы дополнительные данные, которые могут понадобиться в процессе ее работы. На рис. 8.11 приведена одна из схем распределения адресного пространства выполняемой программы.

Рис. 8.11. Схема распределения оперативной памяти процесса

Управление динамической памятью.

Управление динамической памятью. Как мы уже упоминали, в библиотеке языка Си есть функции выделения и освобождения динамической памяти. Благодаря наличию таких функций отпадает необходимость заранее резервировать для программы всю доступную память, что оказывается полезным в ситуациях, когда требуемый объем памяти заранее не известен или зависит от конкретного применения программы.

Работа с динамической памятью (выделение памяти, изменение размера ранее занятого участка, освобождение памяти) производится с помощью функций malloc( ), calloc( ), realloc( ), free( ), описанных в §4.2. Использование функций malloc( ), calloc( ), free( ) выше продемонстрировано на многочисленных примерах. Остановимся на особенностях функции realloc( ).

Функция realloc( ) может быть использована для изменения размера ранее занятого участка памяти. При этом адрес начала участка может измениться. Описание (прототип) функции realloc( ):

void *realloc ( void *oldptr, unsigned int new_size);

где oldptr - указатель на участок памяти, ранее выделенный с помощью функции malloc( ) или calloc( ); new_size - размер требуемой памяти.

Стандарт языка Си [5] рекомендует для устранения влияния "перемещений" выделяемого с помощью realloc( ) участка памяти следующим образом использовать функцию realloc( ):

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

Необходимо отметить, что все функции, за исключением функции free(), возвращают значение указателя, равное NULL, если для выделения запрошенного участка памяти не хватает.