Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 159

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 153 154 155 156 157 158 < 159 > 160 161 162 163 164 165 .. 316 >> Следующая

• StateQueue — функция, вырабатывающая значение состояния очереди: Empty (пустая), Full (заполненная) или Normal (нормальная), в зависимости от наличия сохраняемых элементов;
• GetElQueue — функция, вырабатывающая значение элемента очереди и извлекающая элемент из очереди, если состояние очереди (значение, вырабатываемое функцией StateQueue) не Empty, и специальное, выделенное значения типа элемент очереди NotEl в противном случае;
• PutElQueue — процедура, помещающая элемент-параметр в очередь для хране-ния, если это возможно, т.е. когда состояние очереди (значение, вырабатываемое функцией StateQueue) не Full. Если очередь заполнена, то процедура долна выдавать сообение об оибке обра-
ения к ней.
448
ГЛАВА 8. ПОДПРОГРАММЫ
реде, чем приступить к реализации подпрограмм необходимо договориться о том, для хранения каких элементов будет использоваться библиотека. Ограничиваясь иллюстративными целями, будем считать, что очередь предназначена для хранения целочисленных значений, а значение NotEl равно нулю.
Суествует довольно много вариантов реализации очередей, приспособленных для использования в различных режимах. Среди режимов, определяющих выбор конкретного решения, можно указать, с одной стороны, на дисциплину доступа к даннм, когда чередование записи и чтения информации более или менее равномерно, а с другой — на работу большими порциями, при которой череду тся периоды с относительным преобладанием записи с периодами относительно более частого чтения. В первом случае при достаточно большом объеме памяти, отводимой для хранения элементов, ситуации с переполнением очереди явля тся искл чительными, во втором — необходима особая забота об обработке переполнений. а вбор варианта реализации очереди влияет и то, предусматривается или нет реим работ с приоритетами: требуется ли обеспечить возможность пропускания элемента "вперед". Список подобных особенностей использования очередей легко продолжить. Зачастую трудно заранее предвидеть поведение вычислительного процесса, а значит и оптимальну реализаци очереди. менно поэтому весьма елательно явно разделять уровни использования и реализации: если реализация ока ется неудачной, смена ее не повлечет изменение использующей программы.
В приводимой программе используется следуий подход к реализации очередей. Хранилище элементов представляется массивом Container объема MaxSize. Для указания компоненты массива, в которой при очередном обращении к процедуре PutElQueue разместится элемент очереди, используется переменнаяиндекс IB. Элемент, который должен быть извлечен из Container^ при обращении к функции GetElQueue, указывается переменной-индексом IE. Три структуры данных: Container, IB и IE являются основой реализационного представления очереди.
Все храниме элемент очереди размеа тся меду компонентами, индексируемыми IB и IE (см. рис. 8.9a). Запись элемента влечет увеличение индекса IB, а чтение — IE. Если после чтения элемента IE оказывается равным IB , то это означает, что все элементы очереди прочитан (состояние очереди — Empty). Когда в результате записи элемента значения индекса IB достигает своего максимума (MaxSize), то за счет произошедших ранее чтений из очереди в массиве Container может оказаться свободное место в его начале,
8.6. TURBOPASCAL
449
Container
IE
. Свободные участки. Занятый участок
IB
(а) Конфигурация с одним занятым и двумя свободными участками
Container
IE
Занятые участки Свободный участок
IB
(б) Конфигурация с одним свободным и двумя занятыми участками Рис. 8.9. Представление очереди массивом и двумя индексами
450
ГЛАВА 8. ПОДПРОГРАММЫ
которое целесообразно переиспользовать. Это достигается сбрасыванием IB в минимально возможное значение (в примере: IB := 1). Теперь заполнение очереди возмо но до тех пор, пока IB не станет равным IE (см. рис. 8.9б), и, таким образом, состояние заполненности очереди (Full) есть равенство индексов IB и IE после записи элемента.
ри чтении очередного элемента возмо но, что IE указывает на последний элемент массива. Это означает, что после чтения он должен быть установлен на начало Container^. В результате конфигурация занятости массива снова принимает вид, изобра еннй на рис. 8.9а.
агляднее всего описанный процесс мо но представить при помои изо-бра ения массива Container в виде кольца, т. е. склеивая его начало с концом, благодаря чему особые случаи работы с индексами исключаются (см. рис. 8.10). Следует обратить внимание на равенство IE = IB, которое дости-
Рис. 8.10. Hаглядное представление очереди как массива-кольца
гается в двух крайних случаях: когда очередь опустоается и когда она становится заполненной. Это равенство говорит, что очередь находится в одном из состояний: Empty или Full. Какое из них фактически установилось, ясно, если проанализировать, какая из операций GetElQueue или PutElQueue выполнялась последней. нформация об этом сохраняется в переменнх BFull и BEmpty логического типа, которе долны рассматриваться в качестве со-ставляих представления очереди23.
23 Заметим, что можно было не вводить две этих переменных, а вызывать соответствующую реакцию на крайнее состояние в конце каждой из подпрограмм GetElQueue и PutElQueue. Такое использование структурных переходов и реакций формально не противоречит структурному программированию, но затрудняет модификацию программы.
Предыдущая << 1 .. 153 154 155 156 157 158 < 159 > 160 161 162 163 164 165 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100