11. Динамические струкутуры данных. Работа динамической памяти в c.

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

Во многих задачах требуется использовать данные, у которых конфигурация, размеры и состав могут меняться в процессе выполнения программы. Для их представления используют динамические информационные структуры. К таким структурам относят:

• линейные списки (однонаправленные, двунаправленные, циклические);

• стек;

• очередь;

• деревья;

• динамические массивы (нерекурсивная).

Они отличаются способом связи отдельных элементов и/или допустимыми операциями. Динамическая структура может занимать несмежные участки оперативной памяти.

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

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

Память:

программы

данные

heap/куча

P

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

Функция p=выделить(N) возвращает указатель на объект памяти длиной N,

В Си – p=new(N) (неопределенный тип указателя).

Проблемы:

1. Типизация указателя.

В языка строгой типизации int *p и char*g - не эквивалентны => необходимо преобразование типа.

2. Освобождение выделяемой памяти

• Явный механизм (программист) – функция уничтожить(р);

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

3. Проблема висящих объектов (когда один динамический объекс ссылается на другой динамический объект)

В памяти остаются объекты с отсутствием ссылок. Уничтожив этот объект, можно потерять ссылки на все его подобъекты.

4. Проблема висящих указателей (остются ссылки на уничтоженные объекты);

5. Фрагментация памяти

heap

P1

P2

P3

P4

P5

Уничтожим р3 и р5 – на новый объект хватит памяти, но не будет цельного

куска.

Правила при работе с динамической памятью при наличии явных механизмов уничтожения:

1. Не допускать наличие висящих объектов. Для этого сначала надо уничтожить все вложенные объекты.

2. Не допускать висящих ссылок, т. е. после уничтожения объекта уничтожить и ссылку на него - p=NULL.

3. Минимизировать фрагментацию. Для этого нужно уничтожать объекты в порядке обратном порядку их создания: р5 – р4 – р3.

Реализация механизма динамической памяти в C:

1. Выделение динамической памяти через функцию void *malloc(size_t size).

Например, если нужно 10 элементов массива, то:

int A;

A=(int*)malloc(10 * sozeof(int)).

Размер требуемой памяти size_t size может быть больше, чем требуется (для выравнивания)

2. Функция void *calloc(size_t num, size_t size);

все значения в полученной памяти нулевые.

3. void free (void*p)

указатель указывает на ранее захваченный блок памяти операциями malloc, calloc, realloc, т. е. число освобождаемых байтов = числу байтов, полученных при захвате

преобразование int в void free((void *) A);

4. Функция void *realloc(void*p, size_t new size)

Изменяет размер ранее захваченного блока памяти, p – указатель на начало блока, size – размер в байтах. Блок может быть передвинут в памяти при изменении размера.