1.1.4Статические массивы указателей в динамической памяти

Рассмотренный механизм использования статических массивов указателей на элементы списка предполагает наличие этого массива в статической памяти на весь период прогона программы. Однако если работа со списком занимает только определенный период времени во всем времени прогона программы, то статические массивы указателей на элементы списка можно расположить в динамической памяти. Такой массив создается, когда возникает необходимость в обработке списка, и уничтожается, когда необходимость в обработке списка исчезает.

Примечание. В языках C и C++ имя массива – это указатель на его первый элемент и указатель можно индексировать как массив.

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

int p [5]; //объявление массива из пяти целых чисел

В таком случае результат выражения p == &p[0] будет true.

int* p [5]; //объявление массива указателей на целые числа, состоящего

//из пяти элементов

Массив находится в статической памяти. Фактичски p – это указатель на первый элемент массива, который, в свою очередь, является указателем на целое число.

При таком объявлении данные в статической памяти будут располагаться следующим образом – рисунок 1.5:

Статическая память

		Массив указателей
P - адрес элемента		Индекс	Содержимое
массива с индексом 0		0	->на 1-е число
		1	->на 2-е число
		2	->на 3-е число
		3	->на 4-е число
		4	->на 5-е число

Рисунок 1.5 – Расположение данных в статической памяти при объявлении массива указателей на целые числа

Указатель на массив указателей в динамической памяти так же содержит адрес элемента массива с индексом 0. Но при объявлении такого указателя, массив не должен появляться в статической памяти.

int ** pp; //указатель, который содержит адрес указателя на целое число

//типа int.

При таком объявлении место в статической памяти под массив не выделяется. Выделяется только память для указателя - переменной pp.

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

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

При таком объявлении переменной pp данные в памяти расположены следующим образом – рисунок 1.6:

Статическая память

PP

Рисунок 1.6 – Расположение данных в статической памяти при объявлении указателя на указатель на целые числа

Для того, чтобы в динамической памяти появился массив указателей, необходимо выделить для него место при помощи оператора new.

В общем виде запрос на выделение памяти для массива с помощью оператора new имеет такой вид:

указатель = new тип_элемента_массива[размер массива];

или

указатель = new тип_массива[размер массива];

В случае, если требуемый участок памяти не был выделен, операция new возвращает значение NULL

Для освобождения динамической памяти, занятой массивом, применяется следующая форма оператора delete:

delete [ ] указатель;

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

Используем оператор new для размещения массива указателей на целые числа в динамической памяти:

int ** pp;

pp = new int* [5]; /*эта запись означает – выделить участок динамической

памяти для массива из 5 элементов типа указатель на

целое число int* и адрес выделенного участка памяти

занести в переменную pp*/

тип элемента массива

После выполнения указанного оператора данные в памяти будут расположены следующим образом – рисунок 1.7:

Статическая память Динамическая память

		Массив указателей
PP адрес элемента		Индекс	Содержимое
массива с индексом 0		0	->на 1-е число
		1	->на 2-е число
		2	->на 3-е число
		3	->на 4-е число
		4	->на 5-е число

Рисунок 1.7 – Расположение данных в оперативной памяти при расположении массива указателей в динамической памяти

При этом самих целых чисел в динамической памяти еще нет. Указатели массива указателей содержат неопределенные значения.

Следующий участок программы демонстрирует, как разместить первое число в памяти и занести в него значение 35:

int * * pp;

pp = new int* [5];

pp[0] = new int; /*Адрес выделенного для целого числа участка динамической

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

Здесь происходит индексирование самого указателя*/

*pp[0] = 35; /*Сначала получаем доступ к нулевому указателю в массиве

указателей, а затем, при помощи оператора разыменования

получаем доступ к целому числу, куда заносим значение 35*/

Теперь данные в памяти будут расположены следующим образом – рисунок 1.8:

Статическая память Динамическая память

		Массив указателей
PP адрес элемента		Индекс	Содержимое
массива с индексом 0		0	->на 1-е число		35
		1	->на 2-е число
		2	->на 3-е число
		3	->на 4-е число
		4	->на 5-е число

Рисунок 1.8 – Расположение массива указателей и первого элемента списка в динамической памяти

Примечание. В системе VisualStudio C++ существует возможность получить информацию о свободных и занятых участках кучи. Для этого используется функция

int _heapwalk( _HEAPINFO * hiinfo );

Для ее использования необходимо подключить файл <malloc.h>.

Функция сканирует очередной блок кучи и возвращает указатель на структуру типа _HEAPINFO . Данная структура имеет три поля:

int* _pentry; // указатель на текущий блок кучи

size_t _size; // размер текущего блока;

int _useflag; // флаг – используется блок (значение - 1) или нет (знач.0)

Если результат проверки блока оказался успешным и проверяемый блок был не последним, то функция возвращает как результат – значение _HEAPOK и заполняет поля структуры следующим образом:

• полю _size присваивает размер текущего блока;

• поле-флаг _useflag устанавливается в одно из вышеуказанных значений (0 или 1: _FREEENTRY или _USEDENTRY);

• поле _pentry получет указатель на следующий блок кучи.

Ниже приводится пример использования функции _heapwalk для вычисления размера свободной кучи. По нажатию на кнопку button1 в комопнент listBox выводится информация о размере блока кучи и его занятости. В конце списка информации о блоках будет выведен суммарный размер свободной области кучи .

private: System::Void button1_Click(System::Object* sender, System:: EventArgs* e)

/*Вычисление размера свободной кучи*/

{

_HEAPINFO hinfo;

int heapstatus;

int sum_free=0; /*переменная содержит количество свободных

байт кучи*/

hinfo._pentry = NULL; /*инициализация указателя на текущий блок*/

/*Цикл – пока не будут просмотрены все блоки кучи*/

while( ( heapstatus = _heapwalk( &hinfo ) ) == _HEAPOK )

{

/*Формируется строка о текущем блоке – состояние и размер*/

System::String *k=System:: String:: Concat ((hinfo._useflag == _USEDENTRY

? S"Используется" : S"Свободен "), S" ", hinfo._size ToString());

listBox1->Items->Add(k);

if (hinfo._useflag==0) /*Если блок свободен, то его размер добавляется в

sum_free*/

{

sum_free=sum_free + hinfo._size;

}

}

listBox1->Items->Add (S"ВСЕГО СВОБОДНЫХ БАЙТ:");

listBox1->Items->Add (Convert::ToString(sum_free));

}

Результат работы функции вычисления размера свободной кучи выглядит таким образом – рисунок 1.9:

Рисунок 1.9 – Результат работы функции вычисления размера свободной кучи

После рассмотрения примера для массива указателей на целые числа не будет никаких трудностей для рассмотрения массива указателей на структуры.

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

const SizeArrH = 20; /*верхняя граница массива указателей*/

typedef struct ElmList

{

char Name[30];

int Age;

char Address[30];

} TElmList; /*тип для элемента списка */

Объявление необходимых переменных для работы со списком:

TElmList** PtrStatArrPtrElmList ; /*указатель на начало массива указателей*/

int Count; /*реальное количество элементов списка*/

Здесь вводится переменная PtrStatArrPtrElmList – указатель на статический массив указателей на элементы списка.

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

В языке C++ есть альтернативный способ динамического распределения памяти, основанный на функциях malloc() и free(). Они сохранены для того, чтобы достичь совместимости с языком С.

Заголовок функции malloc() имеет вид:

void * malloc(size);

Эта функция запрашивает участок памяти размером size байт и возвращает нетипизированный указатель, содержащий адрес 1-го байта выделенного участка памяти.

Заголовок функции free():

void free(нетипизированный указатель);

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

Однако, применение в программах на языке С++ операторов new и delete имеет ряд преимуществ. Поэтому следует применять именно эти операторы.

PtrStatArrPtrElmList = new TElmList* [SizeArrH];

где TElmList* – тип элемента массива указателей, SizeArrH – размер массива.

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

delete [ ] PtrStatArrPtrElmList ;

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

PtrStatArrPtrElmList[5]

Здесь сначала с помощью указателя PtrStatArrPtrElmList выполняется доступ к началу массива указателей на элементы списка. Затем выполняется доступ к 5-му элементу массива указателей.

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

*PtrStatArrPtrElmList[5]

Здесь сначала с помощью указателя PtrStatArrPtrElmList выполняется доступ к началу массива указателей на элементы списка. Затем выполняется доступ к 5-му элементу массива указателей, после чего выполняется доступ к первому байту 5-го элемента списка.

Обращение к конкретному полю элемента списка. Пусть полю Name и полю Age 5-го элемента списка необходимо присвоить некоторые значения. Это выполняется следующим образом:

PtrStatArrPtrElmList[5]->Age=18;

strcpy (PtrStatArrPtrElmList [5] -> Name, "Диброва");

и, наоборот,

int d=PtrStatArrPtrElmList[5]->Age;

char s[30];

strcpy (s, PtrStatArrPtrElmList [5] -> Name);

Здесь сначала с помощью указателя PtrStatArrPtrElmList выполняется доступ к началу массива указателей на элементы списка. Затем выполняется доступ к 5-му элементу массива указателей, после чего выполняется доступ к первому байту 5-го элемента списка, после чего выполняется доступ к полю Name 5-го элемента списка.