Лекции по информатике (984119), страница 26
Текст из файла (страница 26)
7.1.1.1 Модуль абстрактного типа данных очередь В качестве нетривиального примера приведем модуль реализации очереди на кольцевом буфере и программу, сортирунлцую очереди различными методами сортировки от пузырка до быстрой, преломленными не только на последовательности, но и на очереди с их разрушающим чтением. Эта программа импортирует процедуры работы с очередькц в тер- минах которых и написаны все сортировки.
1 файл оиеие.р 7' 1' компилируеп<ся урс — с йиеие,р << 1 Д. Райли, Т.Э. <Куравлева, С.С. Крылов < тпо<1п1е С1пепеа 1ньег1асе; ехрогС С~пепез — (ТЧа1пе, С~пепе, 1н1С, ЕшрСу, Рор„Тор, Рпв1<, Г)1вр1ау, Я1хе); сопвС Х вЂ” И): Суре ТЪ'а1пе -- шСенег; С~пепе =- гесогс1 Г<гв1, Тоьа1: О.. Х; Вос1у: аггау 11..М! оЕ Т<<а1пе епс1; ргосес1пге 1шС(айаг С1: Опепе); 1' инициализировать 7' СппсСюп 1ьшрьуЯ: (~пепе): Ьоо1еап: 1' пусто < 7' ргосе<1иге Рор(ъ<аг ц: С1пе<пе); 1 удалить первьй элемент, з< СппсСюп ТорЯ; С1пеш;): ТЧа1пс; 1' значение первого элемента, 7' ргосе<1пге Рпв1з ~л<аг С1: С1пепе; 'Ч: ТЧа!пс); 1' до<поить элемент, в конец <~ ргосес1пге Г11вр1ауЯ: С1пепе); << раси<:латать содсрэ<сил<ос у СппсСюп Я1хеЯ: фы<е): шСенег; <' ко.личеставо элементов 7' епс1.
то<)п1е С1пепеа нпр1ешенСаг1он; ргосес1пге Еггог(Б: вьг1ну): 1' Внутренняя процедура, не экспортируегася у' Ьенш ~«г1Се1п(8); 1<а11,; еп<1; ргосес1пге 1н11(айаг Ц: <',<пепе)); 1' Внеи<няя процедура, экспортируется через интерфейс модуля у' Ьен1п фТоСа1: — О; С1.Г1гзС:==- 1 епс1; СппсСюп Е<нрьуЩ: С1пспе): Ьоо1еап; Ьенш Ешрьу: С).'Гоьа! - О 370 'о1хе: -- ©Теса! епс1; епс1.
7.1.1.2 Модуль внешних сортировок абстрактного типа данных очередь ~ файл зот1.р 3 3 1' Программный модуль сортировки, импортирующий процедуры работы с очередью. Во всех случаях, кроме быстрой сортпировки, в проиедурах используются две вспомогательные очереди, каждая из каторгах по очереди служитп входнойт'выходной Д. Райли, Т.Э.?Ктуравлева, С,С. Крьлов,~ ргоататп С~Лэ' Яотт: ппрот$ С1пепез; ътаг 1, 1с: денег; с: сЬаг; ТЕЯТ: аггау ~1..31 оГ зст1па(10); С1: С1пепе:, 1' сортпировка ВЫБОРКОЙ э1 ГппсФ1оп М1пЯ: С~пепе): ТЪа1пе; 1' определить минимальный элемента очереди ~ маг ш: ТЧа1пе; Ьеиш тп с- ТорЯ): 1' Минимальный элемент определяется выталкиванием всех компонентп локальной копии очереди ~параметр Я передаетпся по значению!) 3 Рор(ф; 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згуелььзя очередь копгзргзегпьзя, в первую рабочгзго очередь...
зг 1шг (®; ( ... после чего исоользрстсЯ как ьзыходгьаЯ, последовапьельнослпь зг ллзЫ1е поС ЕшрСу1Щ~г!) с1о Ьедш ( Покьз ьтэпь нсотсортпировзанные элельс~пьы 3 ш: — Мпз(СЯ~ф: ( Выбираем минильальный из них у' КешочеЯЩЦ, ОфпоС Ц, ггэ); ( Удал,яем его иэ первой рабочегь очереди, псрепгьсььвая, остальные элементпы во вторую рабочую о ьередь,~ Рггв1гЯ, ш); ( Польещаем минимальный ззлемеит в отсортгьровангзгзю последовательносьпь зг г: — поС г; ( Вспомьзгььтелыььье очереди меняютс,я ро,л,ялзи у' епс1; епс1; ( сортировка ПРОСТОЙ ВСТАВКОЙ у ргосес1пге 1пвегСЯ:Сзиегге; лаг С~1: (~гзеие; Ъ: ТЪа1гге); ( Локальная вспомогательная процедура зг ( переписать в Я1 все элеменгпы СЗ, всгпавив на нужное льесто Г зг Ьеаш 1шС ЯЦ; 1Г ЕпгРСУ(ф СЬеп ( ОчеРедь гьрсгпа, искать льесто всгпавки, не надо зг Рггз1г(Щ, 'лз) е1ае Ьедш гггЬ11е поС Егггрг,у(® с1о Ьедш гс Поиск место, для ее>павки, перебираемъге элементъс очереди переносятся в въгходную очередь СЭ1 11 Тор(ф > Ч СЬеп 1' Найден больший элемент,, вспгавка пе1>ед нимl 1' 1>гезЭс; 1' Л1одули и Э>гхаЭг есть в стандарте ВхЭепсХег1 Разса1 >г РггвЩ1, 1Ьр1®); 1' Поиск продолэ>сается с поэлементъгм пере>совам гсз в ъюдной очереди в с>ъстоднг»о >г Рор(ф; 1' Перенеселасый элемеггт, из вхосЭ>гой очереди удаляется >г епс1; Риз1>Щ1,ЧЭ; 1' В въгходную очередь на найденное место помещается очередной элемент сортируемой носледоватесгьности 3 ъъЬ11е поС 1йгггргу(® с1о Ьедш 1' Копирование остатка входной очереди в въгходную, рабогпаегп и для пустых остатков >г Рггз1>Я1,ТорЯ)); Рор(ф епс1 епс1 епс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':--:--:-- --=-=-=:: -=-::-:-=:--:--::-: —: =::- ==- =- -=-==::=-===:--=- ==-=:- =:- =:--=::=-:=::=-:== =:: -= -:--=:=-:-: ==-::-----::-- =::- -= 3 ~ .
р р СДИЯННЕМ3 ргосес1пге Мег~еЯ1, С12: С~ггеие; айаг Я: Чиегге); 1' Вспомогательная процедура 3 1' слить упорядоченные очереди Я1 и Цр, реву>гьтат дописать в СЭ. >г 1' Я не инициализируется, так что новые элелгенгпы добавляются в конег1 >г Ьедш 1' Синхроннъгй просмотр сливаемьгх очередей пока хотя бы одна из них ие опустеет 1 Мп1е поС ЕпгргуЯ1) апс1 поС ЕгпрСуЯ2) с1о 374 1Г Тор(Сг1) < 'ГорЯ2) СЬеп Ьерп ) Верхугслка первой очереди мегсапие верхгдгикгс второй ) Рссг1г(Сг, ТорЯ1)); 1' Переливаем ее в въсходнуго очередь ) РорЯ1) ) отливая ее из входной ) епс1 е1ие Ьед1п 1' В пропсивгсом случае гсереливаепгся верхушка второй очереди ) Рпв1г®, ТорЯ2)); Рор Щ2) епс1; ) Перелив остатка первой очереди.) жЬ11е поС ЕгаргуЯ1) с1о Ьее1п Рпг1сЯ, ТорЯ1)); Рор Я1) епс1; 1' Перелив остатка вгпорой очереди.) Мп1е поС Егпрсу(С12) с1о Ьед1п Риг1гЯ, ТорЯ2)); Рор(Сг2) епс1 1' Один из згпих двух п,оследних цглклов всегда не въсполняется, гп.
к. соответствуюгцая очередь пустпа по одному из условий завершения основного цикла; если О1 = Сг2 = И, гпо ни один гсз циклов не вътолняется ) епс1; ргосес1пге МесдеЯогс(айаг Сг: Сгиеие): сс въсделяпгь с псгчала, исходной очереди упор ядочегсгсгле подо череди: сливать их погшрно и, щтсоес1гснять результалп вхвосгп выходной очереди.
Когда исходная о середь закончгстся. провстти аиалсггичпуго процедуру с ре тультагпскм и т,. д. до тех пор, пока сея сг'чередь ие станет гупорядоченной. Двухфазная четырехлегсгпочгсая, сортировка, (гсе считая са' сну' — допогсгсггтелтсая ле.нта пуэгсгса для простоты программирования в связи с тем, что чтссегсгсе из очереди разргугиаюгцее ) айаг СгСг: аггау[Ьоо1еап] оГ С1пспе; ~1, С12; С~пепе; Ч: ТЪ'а1ие; а11: Ьоо1еап; Ьее1п : -- Са1ве; ) Переключатель рабочих очередей ) СЯ[1]: — С1; ) ЩЦа1зе):=- Входная очередь 3 1п1С ЯСг[поС 1]); ) ЯСг)С ие):= пусто ) гереаС ) Установление факгпа завершенности процесса соргпировки ) 1Г ЕгпрсуЯЩ]) СЬеп Ьед1п 1:=- поС 1: а11: =- Сгпе 375 епс1 е1ве !'Слияние продолоюаеьпся) а!1: — Га1ве; Ъ' г-- ТорЯЩ]); !' Из раба гей очереди вынимается голова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
