Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 55

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 55)

Структуры данньи РкепесеззОк(5, х) Запрос к полностью упорядоченному множеству Я, который возвращает указатель на элемент множества Я, ключ которого является ближайшим меньшим по значению соседом ключа элемента х. Если же х — минимальный элемент множества 5, то возвращается значение ХП.. Запросы Биссеззок и Ркепесеззок в некоторых ситуациях обобщаются на множества, в которых не все ключи различаются. Для множества, состоящего из и элементов, обычно принимается допущение, что вызов операции М~ымСм, после которой и — 1 раз вызывается операция Биссеззок, позволяет пронумеровать элементы множества в порядке сортировки, Время, необходимое для выполнения операций множества, обычно измеряется в единицах, связанных с размером множества, который указывается в качестве одного из аргументов.

Например, в главе 13 описывается структура данных, способная поддерживать все перечисленные выше операции, причем время их выполнения на множестве размером и выражается как 0(1б и). Обзор части Ш В главах 10-14 описываются несколько структур данных, с помощью которых можно реализовать динамические множества. Многие из этих структур данных будут использоваться впоследствии при разработке эффективных алгоритмов, позволяющих решать разнообразные задачи.

Еще одна важная структура данных, пирамида, уже рассматривалась в главе 6. В главе 10 представлены основные приемы работы с такими простыми структурами данных, как стеки, очереди, связанные списки и корневые деревья. В ней также показано, как можно реализовать в средах программирования объекты и указатели, в которых они не поддерживаются в качестве примитивов, Ббльшая часть материала этой главы должна быть знакома всем, кто освоил вводный курс программирования.

Глава 11 знакомит читателя с хеш-таблицами, поддерживающими такие словарные операции, как 1мзект, Редеете и БеАксн. В наихудшем случае операция поиска в хеш-таблицах выполняется в течение времени кэ(п), однако математическое ожидание времени выполнения подобных операций равно 0(1). Анализ хеширования основывается на теории вероятности, однако для понимания большей части материала этой главы не требуются предварительные знания в этой области. Описанные в главе 12 бинарные деревья поиска поддерживают все перечисленные выше операции динамических множеств. В наихудшем случае для выполнения каждой такой операции на и-элементном множестве требуется время 9(п), однако при случайном построении бинарных деревьев поиска математическое ожидание времени работы каждой операции равно 0(1бп).

Бинарные деревья поиска служат основой для многих других структур данных. С красно-черными деревьями, представляющими собой разновидность бинарных деревьев поиска, вы познакомитесь в главе 13. В отличие от обычных бинарных деревьев поиска, красно-черные деревья всегда работают хорошо: в наи- Часть Ш. Стсстктуры даннын худшем случае операции над ними выполняются за время 0(18 и). Красно-черное дерево представляет собой сбалансированное дерево поиска; в главе 18 части Ч представлено сбалансированное дерево поиска другого вида, получившее название "В-дерево". Несмотря на то что механизмы работы красно-черных деревьев несколько запутаны, из этой главы можно получить детальное представление об их свойствах без подробного изучения этих механизмов. Тем не менее будет довольно поучительно, если вы внимательно ознакомитесь со всем представленным в главе материалом.

В главе 14 показано, как расширить красно-черные деревья для поддержки операций, отличных от перечисленных выше базовых. Сначала будет рассмотрено расширение красно-черных деревьев, обеспечивающее динамическую поддержку порядковых статистик для множества ключей, а затем — для поддержки интервалов действительных чисел. Глава 10.

Элементарные структуры данных В этой главе рассматривается представление динамических множеств простыми структурами данных, в которых используются указатели. Несмотря на то что с помощью указателей можно сформировать многие сложные структуры данных, здесь будут представлены лишь простейшие из них: стеки, очереди, связанные списки и деревья. Мы также рассмотрим метод, позволяющий синтезировать из массивов объекты и указатели. 10.1. Стеки и очереди Стеки и очереди представляют собой динамические множества, элементы из которых удаляются с помощью предварительно определенной операции Он.нтн.

Первым из сшека (зГаск) удаляется элемент, который был помещен туда последним: в стеке реализуется стратегия "последним вошел — первым вышел" (1аз1-1п, йгз1-оц1 — ЫРО). Аналогично в очереди 1ццеце) всегда удаляется элемент, который содержится в множестве дольше других: в очереди реализуется стратегия первьим вошел — первым вышел Ягз1-1п, йгзз-ощ — ЯРО).

Существует несколько эффективных способов реализации стеков и очередей в компьютере. В данном разделе будет показано, как реализовать обе этн структуры данных с помощью обычного массива. Стеки Операция вставки 1хзект применительно к стекам часто называется записью в стек Ризи, а операция удаления Оньдтн, которая вызывается без передачи аргумента, — снятием со стека Рог. Как видно из рис. 10.1, стек, способный вместить не более п элементов„можно реализовать с помощью массива Я(1 .. и(, Этот массив обладает атрибутом Я. 1ор, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов 5[1 ..

5. 1ор(, где 5(1( — элемент на дне стека, а Я(Я. 1ор)— элемент на его вершине, Если Я. 1ор = О, то стек не содержит ни одного элемента и является пуешмм (ешргу). Протестировать стек на наличие в нем элементов можно с помощью опе- Часть 1!Е Структуры данных 266 1 2 3 4 5 б 7 В 9 10 11 12 15)(о '1' р рГЗ-'~'4' ().Ьеад = 7 (), гап = 12 (э! й 1 2 3 4 5 б 7 8 9 10 11 12 (б) (2) зс'37 Сыь!ь2ь~~ДД ().1аи = 3 Я.аеас = 7 5 б 7 В 9 1О 11 12 1 2 3 4 (з) Д '1 37й ' ().1а11 = 3 'б ГфТ'Я -.4Я 12.йеад = 3 Рис. 10.2, Реааизапия очереди с помощью массива (2(1., 12).

Элементы очерели содержатся только в светло-серых ячейках. (а) Очередь содержит пять элементов в позициях () !7 .. 1Ц. (6) Конфигурациа очереди после вызовов Еноцвод(О, 17), Еноц под((2, 3) и Енсипив(Я, 3). (в) Конфигурациа очереди после того, как вызов 1)воовпа(()) вернул кщочевое значение 13, ранее находившееся в голове очереди. Новый элемент в голове очереди имеет юпоч б.

очереди к врачу в поликлинике. У нее имеются голока (Ъеаб) и хаоеие (Ва(!), Когда элемент помещается в очередь, он занимает место в ее хвосте, точно так же, как человек занимает очередь последним, чтобы попасть на прием к врачу. Из очереди всегда выводится элемент, который находится в ее головной части аналогично тому, как в кабинет врача всегда заходит больной, который ждал дольше всех.

На рис. 10.2 показан один нз способов, который позволяет с помощью массива Я[1 .. п] реализовать очередь, состоящую не более чем из и — 1 элементов. Эта очередь обладает атрибутом Я. Ьеас(, который является индексом головного элемента или указателем на него; атрибут Я. (аз( индексирует местоположение, куда будет добавляться новый элемент. Элементы очереди расположены в ячейках Я. Ьеа12, Я.

Ье1ы( + 1,..., Я. (аз2 — 1, которые циклически замкнуты в том смысле, что ячейка 1 следует сразу же после ячейки п в циклическом порядке. При выполнении условия Я.Ьеаг( = Я. (аз2 очередь пуста. Изначально выполняется соотношение Я. Ьеаг( = Я. 1а12 = 1. Если очередь пуста, то при попытке удалить из нее элемент происходит ошибка опустошения. Если Я. Ьеагз = ('„3. (аз2 + 1, или Я. ьецгз = 1 и (6.(ае = Я. 1епд(ь, то очередь заполнена, и попытка добавить в нее элемент приводит к ее переполнению. В наших процедурах Е)чО(7е(ге и Пе0(7е(7е проверка ошибок опустошения и переполнения не проводится.

(В улр. 10.1.4 предлагается добавить в процедуры соответствующий код.) В псевдокоде предполагается„что п = Я. (епд(Ь. 2б7 Глава РД Злеывнтааные структуры банкет ЕМ00Е0Е(ф х) 1 Я[Я.1ае1[ = х 2 й' Я. 1ай == Я. 1епдгЬ 3 Я.сае1 = 1 4 е!зе сна.1ае1 = Я.1ае1+1 13Е00ЕОЕ(сне) 1 х = ф(,>.Ьеаа[ 2 И Я.

Ьеай == Я. 1епдЕЬ 3 Я. Ьеас( = 1 4 е1зе Я.Ьеаа = Я.Ьеад+ 1 5 гегпгл х На рис. 10.2 показана работа процедур ЕН00ЕНЕ и 0Е00ЕОЕ. Каждая операция выполняется за время 0(1). Упражнения 10.1.1 Используя рис. 10.1 в качестве образца, проиллюстрируйте результат воздействия яа изначально пустой стек Я, хранящийся в массиве 3[1 .. 6[, последовательности операций Рнен(о,4), Рнзн(Я, 1), Рнен(Я,З), Рот(Я), Рнен(о,8) и Рот(о). 1й1.2 Объясните, как с помощью одного массива А[1 .. и[ можно реализовать два стека таким образом, чтобы ни один из них не переполнялся, пока суммарное количество элементов в обоих стеках не достигнет п. Операции Рнвн и Рог должны выполняться за время 0(1). 1й1.3 Используя рис. 10.2 в качестве образца, проиллюстрируйте результат каждой из операций в последовательности Ен00еие(9, 4), Ен00ене(Я, 1), Ен00ене(ь1,3), 13е00енеЯ), Ен0иене(9,8) и 13е0иене(Я) над изначально пустой очередью Я, хранящейся в массиве Я[1..6].

Характеристики

Список файлов книги