Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

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

В соответствии со схематичным изображением разветвленных списков типичная структура элемента такого списка в памяти должна быть такой, как показано на рис. 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, если аргумент является подсписком.

<== предыдущая лекция | следующая лекция ==>
Основные понятия. Нелинейные разветвленные списки | Управление динамически выделяемой памятью. Язык программирования LISP
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 262; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.