Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 58
Текст из файла (страница 58)
Список свободных позиций работает как стек: очередной выделяемый объект является последним освобожденным. Таким образом, реализовать процедуры выделения и освобождения памяти для объектов можно с помощью стековых операций Рпэн и Рор. Глобальная переменная Тгее, использующаяся в приведенных ниже процедурах, указывает на первый элемент списка свободных позиций.
А[Л.ОСАТЕ-ОВ5ЕСТ О 1 К (гее == ИП. 2 еггог аНе хватает памяти" 3 е1ве х = 5гее 4 5гее = х.пехт 5 геплгп х РКЕЕ-ОВ5ЕСТ(х) 1 х.пехт = утее 2 угее = х Часть Ш Струюлуры данных 27б (б) (а) ! 2 3 4 5 6 7 8 (а) Рнс. 10.7. Результат вызовов процедур Аы.ослтп-Овшст и Ркяп-Ов)пст. (в) Список с рис. 10.5 (светлая штриховка) и список свободных позиций (темная штриховка). Стрелки показывают структуру списка свободньп! позиций.
(б) Результат вызова Аи.ослтя-Ов)вст() (возвращающего индекс 4), установки )гер]4] равным 25 и вмзова С)зт-!ызпкт(Ь,4). Головным элементом нового списка свободных позиций являетса обьеат 8, мпорый в списке свободных позиций представлял собой пссг]4]. (в) после выполнения 1)зт-пяьвте(ь, 8) вызывается ркяе-Ов)вст(б). Обьект 5 становнтся новым заголовком списка свободных позиций; следующим в списке за ним идет обьекг 8. Изначально список свободных позиций содержит все и объектов, для которых не выделено место.
Когда в списке свободных позиций больше не остается элементов, процедура Ап,осАтн-Ов)нст выдает сообщение об ошибке. Один список свободных позиций может обслуживать несколько связанных списков. Но рнс. 10.8 показаны два связанных списка и список свободных позиций, связанные посредством массивов лер, петг и ргеп. Время выполнения обеих процедур равно 0(1), что делает их весьма практичными.
Эти процедуры можно модифицировать так, чтобы они работали с любым набором однородных обьектов, лишь бы один из атрибутов объекта работал в качестве атрибута пех( списка свободных позиций. 2 3 4 5 6 7 8 9 (О лгх! Рнс. 10.8. Связанные списки Ь! (свстло-серый) и 4.7 (темно-серый) и обслукивающий их список свободных позиций (черный).
Глава 1О. Элеиенеларные структуры данник 777 Упражнения 10.3.1 Изобразите последовательность (13, 4, 8, 19, 5, 11), хранящуюся в дважды связанном списке, представленном с помощью нескольких массивов. Выполните зто же задание для представления с помощью одного массива. 10.3.г Разработайте процедуры Ап.осяте-Овзест и Ркее-Оврест для однородного набора объектов, реализованного с помощью одного массива.
10.3.3 Почему нет необходимости присваивать или вновь устанавливать значения атри- бутов ргее при реализации процедур Аееослте-Овзест и Ркее-Оврвот? 10.3.4 Зачастую (например, при страничной организации виртуальной памяти) все элементы списка желательно располагать компактно, в непрерывном участке памяти, например, используя т первых позиций в представлении списка несколькими массивами. Поясните, как реализовать процедуры АееосАте-Овзест и РкееОвуест так, чтобы получить компактное представление.
Считаем, что нет никаких указателей на элементы связанного списка извне. (Указание: восполъзуйтесь реализацией стека с помощью массива.) 10.3.5 Пусть 1, — дважды связанный список длиной и, который хранится в массивах )ееу, ргеэ и пезт длиной т. Предположим, что управление этими массивами осуществляется с помощью процедур Ап.осяте-Овзест и Ркее-Овзест, использующих дважды связанный список свободных позиций г'. Предположим также, что ровно и из т элементов находятся в списке Ь, а остальные гп — п элементов— в списке свободных позиций.
Разработайте процедуру СОМЕАСт1ру-1ЛЗт(1,, Г), которая в качестве параметров получает список Ь и список свободных позиций Г и перемещает элементы списка 1 таким образом, чтобы они занимали ячейки массива с индексами 1,2,..., и, а также преобразует список свободных позиций Г так, что он остается корректным и содержит ячейки массива с индексами п + 1, п + 2,..., тп. Время работы этой процедуры должно быть равным 9(и), а объем используемой ею дополнительной памяти не должен превышать некоторую фиксированную величину.
Докажите корректность разработанной процедуры. 10.4. Представление корневых деревьев Приведенные в предыдущем разделе методы представления списков подходят для любых однородных структур данных. Данный раздел посвящен задаче пред- 278 Часть!и. Структуры даиньи т. тост Рз.!, Рнс.!99. Представление бинарного дерева Т. Каждый узел х имеет атрибуты хр (вверх), х.
(еут (влево вниз) и х. т(р)з( (вправо вниз). Атрибуты /сер не показаны. стааления корневых деревьев с помощью связанных структур данных. Мы начнем с рассмотрения бинарных деревьев, а затем рассмотрим представление деревьев с произвольным количеством дочерних элементов. Каждый узел дерева представляет собой отдельный объект. Как и при изучении связанных списжзв, предполагается, что в каждом узле содержится атрибут )сед.
Остальные интересующие нас атрибуты представляют собой указатели на другие узлы, и их вид зависит от типа дерева. Бинарные деревья Как показано на рис. 10.9, для хранения указателей на родительский, дочерний левый и дочерний правый узлы бинарного дерева Т используются атрибуты р, 1еу( и пдл(. Если х.р = Нпо то х — корень дерева.
Если у узла х нет левого дочернего узла, х, 1ей = )чп.; аналогичное утверждение справедливо в случае отсутствия правого дочернего узла. Атрибут Т. гоо( указывает на корневой узел дерева Т. Если Т. гоо1 = ыи., то дерево Т пустое. Корневые деревья с произвольным ветвлением Схему представления бинарных деревьев мозно обобщить для деревьев любого класса, в которых количество дочерних узлов не превышает незюторой константы )с.
При этом атрибуты 1еу( и гздЬ1 заменяются атрибутами сЬзЫП сЫс(э,..., сЫс(ь Если количество дочерних элементов узла не ограничено, то эта схема не работает, поскольку заранее не известно, место для какого количества атрибутов (массивов при использовании представления с помощью нескольких массивов) нужно выделить.
Кроме того, даже если количество дочерних элементов )с ограничено большой константой, но на самом деле у многих узлов потомков намного меньше, то значительный объем памяти расходуется напрасно. 279 Глава ) О. Элементарные структуры данных ~'+у Рнс. 10.10. Представление дерева Т с левым дочерним и правым сестринским узлами. Каждый узел х имеет атрибуты х р (вверх), х. (еЯ-сЫВ (влево вниз) и х. МдМ взьнпд (вправо).
Атрибуты )мд ие показаны. К счастью, существует остроумная схема представления деревьев с произвольным количеством дочерних узлов. Преимущество этой схемы в том, что для любого корневого дерева с и дочерними узлами требуется объем памяти 0(п). На рис. 10.10 проиллюстрировано представление с левым дочерним и правим сесзнримским узлами (!ей-сЬИд, пйЬ(-з(ЬИпй гергезепгайоп).
Как и ранее, в каждом узле этого представления содержится указатель р на родительский узел, а атрибут Т. гоо1 указывает на юрень дерева Т. Однако вместо указателей на каждый дочерний узел каждый узел х содержит всего два указателя: 1. х. 1еД-сбзЫ указывает на крайний слева дочерний узел узла х; 2. х. Нд61-м6йпд указывает на узел, расположенный на одном уровне с узлом х, справа от него и непосредственно рядом с ним.
Если узел х не имеет потомков, то х. 1еу(-сбзЫ = )чй., а если узел х является крайним справа дочерним узлом своего родителя, то х. тзд61-вз61зпд = )чп.. Другие представления деревьев Иноща встречаются и другие способы представления корневых деревьев. Например, в главе 6 описано представление пирамиды, основанной на полном бинарном дереве, с помощью одного массива и индекса последнего узла пирамиды.
Деревья, о которых идет речь в главе 21, обходятся только по направлению к корню, поэтому в них содержатся лишь указатели на родительские элементы; указатели на дочерние элементы отсутствуют. Здесь возможны самые различные схемы. Наилучший выбор схемы зависит от юнкрегного приложения. 2ае Часть 01 Структуры даннык Упражнения 10.4.1 Начертите бинарное дерево, корень которого имеет индекс 6, и которое представлено приведенными ниже атрибутами.
Индекс кеу 1еД пд1ь! 1 12 7 3 2 15 8 ХП 3 4 1О ХП. 4 10 5 9 5 2 ХП. ХП. б 18 1 4 7 7 ХП. Х!ь 8 14 6 2 9 21 ХП. ХП. 1О 5 ХП. ХП. 70.4.г Разработайте рекурсивную процедуру, которая за время 0(и) выводит ключи всех и узлов бинарного дерева. 10.4.3 Разработайте нерекурсивную процедуру, которая за время 0(и) выводит ключи всех и узлов бинарного дерева.
В качестве вспомогательной структуры данных используйте стек. 10.4.4 Разработайте процедуру, которая за время 0(и) выводит ключи всех и узлов произвольного корневого дерева. Дерево реализовано в представлении с левым дочерним и правым сестринским элементами.
10.45 * Разработайте нерекурсивную процедуру, которая за время 0(и) выводит ключи всех и узлов бинарного дерева. Объем дополнительной памяти (кроме той, которая отводится под само дерево) не должен превышать некоторую константу. Кроме того, в процессе выполнения процедуры дерево (даже временно) не должно модифицироваться. 10.4.б * В представлении произвольного корневого дерева с левым дочерним и правым сестринским узлами в каждом узле есть по три указателя: 1е1т-с1ьгЫ, пдМ-ег61ьид и ратеи1. Если задан какой-то узел дерева, то определить его родительский узел и получить к нему доступ можно в течение фиксированного времени. Определить же все дочерние узлы и получить к ним доступ можно в течение времени, линейно зависящего от количества дочерних узлов. Разработайте способ хранения дерева с произвольным ветвлением, в каждом узле которого используются только два (а не три) указателя и одно логическое значение, при котором ро- 2И Глоее!О.
Элементарные структуры денных дительский узел или все дочерние узлы идентифицируются в течение времени, линейно зависящего от количества дочерних узлов. Задачи 10.1. Сравнение списков Определите асимптотическое время выполнения перечисленных в приведенной ниже таблице операций над элементами динамических множеств в наихудшем случае, если эти операции выполняются со списками перечисленных ниже типов.
10.1. Реализация объединяемых пирамид с помощью связанных списков В о6ьединпеиой пирамиде (шегйаые ))еар) поддерживаются следующие операции: МАке-Недр (создание пустой пирамиды), 1ь)еект, М(ь((м()м, ЕхткдстМ(ы)м()м и П)ч(оы). Покажите, как в каждом из перечисленных ниже случаев реализовать объединяемые пирамиды с помощью связанных списков.
Постарайтесь, чтобы каждая операция выполнялась с максимальной эффективностью. Проанализируйте время работы каждой операции по отношению к размеру обрабатываемого динамического множества. зь Списки отсортированы. 0. Списки не отсортированы. г поскольку в пирамиде полдерживыогсл операции Мгюмцм и Ехтклст-мпсгмцм,такую пирамиду можло назвать ейаейннлеией неубывающей ннркинйой (тегяаме пип-Ьеар). Аналогично, если бы в пирамиде полдсрживались операции Мах гм им и Ехткяст-махгмцм, ес ыткио было бы назвать ойьейннлемой неыпрлпиеющей пнрелтдой (пыгяаЫе пюк-Ьсар) 2В2 Часть Ш.
Структуры данньск в. Списки не отсортированы, а объединяемые динамические множества не пересекаются. 10.3. Поиск в отсортированном компактном списке В упр. 10.3.4 предлагается разработать компактную поддержку и-элементного списка в первых п позициях массива. Предполагается, что все ключи различны и что компактный список отсортирован, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
