Лекции (984123), страница 8
Текст из файла (страница 8)
Для доступа к новому началу очереди (при всех последующих извлечениях компонент из очереди) можно было бы после геке!,!д) !п — 1) раз выполнять це$(>1) и после этого х:= д1, где и номер обращения к чтению из очереди (напомним, что чтение из очереди -- разрушающее, прочитанная компонента всегда удаляется). При таком фиктивном удалении необходимо помнить. сколько компонент очереди было удалено ранее и, следовательно, должно быть пропущено при доступе к текущему первому элементу очереди.
Это число и не удается легко агрегировать с файлом, поскольку время жизни файла-очереди, как правило, больше области действия переменной-счетчика удаленных элементов, и существует опасность неправильной интерпретации остак>щихся в начале файла удаленных из очереди компонс>нт. Фактическое исключение прочитанной компоненты можно обеспечить более трудоемким способом, используя вспомогательный локальный файл. В него надо скопировать все компоненты файла;очереди, начиная со второй, с последующей переписьк> из вспомогательного файла обратно в файл-очередь. Про>седура ! ор вь>талк>гв»с>т элемснт из о шреди.
Если надо сохранить извлеченный элемент, необходимо предварительно получить его при помслци функции Тор и помес'тить в локальнук>переменную, ргосес1пге Рор!таг с1: с!пепе); таг с11: с!пепе; !' Локальный рабочий файл для временного хранения копии очереди без первого элемента. Б стиле тезиса «самый маленький файл больше самого большого массива» мы полагаем, что на устройстве внешней палсяти всегда есть место еще для, одного фай.ла ~ Ьеи!п геве$(с1); геитЫе(с!1); 1!' по1 ео!(ч) 1Ьеп пей®; !' Пропускаем первый элеме>ип, если он есть, Будет работать для пустой очереди, но лучше явно проверять пустоту г>редикотол> Бтр$у перед вызовом Рор у 218 ( Копируем остаток очереди с1 (бсэ первого элемента) в оч>средь <11.
Для, 'пуспгой очереди эпгот цикл тоже работает, гг ч<<Ы1е поС еоГ(<1) с1о Ьеи1п <11":-- с1"; рпС(<11): цеС(<1); епс1; ( Копируем скорректироваг<нуго очередь й1 иэ еремеев<ого локаль»<сгго файла, (без первого элеченгпо) назад, впостоянный внеитий, глоба„льнь<й файл, <1 ) гевеС(<11); геччт1Се(<1); и<Ь11е поС ео1(<11) с1о Ьег 1п <1: - <11"; рпС(<1), деС(<11); епс1: епс1; К сожалению, замечательный Вог|апс1 Равса1 (в нарушение стандарта Паскаля!) не реализует процедуры иеС и рпС и эти программы должны бг>гп> переписаны с помощью процедур геас1 гл ч<гг1Се.
Итак, очередь можно отобразить на файл, но для работы с ней потребуются дополнительныс рс.сурсы: во-первых, время на перемотку файла из конца в конец при попеременном выполнении операций В ОЧЕРЕДЬ и ИЗ ОЧЕРЕДИ, во-вторых, память и время на выполнение операции ИЗ ОЧЕРЕДИ. Кроме того, необходимо помнить, что, в отличие от винчес:тера, имеюгцсто воздушнукг смазку гсгловок, реальные магнитнью ленты выдерживают всего несколько сотен перемоток, поскольку головка НМЛ непосредственно контактирует с лентой.
С другой стороны, СП-ССО'»1, использугощий для считывания данных луч лазера, ещс. болес< бесконтактен, чем винчестер. В заключение заметим, что сходс:тво очередей и файлов особенно заметно во франггузском языке: там эти понятия обозначаются одним и тем же словом с1пеие ~72~. Слово файл английского происхождения. 5.4.2.2 Реализация на массиве При реализации очереди на массиве необходимо зафиксир<эвать размер этого массива, ограничив тем самым максимальную длину очереди. В каждый конкретный момент времени очередь будет представлена спгошньл< участком массива.
Введем две индексные переменные: первую --- для индекса начала очереди < «голова»), вторую -- для индекса первого свободного элемента массива после гюследнего элемента очереди <' «хвост»; наш хвост не является частью тела). Рассмотрим три стратегии отображения очереди па массив: ° страгпегия трудоголика: никогда не откладывай на завтра то, что л<ожно слег<ать сегодня. При такой стратегии голова очереди фиксируется на первом элементе массива. Хвост очереди подвижен, поэтому время постановки элемента в очередь постоянно и невелико 1011)). При извлечении элемента из очереди оставшиеся компоненты 219 сдвигаются к началу массива. Именно так ведут себя люди или автомобили, находящиеся в реальных очередях: хотя каждый участник очереди делает только один шаг вперед, цена этой операции для всей о и реди довольно велика и пропорциональна ее длине 0(Ю).
«Применяется: никогда!> (Д. В. Сопшиков). ° при»ециео6 сп>ратегиг> и голова, и хвост о >среди подвижны. Ленивая очередь нс движется до тех пор, пока это возможно, но, если надо, сдвигается по максимуму. Извлечение элемента из очереди занимает постоянное время, т. к. необходимо всего лишь инкрементировать индексную переменную -- головной указатель. Постановка в очередь осуществляется так: если хвост указывает на свободный элемент массива, то туда записывается новая компонента очереди. В противном случае, когда хвост упирается в конец массива, делается попытка воспользоваться свободным местом в начале массива, освобожденным ушедшими из очереди элементами (примитивная сборка мусора).
В случае успеха вся очередь коллируется в начало массива, после чего и происходит собственно добавление элемента. При малой длине очереди, много меньшей размера хлассива> постановка в очеред в среднем занимает постоянное время, т. к. на одно копирование происходит много добавлений. Если же длина очереди близка к размеру массива, то сдвиг происходит почти при каждой постановке в очередь, и время выполнения этой операции приближается к 0(Ж) Щ. Хотя в этой стратегии что-то есть, грамотные программисты ее также не использу>от. ° стран>егия с кольцевым буфером обобща,ет ленивую стратегию. Перемелцения озере; ди в массиве не бывает никогда. Склеивая на тало массива с его концом (с помощью знакомой нам еще со времлн Цезаря опсрашли пгос1, отбрасывающей нас от конца массива к его началу, мы получаем возможность неограниченного поступательного движения вперед по буферу, при условии, конечно, что его элементы так >ке быстро исчезают> как и появляются), По гениальности идея кольцевого буфера может соперничать с предложенными проф.
Жоголевыкл Е. А. в 1958 г. встречными стеками. При использовании кольцевого буфера как только одна из переменных-индексов подходит к концу массива, ее скачкообразно переустанавливают на начало массива, на освобожденное ушедшими из очереди элементами место. При такой стратегии и постановка, и извлечение из очереди занимак>т постоянное и очень неболыпос.
время 0(1) ~59, 54~. В отличие от предыдущих схем кольцевая буферизация является «экологически чистой» и не требует сборки мусора. И сама очередь, и свободная память образуют сплошные куски буферного массива (по модулю л>>), между началохл и концом которых мигрируют освобождаемые и занимаемые элементы. Как видно, из всех стратегий оптимальной является стратегия с кольцевым буфером, поскольку обе операции занимают минимально возможное время. Может быть такая реализация немного сложнее остальных, но ее характеристики, несомненно, того стоят.
Итак, зафиксируем размер массива-буфера и обозначем его РОО?. Я?ХЕ. Пусть в переменной ??гй хранится индекс головы очереди, в переменной и~с — ее длина. Зная это, легко указать на хвост очереди. 220 Заметим, что более очевидная система координат кольцевого буфера /'ггв1 и 1аа1 не была принята нами в связи с невозможностью различить ситуации пустого и до отказа заполненного буферов. Таким образом, тиц очередь представляется в виде комбинированной структуры с полями 11гМ, з1ве и с1а1а.
сопв$ Р001. ЯХЕ = 100: гопМ тХ РО01 Б1/Е= 100; Суре с1пепе -- гесогс1 йгьс: О.. 1'001. ЯХŠ— 1; Ыие: О.. Р001. ЯХЕ; с1аса: аггау(О..Р001. ЯХŠ— Ц оГ Т епс1; Тип переменных 1и"И и вс ге в Паскаль эеализации сделан интервальным вместо це- лого для повышения надежности (как в период компиляции, когда оудут недопустимы константы за пределами указанного диапазона, так и в период выполнения, облегчая скомпилированные проверки принадлежности текущих значений интервалу типа~.
Поскольку очередь реализована на статическом массиве, создание очереди сводится к инициализации параметров доступа к нему. При необходимости действительно динамического создания очереди надо воспользоваться процедурой певуч (или функцией ша11осД). При инициализации очереди необходимо сделать ее пустой, установив в нуль ее размер. Заметим, что начальное значение переменной-индекса головы очереди не обязателыго должно быть нулем: кольцевой буфер может начинаться в любом месте массива.
моЫ Сгеасе(йпепе~ с~) с1 — >йгвс — О; с1 — >ьйге О; Проверка пустоты очс.реди осущсствлястс я путем сравнения ее длины с нулем. Ьоо1 Ешр1у(сопМ с1пепе* с1) геФпгп с1 — >ь1хе -- О; Гппсс1оп Ешр1уТссаг с1: с1пепе): Ьоо1еап; Ьеи1п Еспр1у; с1.а1ие — О; 221 ргосес1пге СгеаГе(айаг с1: с1пепе); Ьеи1п с1. ангес; — О; с1. з1ис: — О; епс1; гурес1с1 вггпсг 1пс Огас: 1пс иие; Т с1а1а(Р001. З1ХЕ(; ) йпепе: епс1; Размер очереди уже хранится в ней в виде отдельной переменной. поэтому достаточно >1игпь вернуть соответствующее значение. ГппсСюп с>1хс(айаг с1; с1пепс): 1НСедег; Ьеи1п В1хе: с1, э1хе; епс1; 1ИС В1хе(11ог18С (1пепеФ 11) ( геСпгп й — >в1гсч; В функциях ЕтпргуД и В1хеД очередь передается по ссылке, с указанием спецификатора маг, стандартного для массивов Паскаля. В Си массивы всегда передаются по ссылке, что изображается символом ~ или Ц. С теоретической точки зрения это нехорошо, т.
к. параметры функции должны быть константами, а единственным результатом такой подпрограммы должно быть ее значение. Описателысаг к тому же и небезопасен: д>1>1 функций, считывающих характеристики очереди, он предоставляет во:зможность модификации всех ее компонент. К счастью, в Си мы можем добавить модификатор доступа сопвС, запретив тем самым всякое изменение компонент очереди. Операция постановки в очередь реализуется функцией двух аргументов Рпв11(), которая возвращает истинпостное значение: Сгпе, если постановка в очередь была проведена успепгно и Са1ве в про"1ивном случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
