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

Модели памяти.

Существует несколько видов моделей памяти: 1) малая модель; 2) средняя модель; 3) компактная модель; 4) большая модель; 5) максимальная модель.

В малой (small) модели памяти программа занимает два стандартных сегмента: сегмент кода и сегмент данных, в котором размещен также стек. Малая модель подходит для большинства программ и потому назначается компилятором по умолчанию.

В средней (medium) модели памяти для данных и стека программы выделяется один сегмент, а для кода — столько сегментов, сколько потребуется. Каждому исходному модулю программы выделяется собственный сегмент кода.

В компактной (compact) модели программному коду выделяется только один сегмент, а данным — столько сегментов, сколько потребуется. Компактная модель применяется для программ, небольших по количеству операторов, но работающих с большим объемом данных.

В большой (large) модели и под код, и под данные выделяется несколько сегментов. Большая модель используется для больших программ с большим объемом данных.

Максимальная (huge) модель аналогична большой модели, за исключением того, что в ней снимается ограничение на размер массивов.

Статические и динамические данные.

Статические данные — это все данные, объявленные в программе с классом памяти extern или static. Формальные параметры функций и локальные переменные функций и блоков не являются статическими данными. Они хранятся не в сегменте данных, а в сегменте стека. Он обычно совмещен со стандартным сегментом данных физически.

Динамические данные – это данные, внутреннее строение которых формируется по какому-либо закону, но количество элементов, их взаиморасположение и взаимосвязи могут динамически изменяться во время выполнения программы, согласно закону формирования.

Функции, поддерживающие основные операции с динамической памятью.

Динамически распределяемую память следует использовать в случае если мы заранее (на момент написания программы) не знаем сколько памяти нам понадобится и при работе с большими объемами данных.

Для работы с динамической памятью в языке С++ используются следующие функции: malloc, calloc, free, realloc.

Функция malloc, входным параметром которой является размер требуемой области динамической памяти в байтах, а выходным – значение типа void *, указывающее на первый байт выделенной области (void *malloc(size_t size)). Например, для выделения памяти под 1 000 000 int`ов необходимо выполнить следующий код:

int * p = (int *) malloc(1000000*sizeof(int));

Если ОС не смогла выделить память, то malloc возвращает 0.

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

Функция calloc. Функция работает аналогично malloc, но отличается синтаксисом (вместо размера выделяемой памяти нужно задать количество элементов и размер одного элемента) и тем, что выделенная память будет обнулена. Например, после выполнения

int * q = (int *) calloc(1000000, sizeof(int));

q будет указывать на начало массива из миллиона int`ов инициализированных нулями.

Функция realloc. Функция изменяет размер выделенной памяти. Если размер указанный в параметре size больше, чем тот, который был выделен под указатель ptr, то проверяется, есть ли возможность выделить недостающие ячейки памяти подряд с уже выделенными.

Операторы new и delete.

В С++ есть свой механизм выделения и освобождения памяти — это операторы new и delete.

Синтаксис оператора new:

тип данных *имя_указателя = new тип_данных(значение).

Пример использования new:

int * p = new int[1000000]; // выделение памяти под 1000000 int`ов

Т.е. при использовании функции new не нужно приводить указатель и не нужно использовать sizeof().

Освобождение выделенной при помощи new памяти осуществляется посредством следующего вызова:

delete [] p;

Если требуется выделить память под один элемент, то можно использовать:

int * q = new int;

или

int * q = new int(10); // выделенный int проинциализируется значением 10

в этом случае удаление будет выглядеть следующим образом:

delete q;

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

Динамические структуры данных – это структуры данных, память под которые выделяется и освобождается по мере необходимости.

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

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