блоки памяти одинакового размера. Это типичный случай. Альтернативный метод отслеживания памяти, доступной для распределения, напрашивается сам: достаточно использовать связный список! Все узлы, которые не входят ни в один используемый список, можно совместно содержать в единственном связном списке. Этот список называется свободным (free list). Когда необходимо выделить пространство под узел, оно извлекается за счет удаления из свободного списка. При удалении узла из какого-либо списка, он вставляется в свободный список.

Профамма 3.14 является реализацией интерфейса, описанного в программе 3.12, включая функции распределения памяти. При совместной компиляции с программой 3.13 она дает такой же результат, что и прямая реализация, с которой мы начали в профамме 3.9. Содержание свободного списка для узлов фиксированного размера ~ тривиальная задача при наличии базовых операций вставки и удаления узлов из списка.

Программа 3.14 Реализация интерфейса обработки списков

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

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

#include <stdlib.h> #include list.h link freelist; void construct(int N) {

freelist = new node[N+l]; for (int i = 0; i < N; i++)

freelist[i].next = &freelist[i+l]; freelist[N].next = 0;

link newNode(int i) { link X = remove(freelist); x->item = i; x->next = x; return X;

void deleteNode(link x)

{ insert(freelist, x); } void insert (link x, link t)

{ t->next = x->next; x->next = t; } link remove(link x)

{ link t = x->next; x->next = t->next; return t; } link next(link x)

{ return x->next; } Item item (link x)

{ return x->item; }

Рисунок 3.11 иллюстрирует разрастание свободного списка по мере удаления узлов в профамме 3.13. Для простоты подразумевается реализация связного списка (без ведущего узла), основанная на индексах массива.

Реализация обобщенного распределителя памяти в среде С++ намного сложнее, чем подразумевают рассмотренные простые примеры, а реализация оператора new в стандартной библиотеке явно не настолько проста, как показано в программе 3.14. Одно из основных различий состоит в том, что функции new приходится обрабатывать запросы распределения области хранения для узлов различного размера - от крохотных до огромных. Для этой цели разработано несколько хитроумных алгоритмов. Другой подход, используемый некоторыми современными системами, состоит в освобождении пользователя от необходимости явно удалять узлы за счет алгоритмов сборки мусора (garbage-collection). Эти алгоритмы автоматически удаляют все узлы, на которые не указывает ни одна ссылка. В этой связи такжр разработано несколько нетривиальных алгор гшов управления областью хранения. Они не будут рассматриваться подробно, поскольку их характеристики быстродействия зависят от свойств определенных компьютеров.

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

012-3 45678

item next

РИСУНОК 3.11 ПРЕДаДВЛЕНИЕ СВЯЗНОГО СПИСКА и СВОБОДНОГО СПИСКА В ВИДЕ МАССИВОВ

Эта версия рис. 3.6 демонстрирует результат поддержки свободного списка с узлами, удаленными из циклического списка. Слева отображен индекс первого узла свободного списка. В конце процесса свободный список представляет собой связный список, содержащий все удаленные элементы. Прослеживая ссылки, начиная с 1, можно наблюдать следующий ряд элементов:29634715. Они следуют в порядке, обратном по отношению тому, в котором элементы удалялись.

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

Упражнения

о 3.46 Написать программу, которая удаляет все узлы связного списка (вызывает операцию delete с указателем).

3.47 Написать программу, которая удаляет узлы связного списка, находящиеся в позициях с номерами, кратными 5.

о 3.48 Написать профамму, которая удаляет узлы в четных позициях связного списка.

3.49 Реализовать интерфейс программы 3.12 с помощью прямого использования операций new и delete в функциях newNode и deleteNode соответственно.

3.50 Эмпирически сравнить времена выполнения функций распределения памяти из профаммы 3.14 с операторами new и delete (см. упражнение 3.49) для профаммы 3.13 при Л/ = 2 и Л= 10\ 10\ 10 и 10

3.51 Реализовать интерфейс профаммы 3.12, используя индексы массива (при отсутствии ведущего узла) вместо указателей таким образом, чтобы рис. 3.11 иллюстрировал операции профаммы.

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

3.53 При соблюдении условий упражнения 3.52 записать фрагмент кода, отыскивающий по данному указателю узла количество различных узлов, которые будут достигнуты, если следовать ссылкам от данного узла. Модификация любых узлов не допускается. Не использовать более некоторого постоянного объема дополнительного просфанства памяти.

3.54 При соблюдении условий упражнения 3.53 записать функцию, которая определяет, окажутся ли в одном цикле две данных ссылки, если их отслеживать.

3.6 Строки

в языке С термин строка (string) обозначает массив символов переменной длины, определяемый начальной точкой и символом заверщения строки. Язык С++ наследует эту структуру данных из С. Кроме того, строки в качестве высокоуровневой абсфакции включены в стандартную библиотеку. В этом разделе приводится несколько примеров строк в стиле С. Ценность строк в качестве низкоуровневых структур данных обусловлена двумя главными причинами. Во-первых, многие вычислительные приложения предусматривают обработку текстовых данных, которые могут представляться непосредственно сфоками. Во-вторых, многие вычислительные системы предоставляют прямой и эффективный доступ к байтам памяти, которые в точности соответствуют символам строк. Таким образом, в подавляющем больщинстве случаев абстракция строк связывает потребности приложения с возможностями компьютера.

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