Динамическое распределение памяти

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

Во многих задачах часто заранее неизвестно, сколько программа будет хранить объектов данных (чисел, строк текста, структур и т.п.). В таких случаях требуется введение динамических структур данных, размер которых может меняться в процессе работы программы. Сама программа, а не компилятор, должна распределять свободное место в динамической памяти (называемой также “кучей” (heap)) для элементов таких структур и устанавливать связи между ними.

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

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

struct УЗЕЛ { тип переменная; /* поле информации узла */

…

УЗЕЛ *переменная; /* указатель для связи с другими */

… /* узлами */

};

Для работы с динамическими структурами используются следующие типичные функции:

· поиск нужного элемента;

· включение нового элемента;

· удаление существующего элемента;

· присваивание указателю элемента ссылки (адреса первого байта) на другой элемент, либо значения NULL (отсутствие ссылки).

Для динамического управления памятью, выделяемой под элементы в “куче”, используются функции, подключаемые в программе заголовочным файлом <alloc.h>:

· void *malloc (nbytes) – выделяет блок памяти размером nbytes байтов и возвращает указатель на первый байт блока.

· void *calloc (nelem, elsize) – выделяет блок памяти для nelem элементов по elsize байтов каждый (всего nelem * elsize байтов), обнуляет выделенную память и возвращает указатель на нее.

· void *realloc (*block, size) – делает попытку установить новый размер size блока, на начало которого ссылается указатель block.

· free (*block) – освобождает блок памяти, на начало которого ссылается указатель block.

К динамическим структурам относятся следующие связанные структуры: очередь, стек, списки, бинарные деревья, работа с которыми рассмотрена ниже.