Алгоритмы - построение и анализ (1021735), страница 51
Текст из файла (страница 51)
Если 1ор [о] = О, то стек не содержит ни одного элемента и является иусясьсм (ешр1у). Протестировать стек на наличие в нем элементов можно с помощью операции-запроса Зтлск Ем рту. Если элемент снимается с пустого стека, говорят, что он опустошается (шЫегйо)ч), что обычно приводит к ошибке. Если значение 1ор [о] больше св, то стек переполняется (очегбочс). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.) Каждую операцию над стеком можно легко реализовать несколькими строками кода: Ятлск Емртч(о) 1 И 1ор[Я] = 0 2 Феп гегпгп ткне 3 е1зе гегигп РЛ).ЗН Р))зн(Я, х) 1 1ор[Я] — гор[о] + 1 2 5[1ор[о]] с — х РОР(Я) Ы Бтлск Емктч(Я) 2 1Ьеп еггог "шн1е21)о5ч" 3 е!зе 1ор[о] — 1ор[Я] — 1 4 ге1цгп Я[1ор[Я] + Ц Из рис. 10.1 видно, какое воздействие на стек оказывают модифицирующие операции Р))зн и Рок Элементы стека находятся только в тех позициях массива, которые отмечены светло-серым цветом.
В части а рисунка изображен стек Я, состоящий из 4 элементов. На вершине стека находится элемент 9. В части б представлен этот же стек после вызова процедур Р))эн(Я, 17) и Ризи(о, 3), а в части в — после вызова процедуры РОР(Я), которая возвращает помещенное в стек последним значение 3.
Несмотря на то, что элемент 3 все еще показан в массиве, Часть 111. Структуры данныи 262 он больше не принадлежит стеку; теперь на вершине стека — 17. Любая из трех описанных операций со стеком выполняется в течение времени О (1). Очереди Применительно к очередям операция вставки называется Еьк2инпн (поместить в очередь), а операция удаления — 13ЕОцН~Е (вывести из очереди). Подобно стековой операции Рог, операция ПнСя3ниа не требует передачи элемента массива в виде аргумента. Благодаря свойству Р1РО очередь подобна, например, живой очереди к врачу в поликлинике. У нее имеется голова ()ьеас1) и хвосиг (1а(1).
Когда элемент ставится в очередь, он занимает место в ее хвосте, точно так же, ках человек занимает очередь последним, чтобы попасть на прием к врачу. Из очереди всегда выводится элемент, который находится в ее головной части аналогично тому, как в кабинет врача всегда заходит больной, который ждал долыле всех. На рис.
10.2 показан один из способов, который позволяет с помощью массива Я [1..п] реализовать очередь, состоящую не более чем из и — 1 элементов. Эта очередь обладает атрибутом ЬеаИ Я], который является индексом головногс элемента нли указателем на него; атрибут 1а11 [ф] индексирует местоположение, куда будет добавлен новый элемент. Элементы очереди расположены в ячейках Ьеад [ф, Ьеад [Я] + 1,..., 1а11 [Я вЂ” 1, которые циклически замкнуты в том смысле, что ячейка 1 следует сразу же после ячейки и в циклическом порядке.
При выполнении условия Ьеад Я = га11 [Я] очередь пуста. Изначально выполняется соотношение ЬеаН [Я] = 1аь1 [1~] = 1. Если очередь пустая, то при попытке удалить из нее элемент происходит ошибка опустошения. Если ЬеаН [Я] = 1аЫ (Я]+1, то очередь заполнена, и попытка добавить в нее элемент приводит к ее переполнению. В наших процедурах Еьк2ияин и 13н0инцн проверка ошибок опустошения и переполнения не производится. (В упражнении 10.1-4 предлагается добавить в процедуры соответствующий код.) Еыя1/еые(Я, х) 1 ф8а11Ц]] - х 2 !Г та11[ф = 1епдй[ф 3 Феп 1аг٠— 1 4 еИе 8ат1[Я] — 1атЩ+ 1 1)нО~зн~/н(Я) 1 х — Я [Ьеад [Я]] 2 Ы Ьеай[ф = 1епрЯф 3 Фев ЬеаН[Я] — 1 4 е1яе Ьеш٠— Ьеай[ф + 1 5 ге1пгв х Глава 10. Элементарные структуры данных 263 ь ~ 9 0 ~~~~3~~4й~~~~6~('-'[! [ " ) ' [ '~[[![[ 3 а ~ с 7 1 9 Р ;си'~0~= 3 зем ~р)-- з Рис.
10.2. Очередь, реализованная с помощью массива ьГ [1..12) На рис. 10.2 показана работа процедур Еноинон и Рноивнв. Элементы очереди содержатся только в светло-серых ячейках. В части а рисунка изображена очередь, состоящая из пяти элементов, расположенных в ячейках Я [7..1Ц. В части б показана эта же очередь после вызова процедур Енопеок© 17), Емоиник(Я, 3) и Енооннн(Я, 6), а в части в — конфигурация очереди после вызова процедуры 13нФнонф), возвращающей значение ключа 15, которое до этого находилось в голове очереди.
Значение ключа новой головы очереди равно 6. Каждая операция выполняется в течение времени О (1). Упражнения 10.1-1. Используя в качестве модели рис. 10.1, проиллюстрируйте результат воздействия на изначально пустой стек о, хранящийся в массиве Я [1..6), операций Рабан(о, 4), Ризи(Я, 1), Ризн(Я, 3), Рор(Я), Рази(Я, 8) н Рор(Я). 10.1-2. Объясните, как с помощью одного массива А [1.л] можно реализовать два стека таким образом, чтобы ни один из них не переполнялся, пока суммарное количество элементов в обоих стеках не достигнет и. Операции Рахн и Рор должны выполняться в течение времени О (1).
10.1-3. Используя в качестве модели рнс. 10.2, проиллюстрируйте результат воздействия на изначально пустую очередь Я, хранящуюся в массиве Я [1..6[, операций Ен0жннн(Я,4), Единя(Я,1), ЕжНжин(Я,З), 13нОнене(Я), Еьк2нене© 8) и 13еЯнеое(Я). Часть 111. Структуры данных 10.1-4. Перепишите код процедур Еьк)пнзв и 1)в0гжцн таким образом, чтобы они обнаруживали ошибки опустошения и переполнения. 10.1-5. При работе со стеком элементы можно добавлять в него и извлекать из него только с одного конца. Очередь позволяет добавлять элементы с одного конца, а извлекать — с другого. Очередь с двусторонним достулам, или дек (деопе), предоставляет возможность производить вставку и удаление с обоих концов. Напишите четыре процедуры, выполняющиеся в течение времени О (1) и позволяющие вставлять и удалять элементы с обоих концов дека, реализованного с помощью массива.
10.1-6. Покажите, как реализовать очередь с помощью двух стеков. Проанализируйте время работы операций, которые выполняются с ее элементами. 10.1-7. Покажите, как реализовать стек с помощью двух очередей. Проанализируйте время работы операций, которые выполняются с его элементами. 10.2 Связанные списки Связанный список (1ш!геб 1!з1) — это структура данных, в которой объекты расположены в линейном порядке. Однако, в отличие от массива, в котором этот порядок определяется индексами, порядок в связанном списке определяется указателями на каждый объект. Связанные списки обеспечивают простое и гибкое представление динамических множеств и поддерживают все операции (возможно, недостаточно эффективно), перечисленные на стр.
257. Как показано на рис. 10.3, каждый элемент дважды связанного списка (бопЫу йп!сес1 1!з!) Ь вЂ” это объект с одним полем ключа кер и двумя полями-указателями: пех! (следующий) и ргеп (предыдущий). Этот объект может также содержать другие сопутствующие данные.
Для заданного элемента списка х указатель пехЬ [х] указывает на следующий элемент связанного списка, а указатель ргее [х] — на предыдущий. Если ртеи [х] = и!!., у элемента х нет предшественника, и, следовательно, он является первым, т.е. головным в списке. Если пех! [х] = мп., то у элемента х нет последующего, поэтому он является последним, т.е. хвостовым в списке. Атрибут Ьеаа [з ] указывает на первый элемент списка. Если йеаа [з ] = = мп., то список пуст. Списки могут быть разных видов. Список может быть однократно или дважды связанным, отсортированным или неотсортированным, кольцевым или некольцевым.
Если список однократно связанный (однонаправленный) (з!пя1у 1ш1сед), то указатель ргео в его элементах отсутствует. Если список отсортирован (зог!ед), то его линейный порядок соответствует линейному порядку его ключей; в этом случае минимальный элемент находится в голове списка, а максимальный — в его хвосте. Если же список не отсортирован, то его элементы могут располагаться в произвольном порядке. Если список кольцевой (с1гсп1аг !!з!), то указатель Глава 10.
Элементарные структуры данных 265 р«г«ге ««««! "": ~-" ---.'Л:.~: =-:-~"": ---- 1.4.1 --"-ЯУЕ[ 61 кя1 (е.| -- — — [««]з. Г т,,:... г Т91 3 '~~~6Г' [::.: ']ч [ ~„, . '~~. Г],';] Ы 6«а,! К~ -- — ~м/'~25~ ~« * ! 9] :',. «"'.~~16Г~~ .~~- [тЯ Рис. 10.3.
Вставка в дважды связанный список и удаление из него ргет«его головного элемента указывает на его хвост, а указатель ггехг хвостового элемента — на головной элемент. такой список можно рассматривать как замкнутый в виде кольца набор элементов. В оставшейся части раздела предполагается, что списки, с которыми нам придется работать, — неотсортироваиные и дважды связанные. Поиск в связанном списке Процедура 1лзт ЯнАксн(Ыс) позволяет найти в списке Ь первый элемент с ключом Й путем линейного поиска, и возвращает указатель на найденный элемент. Если элемент с ключом Й в списке отсутствует, возвращается значение м~. Процедура Ьвт Звлксн(Ь, 4), вызванная для связанного списка, изображенного на рис.
10.3а, возвращает указатель на третий элемент, а процедура 1лзт ЗвАксн(Ь, 7) — значение нп.: Ь|зт Бнлксн(Ыг) 1 х - аеад[Ц 2 ттЫ1е х „-6 Нп. и кеу[х] ф й 3 Йо х — ггехг[х] 4 гетнгп х Поиск с помощью процедуры Ь1зт БвАксн в списке, состоящем из и элементов, в наихудшем случае выполняется в течение времени 6 (и), поскольку может понадобиться просмотреть весь список.
Вставка в связанный список Если имеется элемент х, полю 1геу которого предварительно присвоено значение, то процедура Ь1зт 1мзвкт вставляет элемент х в переднюю часть списка (рис. 10.3б): Часть 1П. Структуры данных 266 1ЛЯТ 1ХБЕКТ(Ь,х) 1 пех1[х] — Ьеаг1[Ц 2 Н ЬЕаИ[Ь] ф МЬ 3 гпеп ргею[леаа[1]] — х 4 аеас[А] — х 5 ргео [х] — 1ЧП. Время работы процедуры 1лзт 11чзект равно О (1). Удаление из связанного списка Представленная ниже процедура 1лзт Реьете удаляет элемент х из связанного списка Ь. В процедуру необходимо передать указатель на элемент х, после чего она удаляет х из списка путем обновления указателей. Чтобы удалить элемент с заданным ключом, необходимо сначала вызвать процедуру 1лзт БеАксн для получения указателя на элемент: 1ЛЗТ 13ЕЬЕТЕ(Ь,х) 1 Н ргес[х] ~ 1Ч1Ь 2 Феп пех1 [ргеи[х]] — пех1[х] 3 ене аеас[А] — пех1[х] 4 Н пех1[х] ф %1 5 Феп ртес[пех1[х]] — ргеи[х] Удаление элемента из связанного списка проиллюстрировано на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
