Н. Джехани - Язык Ада (1988) (1160771), страница 24
Текст из файла (страница 24)
Как уже упоминалось, пользователь должен быть очень осторожен при явном освобождении памяти, поскольку эффект ссылки на уже освобожденный объект является непредсказуемым. З.б.2. Мнажество очередей с приоритеГпами Этот пример иллюстрирует пошаговую разработку данных, т. е. использова- ние простых пакетов для создания более сложных. Представим себе операционную систему, в которой планирование заданий осу- ществляется в соответствии с их приоритетами (10 будет наибольшим приорите- том, а 1 — наименьшим). Следующим будет выполняться задание с наивысшим приоритетом. Если существует более чем одно задание с наивысшим приорите- том, то будет выполняться то задание, у которого время ожидания больше.
Каж- дая очередь, связанная с приоритетами, должна хранить 50 заданий. Задания бу- дут добавляться в очередь только после проверки того, что очередь не заполнена до предела. Запрос на следующее задание, которое будет выполняться, делается только в случае, если гарантировано, что существует по крайней мере одна непус- тая очередь. Множество очередей с приоритетами будет реализовано в виде пакета РК1ОК1Т'т' ЯУЕ()ЕБ, спецификация которого приведена ниже. Предполагается, что тип 10В 10 имеется в окружении, в котором описан пакет РК!О- К1ТУ 91)Е()ЕЯ; расйаде РК!ОК1ТУ Я()Е(ЗЕВ Ь !уре РК1ОК1ТУ Ь петя 1)х(ТЕОЕК гапке 1..!О; ргосее(пге А1э(э(Р: !н РК(ОК1Тт'; У: ш ЗОВ 1(э); ргосеппге )х(ЕХТ(Я; ош ЗОВ Нэ); (ппс!!оп Р(Л,(.(Р: !и РК(ОК1Ту) ге!пуп ВОО(.ЕА(Ч; унио!!оп А)хГу' эОВ ге!пуп ВОО(.ЕА(х(; — возвращает ТК()Е, если существует — по крайней мере одно задание, — и РА(.БЕ в противном случае епе( РК1ОК1ТУ О(!Е(ЗЕБ; Пакет РК1ОК1ТУ Я()Е()ЕЯ реализуется с использованием пакета Р!РО (первым вошел — первым вышел), который определяет тип (ШЕ(ЗЕ.
Различные очереди с приоритетами можно реализовать в виде массива с элементами типа (П)Е()Е. Операции над объектами типа 9()Е()Е предусмотрены в пакете Р!РО. Спецификация пакета Р(РО имеет вид рас)саяе Р1РО Ь МАХ о1к,Е: сопзгап! с= 50; "Список свободной памяти можно хранить в теле пакета. Освобождаемые элементы булут добавляться к этому списку. Память иэ этого списка будет использоваться по необходимости.
Генератор пои булет вызываться только в случае, если список пуст. Этот список первоначально пуст. Пакеты гуре ()(ЗЕЫЕ Ь !!шйей рг!гаге; ргосеоиге АРР((): !и опг О(ЗЕ(ЗЕ; 3: !и ЮВ 1Р); ргосег)иге НВБТ(О: !п оп! О(ЗЕ13Е; 3: опг ЗОВ 1Р); — возврашает и удаляет первое — задание в очереди рпга1е 1уре ЮВБ Ь аггау (1..МАХ Б1г.Е) о1 ЮВ 1Р; 1уре Я1ЗЕ()Е Ь гесоЫ Х: ЮВБ; Р1ВБТ, ЬАБТ: 1ХТЕОЕК гапяе 1..МАХ ЯУЕ:= 1; С(ЗК Б1г.Е: 1ХТЕОЕВ галие О..МАХ ЯУЕ:= О; епо гесого; епг) НРО; Значения С(ЗК Б1«.Е в очереди в порядке поступления будут Х(Р)ВБТ), Х(НВБТ шог) МАХ Б1УЕ + 1),...
Тело пакета Р1РО имеет вид рас1сайе Ьопу НРО !в ргосеоиге АРР((): !и оп! О(ЗЕ)ЗЕ; 3: !и ЗОВ РР) Ь Ьерп И Р(ЗЬЬ(О) гпеп Р(ЗТ («ОШИБКА: очередь полна»); ХЕЖ Ь)ХЕ; ге!пгп; — лучшей альтернативой будет — возбуждение исключения, указываюшего — процедуре, вызвавшей процедуру АРР, — что очередь полна и что необходимо — выполнить корректирующие действия; — надежные программы проверяют — ошибочные условия, даже если их — спецификации явно не требуют явной — проверки епд И; О.Х(().ЬАБТ): = 3; ОЛ АБТ:= ЯЛ АБТ шод МАХ Б1УЕ + 1; — операция шоо имеет более высокое старшинство, — чем «+» ОС(Ж Б17Е:= ОС()В Б!гЕ + 1; епо АРР; ргосег)пге НКБТ(Я: !и опг О(ЗЕ(3Е; 3: оп( 3ОВ 1Р) Ь Ьея!п И ЕМРТг'Я) Гйеп Р(3Т («ОШИБКА: очередь пуста»); — смотри комментарии к подпрограмме АРР ХЕ% 1.1ХЕ; ге(пгп; спи И; 114 Глава 3 1:= О.Ха.Р!КВТ); Я.Р1КБТ:= О.НКБТ шоо МАХ 81г.Е+ 1; ()С()К ЯКЕ: = ОС()К.
В)КŠ— 1; епй НКВТ, Еппсйоп НЗЫ,(0: )п 01)Е$3Е) ге(пгп ВОО1.ЕАХ !в Ьей!п ге(пгп ()СОК 51УЕ = МАХ ЯУЕ; епй НЛ 1.; (ппсбоп ЕМРТУ(0: (п ()1)ЕОЕ) гегпгп ВООЬЕАХ !я Ьей)п ге1пгп О.СОК Ях.Е = 0; епд ЕМРТУ; епг! Р!РО; Использование переменной СОК $17Е не является необходимым, так как ее значение можно легко подсчитать исходя из переменных ЯКУТ и 1.АКТ. Однако С(ЗК-512Е повышает понимаемость программы. Используя спецификации пакета ЯРО (т.
е. определенные в нем элементы), тело пакета РК10К1ТУ ()1)ЕОЕ описывается так: раскайе Ьопу РК10К1ТУ 01!Е()ЕЯ !я Р 0: апау (РК1ОК1ТУ) о1 НРО.(НЗЕ~1Е; — 1О очередей для задач с приоритетами; — одна для задач равного приоритета ргосеопге А01)(Р: )п РК10К1ТУ; 3: )п 1ОВ !О) В Ьей!п НРО.А1)О(Р ()(Р), )); епо А)з0; ргосейпге ХЕХТ(Л ош 10В 11)) !я Ьей)п 1ог 1 !п гечегяе РК10К1ТУ !оор — поиск очередей с наивысшим приоритетом !1 по! Р!РО.ЕМРТУ(Р О(1)) ГЬеп Р1РО.Р)КВТ(Р ()(1), 1); ге1пгп; епо !1; епо 1оор; Р(3Т (иОШИБКА: нет заданий»); ХЕРУ ЫХЕ; епо ХЕХТ; 1ппсйоп Р1Л 1.(Р: !п РК1ОК1ТУ) ге!игл ВОО! ЕАХ В Ьей!п гегпгп ЯРО.Н)Ы.(Р О(Р)); епг! НЗЫ.; 1ппс(!оп АХУ УОВ ге(пгп ВО01.ЕАХ Ь вЂ” возвращает ТК()Е, если существует задание — с любым приоритетом, и РА(.БЕ в противном случае Ьей!п !ог 1 !п РК(ОК(ТУ 1оор ззб Пакеты И пег Р(РО.ЕМРТУ(Р О(1)) !пеп гегнгп ТЮЗЕ; епо И; епо 1оор; гегнгп РАББЕ; епо А)чг' ЗОВ; епо РК1ОК)Т'г' Я(ЗЕ(ЗЕБ; Подпрограмму, использующую эти пакеты, можно рассматривать как нечто по- добное следующему: тт11)г ТЕХТ 1О; пзе ТЕХТ 1О; ргосег)пге ОРЕКАТ1НО Бг'БТЕМ 1з — описание типа ЗОВ 11) — спецификация и тело пакета Р1РΠ— спецификация и тело пакета РК1ОК1ТУ ЩЗЕ(ЗЕБ Ьея(п епо ОРЕКАТ1г)О БУБТЕМ; 3.6.3.
Задача о несовпадающих подпоследовательностях ~%1К73, ОЕХ751 Построить последовательность )Ч, состоящую из символьных элементов 1, 2 и 3, такую, чтобы она не содержала смежные одинаковые подпоследовательности. Примерами таких последовательностей могут служить нулевая последовательность, 1, 12, !21 и т.
д. Примерами других последовательностей, являющихся ошибочными или неприемлемыми, могут служить 11, 1211, 1212 и 122. При решении используется порождение последовательностей, таких что 1) порождается только правильная последовательность (ие содержащая смежные одинаковые подпоследовательности); 2) легко (эффектнвнее) проверить, правильная последовательность или нет. Начнем с нулевой последовательности и будем удлинять ее до тех пор, пока не сгенерируем правильную последовательность длины г). Промежуточные последовательности будут удлиняться только после проверки того, что они являются правильными, так как все подпоследовательности правильной последовательности являются правильными.
Если промежуточная последовательность оказалась неправильной, то она будет трансформироваться до тех пор, пока не будет найдена другая правильная последовательность. При использовании этой стратегии порождение (и, следовательно, правильность) многочисленных неправильных последовательностей исключается, что повышает скорость нахождения правильной последовательности длины Х. Для удлинения и преобразования промежуточных последовательностей будут использованы две операции: !!б Глава 3 1. ЕХТЕХР(Я): удлиняет последовательность Б за счет добавления к ней 1. 2.
ХЕХТ(Б): изменяет Я на следующую в лексикографическом порядке последовательность. (Если последний элемент последовательности Я есть 1 или 2, добавить его к 2 или 3 соответственно; если последний элемент есть 3, удалить его и применить процедуру ХЕХТ к укороченной последовательности.) Алгоритм ОЕХЕКАТЕ, порождающий требуемую последовательность, абстрактно определяется так: Начать с нулевой последовательности зги!1е длина последовательности не Х или она не является правильной последовательностью !оор Ы последовательность правильная 1!зеп ЕХТЕХР последовательность е1зе найти ХЕХТ последовательность.
Если ее не существует, то сделать последовательность пустой и выйти епд 1оор; Очевидная стратегия проверки всех подпоследовательностей для определения правильности последовательности является очень неэффективной. Исследование алгоритма ОЕХЕКАТЕ показывает, что новые последовательности получают одним из двух путей: 1) удлинением правильной последовательности Я символом 1, что осуществляется процедурой ЕХТЕХР(Б), или 2) выбором последовательности Я, которая без ее последнего элемента является правильной„и изменение ее последнего элемента посредством операции ХЕХТ(Б). Следовательно, для того чтобы определить правильность новой последовательности, достаточно проверить только те смежные подпоследовательности, которые включают новый (т.
е. последний) элемент. Использование этого факта делает проверку правильности эффективной. Наибольшая подпоследовательность, содержащая последний элемент, которая должна проверяться описанным выше способом, будет содержать половину длины последовательности. Это наблюдение базируется на том факте, что для наибольшей подпоследовательности не существует смежной подпоследовательности равной длины. Функция ЧА1.1Р, проверяющая правильность строки, абстрактно определяется следующим алгоритмом: Пусть Б — это последовательность, которую необходимо проверить Пусть 1 будет О (длина подпоследовательности Я, содержащая последний элемент) згй1!е 1 < половины длины Я !оор Увеличить 1 на 1 Ы подпоследовательность длины 1, содержащая последний элемент Б, равна ее смежной подпоследовательности (пеп ге1цгп ЕА(.ЯЕ епц Ы епй !оор ге!игл ТИ)Е !гаке ты Следующий пакет ЧАЫО БЕ()(ЗЕХСЕ РАСКАОЕ будет использован луре ОЕХЕКАТЕ; раскайе ЧАЫР БЕ()(ЗЕХСЕ РАСКАОЕ !з МАХ Б1УЕ: сопя!вне:= 100; !уре БЕ( (ЗЕХСЕ !я рг)ча!е; Рапсйоп ЬЕХОТН(Б: гп БЕО(ЗЕХСЕ) гегпгп 1ХТЕОЕК; 1впсг!оп ЧАЫ1)(Б: !п БЕО(ЗЕХСЕ) гегвгп ВООЬЕАХ; 1ппс!!оп Х(ЗЬЬ БЕ() ге!вгп БЕ()(ЗЕХСЕ; 1впсйоп 1Б Х(Л Ь(Б: !п БЕО(ЗЕХСЕ) ге!пгп ВОО1.ЕАХ; ргосег)пге ЕХТЕХ(У(Б: !п оп! БЕО(ЗЕХСЕ); ргосейпге ХЕХТ(Б: !п оп! БЕ()(ЗЕХСЕ); ргосейпге РК1ХТ(Б: !п БЕ( (ЗЕХСЕ); — РК1ХТ использует пакет ТЕХТ-1О; — тело этого пакета должно — компилироваться вместе с пакетом ТЕХТ 1О в проце- рг!га!е гуре БЕО(ЗЕХСЕ !в гесогй БЕО: БТК1ХО(1..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
