Лекции, страница 9

Единственная причина, по которой функция Рпв1>[) может вернуть Га1ве попытка записать в массив с1аСа элементов больцсе, чем его размер РООЕ ИЛЕ, Теперь вспомним о /'1 гвС. Запись новой компоненты в массив кольцевого буфера производится в свободный элемент, индекс которого вычисляется по формуле ( 1'ггвС+ вг с) пюс1 РООЕ ЫУЕ, происходит так, что выхода за границу массива не возникает. Поскольку Операция взятия Остатка От деления Однознспнсо Опрсщелсна ли1пь лля и('Отрицательных чисс л (подробнее см. [76[), то ~ггвС должен быть неотрицате:1ьным числом. 222 ГппсСюп Рпв11(1гаг ц: 11попе; С: Т): Ьоо1еап; Ьец1п ъ 1С11 с1 с1о Ьеи1п 1' Если буфер полон, вставка исвозмоо1Сна >1 11 ( в>хе -- РОО1 В1ХЕ) СЬеп Рпэ11: — Га1ве е1ве Ьеи1п 1' Операиия тос1 обеспечивает закольиовавносгаь буфера 7' 11аСа[( Йгвс -1 в>хе) птос1 РОО1 В1ХЕ[: = С; в1хе: = э1хе —, 1; Рпв11: == Сгпе епс1 епс1 Ьоо! Рпв11(с1пепе* с1, сопэС Т 1) 11'(с1 — >в1хе -- РОО!.

В1ХЕ) геСпгп 1а1ве; О Оператор взятия остатка % обеспечивает закольцованность буфера ц — >с1аСа[(с1 — >11гэг + с1 — >э1хе++) % РООЬ В1ХЕ~ -- С; геСпгп ггпе: епс1; Операция извлечения из очереди Рор также возвращает истинностное значение., указывающее на, успех операции. Единственная причина неуспеха это отсутствие комгюнент в очереди. После успешного применения этой операции переменная 1сгаС принимает некоторос значение из полуинтсрвала [О:, Р001. ЯХЕ). Первый элемент очереди доступен, если очередь непуста.

Функция Тор проверяет непустоту очереди и возвращает ее первый элемент, если он есть. В противном случае значение функции Тор не определено. Эта операция может быть применена в любой момент, когда очередь непуста.. Чтобы гарантировать отсутствие ошибок, СйаС должен находиться в полуинтсрвалс [О:, Р001. В1ХЕ). Д В ВТ1. такая функция называется 1гопС 0 Т Тор[сопвс с1пепеа с1) ( 1Г[с1 — >Яхе) геСпгп с1 — >с1аСа[с1 — >бгаС!; ГппсСюп Тор[лаг с1: цпепс): Т; Ьенш 1Г[с1. яхе с> 0) СЬеп Тор: — с1,с1аСа[с1, вегас ); епс1; Теперь вернемся к вопросу о начальном значений переменной 1ггвС. Функции Рпв1с Д и Роро с целью обеспечения корректности применения мультипликативной операции шос1 ограничивают 1сгвС неотрицательными значениями.

Поскольку. ТорД не производит никаких проверок, то возникает более строгое ограничение: ~и М Е [О; РООЕ Я1ХЕ), т. е. начальные значения переменной должны быть в этом диапазоне. В отличие от описанного ранее типа вектор и типа список, который будет описан позже, специалыю уничтожать очередь на статическом гиассиве не требуется, и эта функция ничего не делает. 11о если возникнет потребность перейти от очереди на массиве к очереди на динамических структурах [в том числе к очереди на динамическом массиве), которую ГппсСюп Рор[чаг ц: с1пепс): Ьоо1еап; Ьенш в 1СЬ с1 с1о Ьен1п 1С'[яхе - 0) СЬеп Рор: Са1ве е1ве Ьенш Йгв1,::=- [ ЙгэС, 1) пюс1 Р001.

В1ХЕ; яхе:-- яхе — 1; Рор: — Сгпе; епс1; епс1; епс1; Ьоо1 Рор[с1пепе~ с1) ( 11 [! с1 — >яхе) геСпгп 1а1эе: с1 — >бгвС вЂ” , '+; с1 — >6ГЯС %-- РООЕ В1ХЕ:, с1 — >яхе — —. 7 геСпгп 1,гпе: необходимо специально упичтожатгь возвращая память ОС, то нс придется дслгисывать уничтожение очередей в конец каждого блока, где эта очередь появилась. Эта унификация полезна и при обратном переходе к очереди на массиве. ъон1 Пеаггоу(с!пене«с!) ( 1тооы воспрепятствовать использованию уничтоженной очереди, можно положить с! — > эьзе =-- О; ргосес1пге Веэггоу(сгаг с1: с!пепе); Ьеи1п ! гпюбы Вос73реплгггсгпезооагпь использооагиио уничгпо:исенной очереди, л«озюио полоэссить о.зие :-О;3 епс1; Поскольку очередь 1>еализована на статическом массиве, нет возможности вернуть ресурсы, занимаемые ею.

Можно очистить уничтожаемую очередь от элементов, установив з»эе равным О. 5.4.2.3 Реализация на динамических структурах Свяжем ссылками одиночные элементы очереди в цепочку в том порядке, в котором они должны находиться в очереди. Для этого заведем комбинированный тип «элемент очереди», где наряду с полем данных предусмотрим переменную-ссылку на следующий элемент того же типа.

Обратите внимание на рекурсивность соответствующего описани;я. Она позволяет задавать самоподобпые (фрактальные) структуры, части которых имеют тот же самый тип. Заметим, что рекурсивные описания в Паскале должны быть помещены в одном предложении Суре. Суре 1!еш гесогс1 с!а!а: Т: пехС: Р1Сеш; епс1; Р1г,егн 1Сегп; эСгпсС 1Сегп Т с!ага; вСгпсС 1ге1п пех!л 224 Реализуем тип очередь на динамических структурах. Во-первых, понадобится ссылка, на начало очереди. Чтобы обеспечить выполнение операции постановки в очередь за постоянное время, необходимо дополнительно завести ссылку на, конец очереди, В противном случае цсна вставки элемента в очередь повышается до неприемлемого 0(Х). Чтобы удешевить подсчет длины очереди с 0(Х) до О(1) применим неклассический подход, включив в представление очереди переменную егере длину очереди; актуализация ее значения возлагается на операции модификации.

При реализации очереди на массиве хвост указывал на первый свободный элемент массива за концол«очереди. Здесь мы поступим аналогично, введя пустой служебный элемент — пгериинагпор. Для его хранения потребуется дополнительный элемент, но это оправдано простотой реализаций всех функций для работы с очередью. Терминатор очереди не хранит никакого значения и не может быть прочитан из очереди либо разыменован для получения хранимого элемента. Поэтому важен не сам терминатор, а ссылка на него, которая завершает очередь.

Необходимо заметить, что графическая иллн)страция структур данных является особенно полезной для динамических ссылочных объектов. При этом ссылки изображаются стрелками, связывающими ссылочные персменные и указуемые значения. Сами ссылочные переменные изображаются малыми прямоугольниками, из которых исходят стрелки. Указуемые объекты изображаются более крупными прямоугольниками, обычно разграфленными на поля компонент. Стрелки для пустых ссылок загибаются вниз и заканчиван)тся знаками заземления. Суре с1пепе -- гесогс1 ))гэС: Р1Се)п; !авС: Р1Се)п; э1))е: шСеиег; епс1; Сурес1еГ вСгнсС вСгпсС 1Сстп* йгэС:, вСгпсС 1Сепи 1аэС; 1пС э!ее; ) с1пене:, Функция создания очереди выделяет память под терминирунпций элемент. Правоассоциативность оператора, присваивания в Си, и тот факт, что этот оператор возвращает ссылку-синоним типа 'ГЙ, позволяс)т записать вен) инициализацин) ~дней строкой.

225 Замечание. Непроизводительные затраты на терминатор могут быть существенными, если размер элемента типа, достаточно велик (очередь матриц на транспонирование), В этом случае отказыван)тся от представления терминатора тем же типом, что и элементы очереди, и описыван)т его специальным типом, единственным требованием к которому является ненулевая длина (т. к.

невозможно разместить в памяти объект нулевой длины). При этом придется отказаться от типизированных указателей, поскольку они не позволяют ссылаться на элементы разных типов. Бестиповый указатель пехС, в зависимости от положения в очереди, будет указывать либо на ее элемент, либо на терминатор. Более совершенное решение, используемое, в частности, в ЯТ1,, будет описано в разделе, посвященном полиморфизму. Теперь опишем тип данных лля очереди на динамических структурах. Ввиду динамизма этой цепной структуры фиксируются только начальная и конечная ссылки. Конкретная конфигурация очереди всякий раз должна интерпретироваться относительно этих указателей. Поскольку длина очереди на динамических структурах потенциально бес)сонечна и нс имеет явного ограничения, в качестве типа данных для ее размера эгве взят шСеиег.

Любители защитного программирования должны описать тип сагс1гпа1 = 0..МАХ1МТ для переменной иы. В отличие от очереди на масс:иве это действительно ссгздоние очереди, а не просто инициализация статической структуры. чоЫ Сгеаге(цпепе* с1) й — >ага! — й — >1авг — ггла!!ос(в1хеоГ( вСгпсС !Сопл))! с! — >в!хе О; ргосес1пге Сгеаге(лсаг с1: с!пепе); Ьед1п пеи (с1.11гвС); Ф |авг: — с1. Йгвг; с1.

в1хе: О; епс1; Если головой очереди является терминатор, то она пуста, хотя в данной реализации это можно также проверить сравнением размера очереди с нулем. ГппсС1оп Елпрсу(ъаг с1: с!пепе): Ьоо1еап:, Ьеиш Елпргу:-- с1.11гвС -- с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авС вЂ” >пехС -- лпа11ос( в1хеоК(вСгнсС 11епл)))) геСпгп 1а1ве; с! — >1авс — >с1аса — С: с! — >1авС =- с! — =1авг — >пехС; с! — ';= в!хе-:+; геСпгп Сгпе; Возврат булевского значения функции РььзььΠ— чистая прагматика, попытка реального программирования. В теории Ргьз1ь() должен аварийно завершать программу нри нехватке памяти в куче.

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