Методические указания к выполнению контрольных работ по дисциплине "Основы программирования" (стр. 36 из 40)

8. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ.

РАБОТА СО СПИСКАМИ

8.1. Динамическое выделение и освобождение памяти

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

Ранее нами были рассмотрены функции типа alloc, предназначенные для управления памятью. Операции new и delete языка «С++» позволяют программисту выделять память из общей «кучи» памяти компьютера – RAM-ресурса и освобождать ее, т.е. возвращать в «кучу». Они заменяют такие функции Unix и Windows, как malloc, calloc и free, используемые в языке «С».

Есть два основных способа использования операции new:

Способ 1: float *r = new float;

Способ 2: float *r = new (float);

Оба способа использования операции new эквивалентны.

Операция new является функцией, возвращающей значение true, если требуемая память доступна, или false, если нет свободной памяти требуемого размера.

Операция delete может использоваться следующим образом:

float *r = new float[20];

...

delete r;

Что если операция delete используется с указателем, для которого память не была выделена при помощи операции new, либо была освобождена ранее? – Это ошибка. Каждая система ведет себя в этом случае по-своему. В общем случае ответственность за недопущение подобных ситуаций лежит на программисте.

Рассмотрим более сложный пример: выделение памяти для структуры определенного формата. Допустим, что необходимо создать список населенных пунктов, причем длина списка – каждый раз различная. Поэтому конструкция типа «массив структур» для использования в программе не подходит. По-видимому, как это будет видно в следующем параграфе, для создания такого списка и работы с ним нужна более сложная организация памяти (по сравнению с массивом), которая так и называется: «список». Рассмотрим структуру для описания одного населенного пункта scb:

struct scb

{

char village[25];// Название населенного пункта

double lat; // Географическая широта

double lon; // Географическая долгота

struct scb *sb; // Указатель на следующий пункт

struct scb *th; // Указатель на предыдущий пункт

};

Структура scb содержит три элемента памяти: название населенного пункта (символьная строка строка char village[25]) и его географические координаты – широту (double lat) и долготу (double lon). Кроме того, в списке имеются два указателя (sb и th) для размещения служебной информации, которая будет использоваться в следующем параграфе.

Указатель space на память, выделенную для структуры типа scb описывается как:

struct scb *space;

После удачного выполнения операторов:

if( !(space = new scb))

printf("Нет памяти для нового элемента списка!\n");

указатель space содержит адрес вновь выделенного элемента памяти.

8.2. Понятие списка; основные виды списковых образований

В предыдущей главе мы рассмотрели структуры, ссылающиеся на себя, на примере «двоичного дерева». Однако, двоичное дерево – это один из частных случаев сложной организации данных в памяти компьютера (как в оперативной памяти RAM, так и на винчестере HDD, и на компакт-диске CD-ROM), называемой «список». Основной элемент списка – это «узел», являющийся структурой.

Узлы имеют уникальную информацию, номер или имя. Списки представляются в виде направленных графов. Если из узла A в узел B проведена стрелка, то это означает следующее: в структуре A есть указатель, в котором содержится адрес структуры B, т.е. от информации узла A очень просто перейти к информации узла B.

Существуют следующие виды типовых списков: линейные, кольцевые и деревья. Линейные подразделяются на:

·

линейный однонаправленный (рис. 8.1-а);

· линейный двунаправленный (рис. 8.1-б).

Кольцевые списки также подразделяются на однонаправленные списки (рис. 8.1-в) и двунаправленные (читатель без труда может представить его сам). Пример дерева был рассмотрен в предыдущей главе (см. рис. 8.1).

Кроме того, для специальных применений (при создании новых операционных систем ОС, систем управления базами данных СУБД, систем имитационного моделирования СИМ) списки являются основой соответствующих управляющих программ. На рис. 8.2. приведен без комментариев внутренний аппарат современной системы имитационного моделирования Pilgrim-5, применяемой для компьютерного моделирования экономических процессов^*, который построен на основании сложного спискового образования в оперативной памяти компьютера.

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

lenth – число узлов в списке;

listbeg – указатель на первый узел в списке;

listend – указатель на последний узел в списке;

current – указатель на обрабатываемый узел.

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

8.3. Создание и удаление списка

Пример 8-1. Далее рассмотрим программу createlist, которая построит линейный двунаправленный список из элементов памяти типа структуры scb. Если к ней обратиться, например, как createlist(20), то она построит список из 20 узлов (см. рис. 8.1-б). Текст этой программы приведен ниже.

// Глобальные описания и переменные

struct scb

{

double lat; // Географическая широта пункта

double lon; // Географическая долгота пункта

struct scb *sb; // Указатель на следующий пункт

struct scb *th; // Указатель на предыдущий пункт

char village[25]; // Название населен. пункта

int number; // Номер пункта (и узла)

};

int lenth; // Число узлов в списке

struct scb *current; // Указатель на текущий узел

struct scb *listbeg; // Указатель на первый узел

struct scb *listend; // Указатель последнего узла

// createlist: создает двунаправленный список

int createlist(int n)

{

struct scb *space; // Рабочий указатель

struct scb *slast; // Предпоследний указатель

int i;

for (i=1; i <= n; i++)

{

slast = space;

if( !(space = new scb))

{

printf("Нет памяти для нового узла!&bsol;n");

return 0;

}

listend = space; // Последний узел

lenth = i; // Длина списка

space->number = i; // Порядковый номер

if( i == 1) // Выделен первый узел

listbeg = space;

else // Выделен второй или более

{

slast->sb = space; // Прямая связь

space->th = slast; // Обратная связь

}

}

current = listbeg;

return i; // Возвращается длина списка

}

Функция createlist возвращает нулевое значение (false), если список не построен, либо целое число – количество узлов в списке (true). Все узлы пронумерованы с помощью оператора присваивания:

space->number = i .

После выполнения этой функции указатель на текущий узел current показывает на узел, стоящий первым в списке и имеющий номер 1. Но далее, в процессе работы со списком, указатель current всегда показывает на последний узел, который обрабатывала главная программа (например, программа main).

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

1) программу уничтожения списка – возврата всей памяти, занимаемой им в общую «кучу» оперативной памяти компьютера (назовем её условно deletelist);

2) программу позиционирования – получения доступа к узлу списка, имеющего соответствующий признак (условное название knotpointer);

3) программу добавления нового узла, имеющего определенный признак, в соответствующее место списка (назовем её условно knotin);

4) программу исключения узла списка, имеющего соответствующий признак (условное название knotout).

Далее рассмотрим назначение этих программ.

Пример 8-2. Программа уничтожения списка нужна обязательно. Дело в том, что программа createlist создает список, запрашивая память для его узлов у операционной системы с помощью операторов new. Эта программа – функция, к которой обращается более главная программа (например, main). Если функция createlist, создавшая список с помощью динамического распределения памяти, завершится, а память, выделенная этой программой для списка, не освобождена, то вся эта память передается операционной системой без освобождения главной программе, вызвавшей функцию createlist (т.е. программе main). Но если главная программа тоже строит списки, то доступная оперативная память компьютера (один из главных ресурсов операционной системы) может исчерпаться. – Когда это произойдет, главная программа не сможет выполняться (часто это наблюдается в виде «зависания компьютера»). Часто списки, память которых уже не нужна, называются «программным мусором», а соответствующие программы уничтожения списков называются программами-мусорщиками.