Операции обработки списков. Представление списковых структур в памяти

Представление списковых структур в памяти

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

data – данные атома

down – указатель на подсписок того же уровня

next – указатель на следующий элемент

Рис. 6.13. Структура элемента разветвленного списка.

Элементы списка могут быть двух видов: атомы, содержащие данные, и узлы, содержащие указатели на подсписки. В атомах не используется поле down элемента списка, а в узлах – поле data. Поэтому логичным является совмещение этих двух полей в одно, как показано на рис. 6.14.

type

data/down

next

Рис. 6.14. Структура элемента разветвленного списка.

Поле type содержат признак атом/узел и может быть однобитовым. Такой формат элемента удобен для списков, атомарная информация которых занимает небольшой объем памяти. В этом случае теряется незначительный объем памяти в элементах списка, для которых не требуется поля data. В общем случае для атомарной информации необходим относительно большой объем памяти. Наиболее распространенный в данной ситуации формат структуры узла представленный на рис. 6.15.

type

down

next

Рис. 6.15. Структура элемента разветвленного списка.

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

Базовыми операциями при обработке списков являются следующие:

1. Операция car в качестве аргумента получает список (указатель на начало списка). Возвращаемым значением является первый элемент этого списка (указатель на первый элемент):

если X = (2,6,4,7), то car(X) = атом 2;

если X = ((1,2),6), то car(X) = (1,2);

если X – атом то операция car(X) не имеет смысла.

2. Операция cdr в качестве аргумента также получает список. Возвращаемым значением является остаток списка – указатель на список после удаления из него первого элемента:

если X = (2,6,4), то cdr(X) = (6,4);

если X = ((1,2),6,5), то cdr(X) = (6,5);

если список X содержит один элемент, то cdr(X) = nil.

3. Операция cons имеет два аргумента: указатель на элемент списка и указатель на список. Операция включает аргумент-элемент в начало аргумента-списка и возвращает указатель на получившийся список:

если X = 2 и Y = (6,4,7), то cons(X,Y) = (2,6,4,7);

если X = (1,2), Y = (6,4,7), то cons(X,Y) = ((1,2),6,4,7).

4. Операция atom выполняет проверку типа элемента списка. Она должна возвращать логическое значение true, если аргумент является атомом или false, если аргумент является подсписком.

Дата добавления: 2014-01-07