Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 55
Текст из файла (страница 55)
Выполните это же задание для представления с помощью одного массива. 10.3-2. Разработайте процедуры Аш)слте Овтест и Ркее Овзест для однород- ного набора объектов, реализованных с помошью одного массива. 10.3-3. Почему нет необходимости присваивать или вновь устанавливать значения полей ргеи при реализации процедур АЕЕОсАте Овшст и Ркее ОВ1ЕСТ? 10.3-4. Зачастую (например, при страничной организации виртуальной памяти) все элементы списка желательно располагать компактно, в непрерывном участке памяти. Разработайте такую реализацию процедур АееосАте Овшст и Ркее Овзест, чтобы элементы списка занимали позиции 1..т, где тп — количество элементов списка. (Указание: воспользуйтесь реализацией стека с помощью массива.) 10.3-5.
Пусть Х, — дважды связанный список длины тп, который хранится в массивах кер, ртеи и пех1 длины и. Предположим, что управление этими массивами осуществляется с помощью процедур Аы.Ослте Овтест и Ркее Овтест, использующих дважды связанный список свободных позиций г'. Предположим также, что ровно т из и элементов находятся в списке Х, а остальные и — т элементов — в списке свободных позиций. Разработайте процедуру Сомрлст~ет 1лзт(Х, Р), которая в качестве параметров получает список Х,и список свободных позиций Г; и перемешает элементы списка Х, таким образом, чтобы они занимали ячейки массива с индексами 1,2,..., пт, а также преобразует список свободных позиций Г так, что он остается корректным и содержит ячейки массива Часть П1.
Структуры данных 274 с индексами т + 1, т + 2,..., и. Время работы этой процедуры должно быть равным О (и), а объем использующейся ею дополнительной памяти не должен превышать некоторую фиксированную величину. Приведите тщательное обоснование корректности представленной процедуры. 10.4 Представление корневых деревьев Приведенные в предыдущем разделе методы представления списков подходят для любых однородных структур данных. Данный раздел посвящен задаче представления корневых деревьев с помощью связанных структур данных. Мы начнем с рассмотрения бинарных деревьев, а затем рассмотрим представление деревьев с произвольным количеством дочерних элементов. Каждый узел дерева представляет собой отдельный обьект.
Как и при изучении связанных списков, предполагается„ что в каждом узле содержится поле йеу. Остальные интересующие нас поля — это указатели на другие узлы, и их внд зависит от типа дерева. Бинарные деревья Как показано на рис. 10.9, для хранения указателей на родительский, дочерний левый и дочерний правый узлы бинарного дерева Т, используются поля р, 1ей и гзд61. Если р [ж] = ьа., то х — корень дерева. Если у узла х нет дочерних узлов, то 1еГг [х] = г1д1з1 [х] = ьл~..
Атрибут гио1 [Т] указывает на корневой узел дерева Т. Если тоо1 [Т] = ни., то дерево Т пустое. Рис. 10.9. Представление бинарного дерева Т 1поле лисеу не показано) Глава 10. Элементарные структуры данных 275 Корневые деревья с произвольным ветвлением Схему представления бинарных деревьев можно обобщить для деревьев любого класса, в которых количество дочерних узлов не превышает некоторой константы й. При этом поля правый и левый заменяются полями сЬзЫг, сйгЫз,..., с)гав. Если количество дочерних элементов узла не ограничено, то эта схема не работает, поскольку заранее не известно, место для какого количества полей (или массивов, при использовании представления с помощью нескольких массивов) нужно выделить. Кроме того, если количество дочерних элементов )г ограничено большой константой, но на самом деле у многих узлов потомков намного меньше, то значительный объем памяти расходуется напрасно.
К счастью, существует остроумная схема представления деревьев с произвольным количеством дочерних узлов с помощью бинарных деревьев. Преимущество этой схемы в том, что для любого корневого дерева с и дочерними узлами требуется объем памяти О (и). На рис. 10.10 проиллюстрировано представление с левым дочерним и прааьии сестринским узлами Пей-сЬ11б, пяЬг-з1Ь11ля гергезепгабоп).
Как и в предыдущем представлении, в каждом узле этого представления содержится указатель р, а атрибут пюг 1Т] указывает на корень дерева Т. Однако вместо указателей на дочерние узлы каждый узел гс содержит всего два указателя: 1. в поле 1еф сйгЫ [х) хранится указатель на крайний левый дочерний узел узла х; «.о~:, Г) Рис. 10.10. Представление дерева с левым дочерним и правым сестринским узлами 276 Часть 111. Структуры данных 2. в поле г1дЫ з1Ыйтд [х] хранится указатель на узел, расположенный на одном уровне с узлом х справа от него. Если узел т не имеет потомков, то 1е71 сЬ|1а[х] = мь, а если узел х— крайний правый дочерний элемент какого-то родительского элемента, то гтдй1 иЫгпд [х] = мь. Другие представления деревьев Иногда встречаются и другие способы представления корневых деревьев.
Например, в главе 6 описано представление пирамиды, основанной на полном бинарном дереве, в виде индексированного массива. Деревья, о которых идет речь в главе 21, восходят только к корню, поэтому в них содержатся лишь указатели на родительские элементы; указатели на дочерние элементы отсутствуют. Здесь возможны самые различные схемы. Наилучший выбор схемы зависит от конкретного приложения. Упражнения 10.4-1. Начертите бинарное дерево, корень которого имеет индекс 6, и которое представлено приведенными ниже полями. Индекс сер 1е7г ттдлт 1 12 7 3 2 15 8 мь 3 4 10 мь 4 10 5 9 5 2 мь ыьь 6 18 1 4 7 7 мь мь 8 14 6 2 9 21 мь ып.
10 5 мь мь 10.4-2. Разработайте рекурсивную процедуру, которая за время О (и) выводит ключи всех и узлов бинарного дерева. 10.4-3. Разработайте нерекурсивную процедуру, которая за время О (и) выводит ключи всех п узлов бинарного дерева. В качестве вспомогательной структуры данных воспользуйтесь стеком. Глава 10.
Элементарные структуры данных 277 Задачи 10-1. Сравнения списков Определите асимптотическое время выполнения перечисленных в приведенной ниже таблице операций над элементами динамических множеств в наихудшем случае, если эти операции выполняются со списками перечисленных ниже типов. Неотсорти- рованный однократно связанный Отсортиро- ванный Нсотссрти- рованный дважды связанный Отсортиро- ванный однократно связанный дважды связанный список список список список Белкси(ь,й) 1нзект(Ь,х) 1эеьете(Ь,х) Зцссезэок(ь,х) Ркепесеззок(Ь,к) М ламам(Ь) МАхвшм(Ь) 10.4-4.
Разработайте процедуру, которая за время О (и) выводит ключи всех п узлов произвольного корневого дерева. Дерево реализовано в представлении с левым дочерним и правым сестринским элементами. * 10.4-5. Разработайте нерекурсивную процедуру, которая за время О (и) выводит ключи всех п узлов бинарного дерева.
Объем дополнительной памяти (кроме той, что отводится под само дерево) не должен превышать некоторую константу. Кроме того, в процессе выполнения процедуры дерево (даже временно) не должно модифицироваться. *10.4-6. В представлении произвольного корневого дерева с левым дочерним и правым сестринским узлами в каждом узле есть по три указателя: 1еЯ с)иЫ, гщ)з1 агЫту и рагеп1. Если задан какой-то узел дерева, то определить его родительский узел и получить к нему доступ можно в течение фиксированного времени. Определить же все дочерние узлы и получить к ним доступ можно в течение времени, линейно зависящего от количества дочерних узлов.
Разработайте способ хранения дерева с произвольным ветвлением, в каждом узле которого используется только два (а не три) указателя и одна логическая переменная, при котором родительский узел или все дочерние узлы определяются в течение времснп, линейно зависящего от количества дочерних узлов.
Часть!11. Структуры данныи 278 10-2. Реализация объединяемых пирамид с помощью связанных списков В объединяемой пирамиде (шегйаЫе !зеар) поддерживаются следующне операции: МАке Недр (создание пустой пирамиды), !нбект, М(ммпн, БхткАст Мпч)м()м и ()яон'. Покажите, как в каждом из перечисленных ниже случаев реализовать с помощью связанных списков обьеднняемые пирамиды. Постарайтесь, чтобы каждая операция выполнялась с максимальной эффективностью. Проанализируйте время работы каждой операции по отношению к размеру обрабатываемого динамического множества. а) Списки отсортированы. б) Списки не отсортированы. в) Списки не отсортированы, и объединяемые динамические множества не перекрываются. 10-3.
Поиск в отсортированном компактном списке В упражнении 10.3-4 предлагается разработать компактную поддержку и-элементного списка в первых и ячейках массива. Предполагается, что все ключи различны, и что компактный список отсортирован, т.е. дла всех з = 1, 2,..., и, таких что иех! [з] ф нп., выполняется соотношение йеу [з] < кеу [иех! [з]]. Покажите, что при данных предположениях математическое ожидание времени поиска с помощью приведенного ниже рандомизированного алгоритма равно О ( /й): СОМРАСТ 1.1БТ БЕАКСН(Х., и, гс) 1 з — Йеаг![Ь] 2 зв!з!1е з ф (Ч(Е и Йеу[(] < )с 3 г!о 7 — КАЕМ(1, и) 4 !т" )сеу[з) < 3сеу[2) и )сеу[2) < )с 5 Феп з' 6 !г Йеу[(] = Й 7 гпеп ге!цгп з 8 з — иехе[а) 9 !Г з = мЕ или Ееу[г) > lс 10 г!зеп ге!цгп НП. !1 е!не гегцгп з' 'Поскольку в пирамиде поддерживаются операции Мщгмом н Ехталст Мгюмцм, такую пирамиду можно назвать обьщнняемой неубывающей пирамидой (гпегбаЫе югп-Ьеар).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
