тельный узел, который называется заголовком Списка, поэтому конфигурацию (6) можно представить, например таким образом:

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

В исходной схеме (6) узел с элементом b является атомом, а узел с элементом / - пустым Списком. Эти два объекта структурно идентичны, поэтому читатель может вполне резонно возразить: "А зачем вообще нужно было упоминать об ато.мах?". Без утраты общности можно было бы определить Список всего лишь как "конечную последовательность атомов или Списков, число которых может быть больше нуля или равно нулю" с обычным соглашением о том, что в каждом узле Списка могут, помимо структурной информации, содержаться данные. Эта точка зрения вполне оправданна, а потому понятие "атом" представляется весьма искусственным. Однако для решения проблемы эффективного использования памяти компьютера было бы разумно выделить именно атомы, так как они не подвергаются тем универсальным операциям, которые желательно использовать для обработки Списков. Можно заметить, что в представлении наподобие (6) в каждом узле-атоме Ь содержится больше места для данных, чем в узле-Списке /. Кроме того, при использовании заголовков Списков в представлении наподобие (7) для узлов Ь и / предъявляются совершенно разные требования к памяти. Таким образом, концепция атомов вводится только для организации эффективного использования памяти компьютера. В типичных Списках содержится гораздо больше атомов, чем в приведенных здесь примерах. Примеры (4)-(7) даны лишь для того, чтобы продемонстрировать возможные усложнения данной схемы, а не присущую ей простоту.

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

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

Здесь LLINK используется для левого указателя в дважды связанном списке. Поля INFO и DLINK одинаковы для всех трех типов списков.

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

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

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

а) Однословный формат, в котором все данные (INFO) содержатся в следующих атомах:

RLINK

s: т:

Знак (сокращение от слова "sign"), т. е. маркировочный бит, используемый при сборке мусора (см. ниже)

Тип (сокращение от слова "type"), т. е. т = О для заголовка Списка, т = .1 для элемента подСписка и т > 1 - для атомов

REF: Если Т = О, то REF - счетчик ссылок (см. ниже); если Т = 1, то REF указывает на заголовок Списка рассматриваемого подСписка; если Т > 1, то REF у{![азывает на узел, в котором содержатся маркировочный бит и 5 байт атомарной информации

RLINK: Указатели, используемые в обычном или циклическом списке (8) Ь) Двухсловный формат:

(10)

S, Т: To же, что в (9)

LLINK, RLINK: Обычные указатели, которые используются в дважды связанных списках (8)

INFO: Полное слово с данными узла; в узле-заголовке оно может со-

держать счетчик ссылок; текущий указатель на внутренний компонент Списка, используемый для упрощения линейного обхода Списка; символьное имя и т. д. Если Т = 1, то в нем содержится также поле DLINK

3) Ясно, что Списки представляют собой структуры очень общего типа. Действительио, по-видимому совершенно справедливо утверждение о том, что любую структуру, какой бы она ни была, можно представить в виде Списка, учитывая соответствующие соглашения. Благодаря такой универсальности Списков для упрощения работы с ними было разработано множество систем программирования. Причем для компьютера практически любого типа обычно существует сразу несколько таких систем. Они основаны на универсальном формате узлов, например на таком, как показано выше, на схемах (9) и (10), которые созданы специально для более гибкой организации операций со Списками. На самом деле ясно, что обычно такой универсальный формат - не самое лучшее решение какой-либо конкретной проблемы, поэтому универсальные программы выполняются значительно медленнее, чем система с настройками для конкретной задачи. Например, легко видеть, что если бы мы использовали универсальное представление Списка типа (9) или (10) практически во всех приложениях, с которыми нам приходилось работать до сих пор в этой главе, вместо принятого в них формата узлов, это существенно усложнило бы их код. Часто при обработке узлов Списка необходимо проверять содержимое поля Т, что не требовалось в любой из перечисленных выше программ. Эта потеря эффективности при использовании универсальной системы во многих случаях компенсируется сравнительной простотой программирования и сокращением времени отладки.

4) Существует также чрезвычайно важное различие между алгоритмами обработки Списков и алгоритмами, приведенными выше в этой главе. Так как один Список может содержаться сразу в нескольких Списках, совершенно неясно, когда его следует вернуть в пул свободной памяти. До сих пор в наших алгоритмах всякий раз, когда узел NODE(X) уже не был нужен, упоминалась команда "AVAIL <=Х". Но поскольку во время работы Списки общего типа могут генерироваться и здалять-ся совершенно непредсказуемым образом, то часто очень трудно сказать, когда > зел