Рис. 15.1. Два связанных объекта класса с самоадресацией

15.3. Динамическое вьщеление памяти

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

Операции new и delete являются основными при динамическом распределении памяти. Операция new принимает в качестве аргумента тип динамически размещаемого объекта и возвращает указатель на объект этого типа. Например, оператор

Node *newPtr = new Node(10);

выделяет область памяти размером sizeof(Node) байтов и сохраняет указатель на эту область памяти в указателе элементе newPtr. Если такого объема свободной памяти не имеется, то операция new возвращает нулевой указатель. Число 10 представляет собой число размещаемых объектов данных.

объявляется; такие классы мы будем называть классами с самоадресацией . Элемент nextPtr используется как связь, то есть nextPtr может быть использован для связи объекта типа Node с другим объектом того же типа. У класса типа Node имеется также пять функций-элементов: конструктор, который принимает данные целого типа для инициализации элемента data, функция-элемент для установки значения data, функция-элемент getData, возвращающая значение data, функция-элемент setNextPtr для установки значения элемента указателя nextPtr, а также функция-элемент getNextPtr, которая возвращает значение элемента указателя nextPtr.

Объекты классов с самоадресацией могут связываться друг с другом, формируя такие полезные структуры данных, как списки, очереди, стеки и деревья. На рис. 15.1 показаны два объекта класса с самоадресацией, связанных вместе для создания списка. Заметим, что обратный слэш (\), изображающий нулевой указатель (О), помещен в элемент связи второго объекта только чтобы было ясно, что эта связь не указывает на какой-либо другой объект. Этот символ имеет чисто иллюстративное назначение и никак не связан с символом обратного слэша (\), используемым в языке С-Ы-. Нулевой указатель обычно отражает конец структуры данных так же, как нулевой символ (\0) отражает конец строки.

Типичная ошибка программирования 15.1

Указатель связи в последнем узле не устанавливается на нуль (0).

Типичная ошибка программирования 15.2

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

Хороший стиль программирования 15.1

Используя операцию new проверьте, не вернула ли она нулевой указатель. Выполните соответствующую обработку ошибки, если операция new не выделила область памяти.

Типичная ошибка программирования 15.3

Не осуществляется возвращение динамически вьщеленной памяти, когда эта память уже более не требуется. Это может явится причиной преждевременного переполнения памяти. Иногда это явление называют утечкой памяти .

Хороший стиль программирования 15.2

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

Типичная ошибка программирования 15.4

Освобождение операцией delete памяти, которая не была выделена динамически операцией new.

Типичная ошибка программирования 15.5

Ссылка на область памяти, которая была освобождена.

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

delete newPtr;

Заметим, что сам указатель newPtr не удаляется, исчезает только область памяти, на которую указывал newPtr.

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

Замечание по мобильности 15.1

Размер объектов класса не обязательно равен сумме своих данных-элементов. Это происходит из-за различных машинно-зависимых требований по выравниванию границ областей памяти (см. главу 16) и по другим причинам.

15.4. Связные списки

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

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

Совет по повышению эффективности 15.1

Можно объявить размер массива таким, чтобы он мог вместить большее число элементов, чем ожидается. Но это может привести к избыточному расходу памяти. Связные списки могут обеспечивать более рациональное использование памяти. Связные списки позволяют программе настраиваться во время счета.

Связные списки могут сортироваться просто путем вставки каждого нового элемента в соответствующую позицию в списке. При этом существующие элементы списка не надо перемещать.

Совет по повышению эффективности 15.2

Операции вставки и удаления в отсортированном массиве могут быть продолжительными по времени, так как все элементы, следующие за вставляемым или удаляемым, должны быть соответствующим образом сдвинуты.

Совет по повышению эффективности 15.3

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

Узлы связных списков обычно физически не хранятся в памяти по соседству друг с другом. Однако, логически они как бы хранятся подряд. На рис. 15.2 представлен связный список с несколькими узлами.