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