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

Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.

Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.

Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.

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

Функции, работающие с динамической памятью, используются для создания динамических переменных и массивов произвольных типов. Единственно важным для них является размерность структур данных, выраженная естественным для С способом в байтах (при помощи операции sizeof).

Адрес выделенной области памяти также возвращается в виде указателя типа void* - абстрактный адрес памяти без определения адресуемого типа данных. Рассмотрим объявления основных функций:

void *malloc(int size);

// выделить область памяти размером

// в size байтов и возвратить адрес

void *calloc(n, sizeof(objеct));

// выделить область памяти, достаточной для размещения

// n объектов указанного размера

void free(void *p);

// освободить область памяти,

// выделенную по адресу p

void *realloc(void *p, int size);

// расширить выделенную область памяти

// до размера size, при изменении адреса

// переписать старое содержимое блока

Пример:

Создание простой динамической переменной:

double *pd;

pd = malloc(sizeof(double));

if (pd !=NULL)

{

*pd = 5;

...

free(pd);

}

Организация линейных списков

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

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

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

Линейный список F, состоящий из элементов D1, D2, ..., Dn, записывают в виде последовательности значений заключенной в угловые скобки F=<D1,D2,...,Dn>, или представляют графически (см.Рис. 2).

Рис.2.

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

- найти элемент с заданным свойством;

- определить первый элемент в линейном списке;

- вставить дополнительный элемент до или после указанного узла;

- исключить определенный элемент из списка;

- упорядочить узлы линейного списка в определенном порядке.

Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. При последовательном хранении элементы линейного списка размещаются в массиве фиксированного размера и длина списка указывается в переменной , т.е. в программе необходимо иметь объявления вида:

float d[100]; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка.

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

typedef struct snd /* структура элемента хранения */

{ float val; /* элемент списка */

struct snd *n ; /* указатель на элемент хранения */

} DL;

DL *p; /* указатель текущего элемента */

DL *dl; /* указатель на начало списка */

Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). Формирование списка в связанном хранении может осуществляется операторами:

p=malloc(sizeof(DL));

p->val=10; p->n=NULL;

dl=malloc(sizeof(DL));

dl->val=7; dl->n=p;

В последнем элементе хранения (конец списка) указатель на соседний элемент имеет значение NULL. Получаемый список изображен на рис.3.

Рис.3.