Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Очереди





Интересным применением разностных списков является организация очередей. Очередь – структура данных для хранения списков, используемая по принципу: «первым записан – первым считан». Голова разностного списка представляет начало очереди, хвост – ее конец, а объекты разностного списка – это элементы очереди. Очередь пуста, если пуст разностный список, т.е. голова и хвост тождественны.

Управление очередью отличается от управления описанным выше справочником. Рассмотрим отношение queue(S), предназначенное для обработки потока команд, представленных списком S. Существуют две основные операции с очередью – включение элемента в очередь и исключение элемента из очереди, представляемые структурами enqueue(X) и dequeue(X) соответственно, где Х –интересующий нас элемент.

В программе 15.11 эти операции реализуются абстрактно. Предикат queue (S) обращается к предикату queue (S,Q), где Q – первоначально пустая очередь. Предикат queue/2 является интерпретатором для потока команд включения и исключения. Он воспринимает каждую команду и соответственно изменяет состояние очереди. При включенииэлемента используется незаполненность хвоста очереди; производится конкретизацияего новым элементом и соответствующее обновление хвоста очереди. Понятно, что отношения enqueue и dequeue могут быть и неразвернутыми, что дает более выразительную и эффективную, однако более трудную для чтения программу.

queue(S) ¬

S – последовательность операций включения элементов в очередь и исключения элементов из очереди, представленных списком термов enqueue (Х) и dequeue(X).

queue(S) ¬ queue(S,Q\Q).

queue([enqueue(X)|Xs],Q) ¬

enqueue(X,Q,Q1),queue(Xs,Q1).

queue([dequeue(X)|Xs],Q) ¬

dequeue(X,Q,Ql),queue(Xs,Ql).

queuc([ ],Q).

enqueue(X.Qh\[X|Qt],Qh\Qt).

dequeue[X,[X | Qh]\Qt,Qh\Qt).

Программа 15.11. Выполнение операций над очередью.

 

Выполнение программы завершается, когда исчерпывается поток команд. Эта программа может быть расширена так, чтобы после выполнения последней команды очередь становилась пустой; для этого один базисный факт можно заменить следующим предложением:



queue([ ].Q) ¬ empty(Q).

Очередь пуста, если ее голова и хвост конкретизируются пустыми списками, выраженными фактом empty([ ] \[ ]). Логически для этого должно быть достаточно предложения empty (Х\Х). однако из-за отсутствия в Прологе контроля на вхождение, рассмотренного в гл. 4, оно может быть удовлетворено ошибочно на непустой очереди, образующей некоторую циклическую структуру данных.

Продемонстрируем использование очередей для раскрытия списка в программе 15.12. Хотя этот пример до некоторой степени надуманный, он ясно показывает, как могут быть использованы очереди.

flatten (Xs,Ys) ¬

Ys – раскрытый список, содержащий элементы из списка Xs.

flatten(Xs,Ys) ¬ flatten_q(Xs,Qs\Qs,Ys).

flatten_q([X Xs],Ps\[Xs| Qs],Ys) ¬

flatten_q(X.Ps\Qs.Ys),flatten_q(X,[Q| Ps]\Qs,[X! Ys]) ¬

constant(X).X ¹ [ ],flatten_q(Q,Ps\Qs,Ys).

flatten._q([ ].[Q | Ps] \Qs,Ys) ¬

flatten q(Q.Ps\Qs,Ys).

flatten„q([ ].[ ]\[ ],[ ]).

Программа 15.12. Программа раскрытия списка с использованием очереди.

 

Основное отношение в программе flatten_q(Ls,Q,Xs), где Ls – список списков, подлежащий раскрытию, Q – очередь списков, ожидающих раскрытия, и Xs – список элементов в Ls. Первое предложение flatten/3 посредством отношения flatten/2 инициализирует пустую очередь. Базовой операцией являются включение в очередь хвоста списка и рекурсивное раскрытие головы списка:

flatten. q([X|Xs].Q,Ys) ¬enqueue(Xs,Q,Ql),flatten_q(X,Ql,Ys).

Явно pacкрывая отношение enqueue получим

flatten_q([X | Xs],Qh\ [Xs | Qt].Ans)¬

flatten_q(X.Qh\Qt,Ys).

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

flatten_q(X,[Q|Qh] \Qt,[X | Ys]) ¬ constant(X).X ¹ [ ],flatten_q(Q,Qh \,Qt,Ys).

Когда при раскрытии встречается пустой список, либо верхний элемент исключается из очереди

flatten_q([ ].[Q | Qh],Qt,Ys) ¬ flatten_q(Q,Qh\Qt,Ys),

либо очередь оказывается пустой, и вычисления прекращаются.

Рассмотрим операционный смысл программы 15.11. В процессе предполагаемого использования очереди сообщения enqueue (X) передаются с определенными X, а deqiieue(X) – c неопределенными X. Пока в очередь включено больше элементов, чем из нее исключено, очередь ведет себя нормально; разность между головой очереди и ее хвостом дает элементы, содержащиеся в очереди. Однако, если число полученных команд исключения из очереди превышает число команд включения элементов в очередь, происходит интересное явление – содержимое очереди становится «отрицательным». Голова опережает хвост очереди, что приводит к появлению в очереди отрицательной последовательности неопределенных элементов.

Число таких элементов определяется числом избыточных операций исключения из очереди.

Интересно понаблюдать, как такое поведение согласуется с ассоциативностью присоединения разностных списков. Если очередь Qs\[X1,X2,X3\ Qs], содержащая три неопределенных отрицательных элемента, присоединяется к очереди [а,b,c,d,e\Xs]\Xs, состоящей из пяти элементов, то результатом присоединения будет очередь [d,e\Xs]\Xs с двумя элементами, где отрицательные элементы Х1,Х2,ХЗ инфицируются с а,b,с.

 





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


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



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

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