Cтраница 2
В программе должен использоваться предложенный вами способ представления списков. [16]
Поскольку Хвост - это список, он либо пуст, либо имеет свои собственную голову и хвост. Таким образом, выбранного способа представления списков достаточно для представления списков любой длины. [17]
В главе 3 была введена специальная система обозначений для списков ( специальная прологовская нотация), которую мы и использовали в последующем изложении. Разумеется, это был всего лишь один из способов представления списков на Прологе. [18]
Списки, как и деревья, являются иерархическими структурами, поэтому для обозначения узлов Списка L можно использовать индексные обозначения, принятые при описании древовидных структур. Координатами служат уровни ссылок Списка. Для представления Списков в памяти обычно применяются примерно такие же схемы, как и для представления бинарных деревьев. [19]
Список - это структура данных, которая широко используется в Прологе для самых различных приложений. Примеры из упражнения 3.2 показывают, что с помощью простого предиката, специфицировав внутри цели список особой формы, мы можем отвечать на удивительно разнообразные вопросы. Однако для представления списков, которые мы использовали до сих пор, возникают определенные трудности. Во-первых, пользователю для правильной записи формы списка мешают многочисленные скобки, они же затрудняют интерпретацию списков, возвращаемых программой в качестве результатов. [20]
Изменения в методе состояли бы только в том, что не надо было бы отдельно представлять ключи, однако, потребовалась бы косвенная адресация. В этом случае довольно много внимания пришлось бы уделять представлению списков адресов и работе с ними. [21]
Поэтому определения соответствующих адресных функций и основных операций над Списками получаются из выражений для линейных списков и древовидных структур. Поскольку необходимо различать головы Списка, неатомарные и атомарные узлы, каждый узел обычно содержит поле типа. Помимо указания типа узла, головы Списка могут содержать идентификатор Списка, а также информацию, упрощающую сбор мусора и алгоритмы прохождения. Включение идентификатора Списка в неатомарные узлы соответствует хранению информации в неконцевых узлах дерева. Для обработки данных с переменной длиной блоков можно либо хранить в атомарных узлах информацию о длине блока и типе данных, либо хранить список указателей, описывающий структуру данных, отдельно от списка данных. Универсальность Списков служила причиной создания большого числа систем обработки Списков. В основе этих систем лежит приведенная выше концепция представления Списков. [22]
Связанные списки могут быть представлены с помощью основной для Фортрана структуры данных - вектора. Сначала определяется один большой вектор М, который будет изображать память. Индексы элементов вектора служат в качестве адресов или указателей позиций ( элементов вектора) в этой памяти. Поскольку индексы являются целыми числами, они могут храниться в тех же самых векторах, что и целочисленные данные, содержащиеся в списках; следовательно, вектор М должен иметь тип integer. Теперь связанные списки можно представить, в векторе так, как это предлагается в разд. Таким образом каждый элемент списка занимает в М две последовательные позиции. Это представление иллюстрируется на рис. 3.20. Несмотря на простоту такого представления списков, их невозможно использовать эффективно, если программист не напишет набор подпрограмм для выполнения соответствующих операций над списками и, что более важно, не построит для вектора М систему управления памятью, которая позволит по мере необходимости выделять, возвращать и повторно использовать память во время обработки списка. Несколько методов, с помощью которых можно реализовать эти механизмы, обсуждаются в гл. [23]