Алгоритмы - построение и анализ (1021735), страница 54
Текст из файла (страница 54)
Деревья, о которых идет речь в главе 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 е!не гегцгп з' 'Поскольку в пирамиде поддерживаются операции Мщгмом н Ехтклст Мгюмцм, такую пирамиду можно назвать обьщнняемой неубывающей пирамидой (гпегбаЫе югп-Ьеар). Аналогично, если бы в пирамиде поддерживались операции Млх~мгзм н Ехтнлст Мдхгмом, ее можно было бн назвать объединяемой невозрастающей пирамидой (гпегбаЫе так-ьеар).
Глава 10. Элементарные структуры данных Если в представленной выше процедуре опустить строки 3-7, получится обычный алгоритм, предназначенный для поиска в отсортированном связанном списке, в котором индекс 1 пробегает по всем элементам в списке. Поиск прекращается в тот момент, когда происходит "обрыв" индекса 1 в конце списка или когда Ееу [1] > й.
В последнем случае, если выполняется соотношение Еед [1] = 1с, то понятно, что ключ 1с найден. Если же Йеу [1] > Й, то ключ Й в списке отсугствует и поэтому следует прекратить поиск. В строках 3-7 предпринимается попытка перейти к случайно выбранной ячейке 2. Такой переход дает преимущества, если величина йеу [7] больше величины йеу [1], но не превышает значения й.
В этом случае индекс з соответствует элементу списка, к которому рано или поздно был бы осуществлен доступ при обычном поиске. Поскольку список компактен, любой индекс 2 в интервале от 1 до п отвечает некоторому объекту списка и не может быть пустым местом из списка свободных позиций. Вместо анализа производительности процедуры СомРАст Ь!эт ЗеАксн мы проанализируем связанный с ним алгоритм СомРАст 1лзт ЯеАксн', в котором содержатся два отдельных цикла. В этом алгоритме используется дополнительный параметр 1, определяющий верхнюю границу количества итераций в первом цикле: СОМРАСТ ЬБТ БЕАКСН (Х, и, Й, 1) 1 1 — Ьеад[Ь] 2 аког д ~ — 1 го 1 3 йо 2 КАмэом(1, п) 4 Рб Йеу[г] < /сер[2] и Фей[2] < к 5 1'пеп г' 6 1Г йеу[г] = Й 7 гпеп ге1пгп 1 8 тгИ1е1~ ий. и Йеу[1] < Й 9 йо 1 — пех1[1] 1О 111 = ме или йеу[г] > lс 11 1пеп гегнгп ип.
12 е1ае ге1пгп 1 Для простоты сравнения алгоритмов СомРАст 1лзт Белксн(Ь,п, Е) и Сомглст 1лзт БеАксн'(Ь,п,й,1) будем считать, что последовательность случайных чисел, которая возвращается процедурой Кливом(1, п), одна и та же для обоих алгоритмов. а) Предположим, что в ходе работы цикла и Ы1е в строках 2-8 процедуры СомРАст 1.Бт Белесн(Ь, и, Й), выполняется 1 итераций. До- Часть й!. Структуры данных 280 кажите, что процедура Сомглст 1лзт Белксн'(Т„п, )с,1) даст тот же ответ, и что общее количество итераций в циклах 1ог и иЫ1е этой процедуры не меньше 1.
Пусть при работе процедуры Сомглст 1.!зт Бвлксн'(Ь, и, Й, 1) Х~ — случайная величина, описывающая расстояние в связанном списке (т.е. длину цепочки из указателей пез1) от элемента с индексом г' до искомого ключа )с после 1 итераций цикла 1ог в строках 2-7. б) Докажите, что математическое ожидание времени работы процедуры СомРлст 1.!Бт Белксн (Ь, п, й, г) равно О (г+ Е [Х~]). в) Покажите, что Е[Х~] < 2"," „(1 — г/и) . (Указание: воспользуйтесь уравнением (В.24)). г) Покажите, что 2 „, г < п~+1/(1+1).
д) Докажите, что Е [Х,] < и/(Ф + 1). е) Покажите, что математическое ожидание времени работы процедуры СомРлст 1!зт Бвлксн'(Х,, п,)с,1) равно О(1+п/1). ж) Сделайте вывод о том, что математическое ожидание времени работы процедуры Сомклст 1лзт Бвлксн равно О (~/й). з) Объясните, зачем при анализе процедуры Сомглст 1лзт БРлксн понадобилось предположение о том, что все ключи различны. Покажите, что случайные переходы не обязательно приведут к сокращению асимптотического времени работы„если в списке содержатся ключи с одинаковыми значениями. Заключительные замечания Прекрасными справочными пособиями по элементарным структурам данных являются книги Ахо (АЬо), Хопкрофта (Норсгой) и Ульмана (11!!шап) (6] и Кнута (Кпи1п) [182].
Описание базовых структур данных и их реализации в конкретных языках программирования можно также найти во многих других учебниках. В качестве примера можно привести книги Гудрича (Оообпсп) и Тамазии (Ташазз!а) (128], Мейна (Маш) [209], Шаффера (Бпайег) (273] и Вейса (%е1зз) [310, 312, 313]. В книге Гоннета (Ооппе1) [126] приведены экспериментальные данные, описывающие производительность операций над многими структурами данных. Начало использования стеков и очередей в информатике в качестве структур данных по сей день остается недостаточно ясным. Вопрос усложняется тем, что соответствующие понятия существовали в математике и применялись на практике при выполнении деловых расчетов на бумаге еще до появления первых цифровых вычислительных машин. В своей книге (182] Кнут приводит относящиеся Глава 10.
Элементарные структуры данных 281 к 1947 году цитаты А. Тьюринга (А.М. Типпй), в которых идет речь о разработке стеков для компоновки подпрограмм. По-видимому, структуры данных, основанные на применении указателей, также являются "народным" изобретением. Согласно Кнуту, указатели, скорее всего, использовались еще на первых компьютерах с памятью барабанного типа. В языке программирования А-1, разработанном Хоппером (О.М. Норрег) в 1951 году, алгебраические формулы представляются в виде бинарных деревьев. Кнут считает, что указатели получили признание и широкое распространение благодаря языку программирования 1Р1.-11, разработанному в 195б году Ньюэлом (А.
Нетче11), Шоу ().С. Блатч) и Симоном (Н.А. Зппоп). В язык 1Р1.-П1, разработанный в 1957 году теми же авторами, операции со стеком включены явным образом. ГЛАВА 11 Хе ш-таблицы Для многих приложений достаточны динамические множества, поддерживающие только стандартные словарные операции вставки, поиска и удаления. Например, компилятор языка программирования поддерживает таблицу символов, в которой ключами элементов являются произвольные символьные строки, соответствующие идентификаторам в языке. Хеш-таблица представляет собой эффективную структуру данных для реализации словарей.
Хотя на поиск элемента в хеш-таблице может в наихудшем случае потребоваться столько же времени, что и в связанном списке, а именно 6 (и), на практике хеширование исключительно эффективно. При вполне обоснованных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет О (1). Хеш-таблица представляет собой обобщение обычного массива. Возможность прямой индексации элементов обычного массива обеспечивает доступ к произвольной позиции в массиве за время О (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
