Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 52
Текст из файла (страница 52)
В ней также показано, как можно реализовать в средах программирования объекты и указатели, в которых они не поддерживаются в качестве примитивов. Ббльшая часть материала этой главы должна быть знакома всем, кто освоил вводный курс программирования.
Глава 11 знакомит читателя с хеш-таблицами, поддерживающими такие присущие словарям операции, как 1хзект, Редеете и Беяксн. В наихудшем случае операция поиска в хеш-таблицах выполняется в течение времени 9 (и), однако математическое ожидание времени выполнения подобных операций равно О (1). Анализ хеширования основывается на теории вероятности, однако для понимания большей части материала этой главы не требуются предварительные знания в этой области. Описанные в главе 12 бинарные деревья поиска поддерживают все перечисленные выше операции динамических множеств.
В наихудшем случае для выполнения каждой такой операции на и-элементном множестве требуется время 9 (и), однако при случайном построении бинарных деревьев поиска математическое ожидание времени работы каждой операции равно О(!кп). Бинарные деревья поиска служат основой для многих других структур данных. С красно-черными деревьями, представляющими собой разновидность бинарных деревьев поиска, нас знакомит глава 13. В отличие от обычных бинарных деревьев поиска, красно-черные деревья всегда работают хорошо: в наихудшем случае операции над ними выполняются в течение времени О(1кп).
Красно- Часть ! П. Структуры данных 259 черное дерево представляет собой сбалансированное дерево поиска; в главе 18 представлено сбалансированное дерево поиска другого вида, получившее название В-дерево. Несмотря на то, что механизмы работы красно-черных деревьев несколько запуганы, из этой главы можно получить подробное представление об их свойствах без подробного изучения этих механизмов. Тем не менее, будет довольно поучительно, если вы внимательно ознакомитесь со всем представленным в главе материалом. В главе 14 показано, как расширить красно-черные деревья для поддержки операций, отличных от перечисленных выше базовых.
Сначала мы рассмотрим расширение красно-черных деревьев, обеспечивающее динамическую поддержку порядковых статистик для множества ключей, а затем — для поддержки интервалов действительных чисел. ГЛАВА 10 Элементарные структуры данных В этой главе рассматривается представление динамических множеств простыми структурами данных, в которых используются указатели. Несмотря на то, что с помощью указателей можно сформировать многие сложные структуры данных, здесь будут представлены лишь простейшие из них: стеки, очереди, связанные списки и деревья.
Мы также рассмотрим метод, позволяющий синтезировать вз массивов объекты и указатели. 10.1 Стеки и очереди Стеки и очереди — это динамические множества, элементы из которых удаляются с помощью предварительно определенной операции гзеьете. Первым из стека (апаса) удаляется элемент, который был помещен туда последним: в стеке реализуется стратегия "последним вошел — первым вышел" (1аяг-1п, йга1-ош — 1.1РО). Аналогично, в очереди (с)иеие) всегда удаляется элемент, который содержится в множестве дольше других: в очереди реализуется стратегия "первым вошел— первым вышел" (йгя~-1п, йгя~-ощ — Р1РО).
Существует несколько эффективных способов реализации стеков и очередей в компьютере. В данном разделе будет показано, как реализовать обе эти структуры данных с помощью обычного массива. Стеки Операция вставки применительно к стекам часто называется Р0зн (запись в стек), а операция удаления — РОЕ (снятие со стека). Как видно из рис. 10.1, стек, способный вместить не более п элементов, можно реализовать с помощью массива 5 [1..п].
Этот массив обладает атрибутом гор [5], Глава 10. Элементарные структуры данных 261 4 5 с!5 с 6 1 2 '5 1 Л с —.-- — т--т, сор)5]= 5 5:. [[6! 2,4 ьЯДЯР1 ~~~ЙЙ сор!51 = 4 ) 4 5 С) сор 151 = 6 б) в) а) Рис. 10.1. Реализация стека Я в виде массива представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов Я [1..1ор [Я]], где Я [1] — элемент на дне стека, а Я [$ор [Я]]— элемент на его вершине.
Если 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 ~~~!":~!~4~2~~~~6~( -') ' [ " ) ' [ 4~[[![[ 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!з!) Ь вЂ” это объект с одним полем ключа кер и двумя полями-указателями: пех! (следующий) и ргеп (предыдущий).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
