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