Лекции (984123), страница 10
Текст из файла (страница 10)
При использовании терминатора специального типа необходимо соответствующим образом переделать функции Сгеа1еО, РгьзЦ) и Вез1гоу(). Функция Рор(), копируя указатель па первый элемент очереди, готовит этот элемент к отсоединению от очереди, переустанавливая соответствующую ссылку на следукнций элемент, с последующим уничтожением отсосдинснной компоненты по копии ссылки. При этом также декрементирустся счетчик элементов очереди. 227 элемекип Г с1. з1хс: - с1. з1хс ! 1; !' Корреклпировка длинъь очереди п.осле успеганоео добавлениЯ элемента, эг 1' Предыдущие два оперогтора инду ктивьього гьрисваивсьььгья сракггьсьчески дшопь наяь следующие по порядку элечегнты (зисе(д,!азу) и зььсс! сь.зьхе) для двух розных упорядочелчных множеств 3 1~пз1ь: -- 1гпе; епс1; епс1; ГппсФ1оп Рор(чнг с1: йпепе): Ьоо1еап; саг р1: Р1сскп! Ьен1п 11'(с1.
багз! с1.!аз!) ФЬеп Рор: — Га1ве !' Очередь пуспьа, извле ьение невозможно Г е1ве Ье4п ь' Очередь непуста эг рь:-- с1. йгзс; !' Копируем ук ватель на начало очереди 3 с1. Йгзг: ср йгзс ".пехс; !' Перемещаем указатель начала очереди на новый первый элемент или на гперминатор, если извлечен единппвенный элемент очереди г Ч. в!хе: -- с1.
в!хе — 1: 1' Корректировка размера очереди 3 с11зрозе(р1); !' Освобождение памяти, Ьоо! Рор(с1ььеьье* с1) 11'(с! — >йгзг — — с! — >1азс) геСпгп !ьь!зсц вФгпс$ 1сеш* р! — с! — >Йгзг; с! — >ЙгзГ, -- с! — >Йгзс — >ссекал; с1 — >з1хе — —. 1гее (р1); ге1пгп ьгпе; занимаемой удаляемым элементом >' Рор:-- Сгпе; епс1; епс1; Как и при реализации очереди на массиве, функция ТорЦ) определена только на непустых очередях.
ГппсС1оп Тор1саг с1: сгпепе): Т; Ьен1п 1г Сс1. 6гэС <> сь1азС) СЬеп Тор: - ар 6гаС ".с1аСа; епс1; Т '1ор1сопвС с1пепс>* с1) ( 1г1сС вЂ” '>6гаг! - с1 — >1ааг) геСпгп с1 — >6геС вЂ” >с1аСа: ъоЫ РеаСгоу1с1пепеэ с1) жЬ11е(!Еп>ргу(с~)) ( вСгпсС 11епм р> — с1 — >6гэС; с1 — >6геС - с1 — >6гаС вЂ” >пехг;; Сгее (р1 ); ) Ггее Сс1 — >6гаС): й — >6гаС =- с1 — >1акг =- О; с1 — >е1хе О: ргосес1пге ВеаСгоу1каг с1: с1пепе); аунг р1: Р1Сеш: Ьен1п и Ы1еСпоС Егпргу1с1)) с1о Ьен1п 1' Или: д.1>гег <'> уЛаяг == пока. терминатор не станет головой очереди г р1: — с1.
6>вС: с1. 6гэС: — ср 6гвг,псхг; с11ароае(р>); 1' Ос>сзобоэ>с>дассм память очередноео элемента оче1>еди >~ епс1; с11эрове1с1. 6гаг ); 1' Уничтожаем пирмлснатор, удаляя о>густосиенну>о очередь >С с1. 6гэС: — ш1; 1 Уни ппоэ>саем ссылки на уничтоженный объект с1.
!акС ь- п11; с1. э1хе: — О; епс1; Эта программа совмещает обход очереди и посещение всех ее элементов с одновременным удалением пройденных компонент. Воспользуемся рекурсивностью определения очереди для ее рекурсивного уничтожения: 228 Для уничтожения очереди надо поочередно удалить все ее элементы, сохраняя в локалыгой перемегшой рг (на мгновение!) перед удалением каждого элемента содержащуюся в пем ссылку на следующий элемент. ргосес1пге Вез1гоу(айаг с1: с1пепе); гулаг р1: Р11еш1 Ьеи1п 1' Упичтосясение очереди сводится к удаллениго первого элемента, и упичтоэмхению осплатка, который гпоэюе являепгся очередьло лг 1' Для остановки рекурсии ~о ис'ле1гпаьпса очередлл установим 'нели'пользуемукэ ссьллку «вперед» из термглнаплора в пл1 лс с1.1азг .пех1: - п11; 1' Эта операция правомерна, т.
к. в очереди есть по крайней мере термивирунпллий элемент, р1:=- с1. 11гзй; ц. Йгз1:== с1. Йгзу .пех14 Йзрозе(р1); К(с1. ангес <'> п11) ФЬеп 1' Условие прекращения рекурс:па; выполнимо, поскольку длина конечна и уменьсллается на 1 при казсдом вьлзове с1лункции лл 1' Здесь процедуре ллеэЬоуО п.одается очередная обезглавленн я очередь лг Рез1хоу(с1); 1 К моменту возврата из всех инициированных удалений подочередей очсредь уничтожег*сл полл*остью, слклзочая. пгерминатор лл ц. 1аз$:=- ш1:, ц.з1яе г 0: епс1; ъоЫ 1леэстоу(цпепе» с1) ( с1 — >1авс — >пех1 -- 0; Мгпс$ 11егп» р1 - с1 — >йгэ1; с1 — >Йгвг — с1 — >бгзс — >пехг; 1гс'с' (1э1 ); 1Г(с1 — >Йгзг) 1лслз1гоу (с1); с1 — >1азг = 0; с1 — >з1ге 0; паптеврасе з1с1 Септр1аСе <с1авв Т, с1авв Сопга1пег с1ецпе<Т> с1авв с1пепе Рекурсивная версия прслгсдуры уничтожения очереди математически прямолинейна (кипячение чайника математиком) и подобна итеративной, но, помимо затрат ресурсов на рекурслию, требует специальных знаний и культуры программирования.
Говоря о логическом описании очереди, нельзя не упомянуть ее реализацию в стандартной библиотеке шаблонов ЯТ1, С-,+ (180,'1ЕС 14882). Как писал Дж. Бзлсус в своей Тьюринговской лекции 120), язык должен иметь небольшое ядро и расширяться за счет изменяемой части -- в данном случае воплощенной в виде библиотечных функций. Ниже приводится фрагмент функциональной спецификации типа очередь из Стандарта С-+ (с. 479--480): Сегпр1аСе <с1авв Т, с1авв Сопгашег> Ьоо1 орегаСог--- (сопвС цпепе<Т, СовСапгег>ес, сопвС с1пепе<Т, СопСа1пет>вь)1 Сегпр1аСе <'с1авв Т, с1авв Сопсашег> Ьоо1 орегаСог<(сопвС йпепе<Т, Сопга1пег>Й, сопвС сгпепе<Т, Согггапгег>Й); Сегпр1аСе <с1авв Т, с1авв Сопсапгег> Ьоо1 орегаСог1- (сопвС Чпепе<Т, Сопга1пег>Й, сопвС с1псэпе<Т, Сопга1пег>Й): Сегпр1аСе <с1авв Т, с1авв Сонг,а1пег> Ьоо1 орегаСог>(сопвС Чпепе<Т, Сопга1пег>Й, сопвС с1пепе<Т, Сопга1пег>Й); Сегпр1аСе <с1авв Т, с1авв Сопга1пег> Ьоо1 орегаСог< — (сопяС с1пепе<Т, Сонга1пег>лСс, сопвС с1пепе<'1', Согэга1псг>ьс): Сегпр1аСе <с1авв Т, с1авв Сопгашег> Ьоо1 орегаСог> (сопвС с1пепс-<Т, Сопга1гэег>ьс, сопнС с1пепе<Т, Согпа1пег>й); Це надо быть знатоком С+ —,, чтобы понять: данное описание полностью соответствует вышеописанной функциональной спецификации.
Теперь рассмотрим пример реверсирования очереди (перестановки элементов в обратном порядке) с использованием вышеописанных функций (благодаря единому интерфейсу различных реализаций очереди программа может быть использована с любой из них): 230 рпЫ1с: ехр11с1С йпепе(сопвС Согэга1пегвс -- Соггга1псэг()); Ьоо1 сэпэргу() сопвС; в1исэ Суре в1ие() сопяС: ге1егенсе,тонг (); сопаг ге1егегюе 1гопг Д сопвС; гегеГс'.псе Ьас1с(); сопвС ге1егепсе 1эаЖ() сопвС1 чоЫ рпз1э(сопвС ча1пе Сурсъс):, чоЫ рор(); ргосес1пге Кечегве(чаг с1: с1пепе); чаг С: Т; 1' В этой локальной эгерелсенной будет храниться очередная голова посэпепенно обезалавливаемой очереди. При Х рекурсивнъсс въазосэах этой процедуръс будет создано эч' экзнлспляров эгпой перемеэспой, причем новизна эгпиго значений будеип, обратна вралсени, их создания,. Исчерпав очередь в эти перелсенные при оэпработке возвратов, мы помеисаелс чоЫ 1Сечегве(сгпепеа с1) 11' (! Еэнргу(сг) ) ( Т С - Тор(с1); Рор(й); 11счсэгве(с1); Рпз1э(с1, С): ) элементам из последовательности экземпляров переменной 1 в очередь у в порядке, обратном их извлечению, поскольку это делается при возвратах из рекурсии з~ Ьен1п 11' поС Е|т~рСу(ц) СЬеп Ьен1п ТоР(с1~; Рор(с~); 1' Реверсируем очередь без очередного первого элемента ~ Кечегве(с1); 1' Возвращаем в очередь элементы, извятые перед входом в рекурсию 3 Рпг1цс~, С); епс1 епс1; Замечание.
Экземпляры переменной С образуют своеобразный временной стек, в который в обратном порядке заносятся головы подочередей. С этим инверсирующим свойством стека мы познакомимся позднее. 5.5 Стек Стековые структуры и дисциплины доступа, нередко встречаются в повседневной жизни. Бюрократ складывает бумаги на стол в пачку своеобразный стек так, что пришедшие первыми документы лежат месяцами, прежде чем выберутся на поверхность...
Пришедший первым уходит последним определяющий принцип такой структуры данных ~49, 63, 59~. Стек — это структура с единственной читающей-записывающей головкой, последовательным достусюм и перазрушающей записью. с1тение из стека, как и у очереди, разрушающее (удаление!). Более строго, стеком называется множество некоторого переменного (возможно, нулевого1 числа данных, па котором выполняются следующие операции: ° пополнение стека новыми данными; ° проверка, определяющая, пуст ли стек; ° просмотр верхнего (самого нового) элемента, если он существует; ° уиичтожение последнего добавленного, но еще не уничтоженного элемента, если он есть.
Другой пример -- пачка книг, из которой легко снимать и класть книгу только сверху. Уровни протоколов ТСР 1Р также принято складывать в стек, закрывая низкоуровневые протоколы высокоуровневыми в строго указанном ссорядке. В информатике стеки используются очень часто. Во-первых, для изучения физических процессов, в которых встречаются настоящие стеки.
Например., при продаже творожных сырков в супермаркете, их удобно подкладывать в охлаждаемый прилавок сверху; сверху их берут и покупатели. В результате, снизу залеживаются оолее старые сырки, срок хранения которых истекает и их приходится выбрасывать ~72~. Пополнение сырков не должно идти слишком часто, так как это не только лишняя работа продавцов, но и транспортные и такелажные расходы. Стек позволит промоделировать и оптимизировать последовательность добавлений и извлечений сырков из стопки; частота покупок в разное время дня может быть определена экспериментально. Более сложная модель может учесть, что некоторые покупатели не берут верхний сырок. Таким образом, чтобы лу ппе организовать работу секции, надо смоделировать поведение одного или нескольких стеков, элементы которых характеризуются предельным сроком хранения.
Полагая известной повременную выборку сырков, надо определить идеальную последовательность пополнения, такую,что: 1. стек никогда, не становится пустым; 2, элементы, находящиеся на дне стека, не остаются в стеке после пределыюй даты; 3, частота пополнения не слишкоь< велика.
Практическое решение представляет некоторый разумный компромисс между этими целями. Стеки весьъ<а полезны при решении различных собственных задач информатики: е синтаксический анализ текста, выполняемый трансляторами с языков высокого уровня, существенно использует стеки; вложенная структура блоков, процедур, выражений и описаний такова, что оъ<ониъличные переменные образуют стек; ° в стеке удобно отводить память под локальные переменные программных единиц блочной структуры; ° выполнение рекурсивной процедуры также организуется с помощью стека; вложенный вызов может породить еще один, который завершается до того, как управление возвращается на породивший его уровень.
В данном случае в стек откладываются копии множеств локальных переменных предыдущих незавершенных вызовов одной и той же процедуры; ° некоторые ЭВМ (Впгго«ф<а, Эльбрус, 1С1.), микропроцессоры (многие), калькуляторы и языки программирования имеют существенно стековую архитектуру; другие только обеспечивают программную (шаблон эЫ:э1ас1 в С вЂ” —:) или аппаратную поддержку стеков (ЭВМ РГ)Р, ЧАХ и другие). Машины со стековой нуль-адресной системой команд имеют в 3--4 раза более короткие программы за счет экономии на адресах операндов, почти как и у наиболее изощренных представителей С1ЯС архитектур ~ЪЛХ), в сочетании с простотой К1ЯС процессоров. Это же свойство стековой архитектуры позволило успешно использовать язык ФОРТ для програълмирования самых примитивных и маломощных микропроцессоров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
