Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 52
Текст из файла (страница 52)
Вновь обозначим через п размер таблицы, а через гн — число ключей, находящихся в таблице. Тогда Е= — ~ Ез =- 1 тз и+1 тч 1 и+1 = — (Н вЂ” Н т Лл ' т 2.г и — а+2 т н+! е=! з-! (4.95) где Н„=1+ —., + ... + — „— гармоническая функция, функ! ! цию Нн можно аппроксимировать следу1ощим образом; Н, ов ов!п(п)+т, где у — эйлерова константа. Если, кроме того, в (4.95) и/(л+ 1) заменить на сс, то мы получим Е = — „(!п(п+ 1) — !п(н — т+ 1)) = 1 = — !и 1 и+1 — 1 = — ! п (1 — а), (4.
96) а и+1 — т а где а приблизительно равно отношеншо занятой н имеющейся памяти, называемому коэффициентом заполнения; сз = 0 предполагает пустую таблицу, се = в/(и+ 1) — заполненнукз таблицу. Среднее значение Е числа проб при поиске или вклю. ченин случайно выбранного ключа как функции от коэффициента заполнения аз приведено в табл. 4.5. Таблица 4.6. Среднее значение числа цроб каи функции от коэффициента загрузки 0,1 0,25 0,5 0,75 0,9 0,95 0з99 1,05 1,15 1,39 1,65 2,5б 3,!5 4,бб 4.6. Лреобрааовоння ключа <расстановка) 313 Полученные числа действительно нызывают удивление; онн показывают чрезвычайно высокую эффективность метода преобразования ключа. Даже если таблица заполнена на 90 ош нонадобится в среднем только 2,5б пробы, чтобы лабо обнаружить местоположение ключа, либо найти свободное место1 Особо отметим, что эта цифра не зависит от абсолютного числа имеющихся ключей, а зависит лишь от коэффнццента заполнения.
Проведенный выше анализ основан на использовании метода разрешения конфликтов, который равномерно рассеивает ключи на оставшемся пространстве. Методы, прнмсняемыс на практике, несколько менее эффективны. Подробный анализ линейного опробирования дает следующее (4.97) среднее значение числа проб 14.10): 1 — а/2 Š—. =1 †(4 <)7) Некоторые значения Е1а) перечислены в табл, 4.7. Результаты, полученные даже при худшем методе разрешения конфликтов, так высоки, что возникает соблазн рассматривать преобразования ключей (расстановку) как всеобщую панацею. Ведь эффективность этого метода даже выше, чем у самых утонченных методов организации деревьев, которые здесь рассматривались, во всяком случае, если сравнивать количество шагов, необходимых для поиска и включения. Поэтому важно отчетливо представлять себе некоторые недостатки мс,- тода расстановки, которые очевидны при беспристрастном изучении.
Таблица 4.7. Среднее значение числа проб при линейном опробировании Ф Е 1,06 1,17 1,50 250 5,50 10,50 0,1 0,25 0,5 0,75 0,9 0,95 Разумеется, основной недостаток по сравнению с методами, использующими динамическое размещение, состоит в том, что размер таблицы фиксирован н не может приспосабливаться 1< действительнь|м потребностям. Поэтому необходимо доста точно хорошо оценить а рг)ог1 количество классифицируемых элементов данных, если мы хотим избежать незкономного использования памяти, а также низкой эффективности (или да>не переполнения таблицы). Даже если число элементов З(4 4, Динамические инчюрмациониыг структуры точно известно, что бывает крайне редко, для получения хорошей эффективности нужно, чтобы размер таблицы был несколько больше (скажем, на 10 о/в).
Второй главный недостаток метода рассеянной памяти становится очевидным, если ключи надо не только вставлять и разыскивать, но и удалять, так как удаление из таблицы очень затруднено, если не используется прямое связывание в цепочку элементов из области переполнения. Итак, справедливость требует отметить, что древовидные структуры не теряют своей привлекательности и в самом деле предпочтительны, если объем данных сильно варьируется и временами даже уменьшается.
УПРАЖ1! ЕНИЯ 4Л. Введем понятие рекурсивного типа тес(уре Т = Т, как объединения множества значе.п:й, определенных типом Т«с единственным значением попе «ничто», т. е. Т = Т«() (попе), Определение типа рег( (см (43)( могкпо, например, упростить до тес!ура рго = гесогд лоте. а((а; (ор)~гг, люгаег: ргг( епб Как располагается и памяти рекурсивная сгруктура, соответствуюшан рпс. 4.2? Вероятно, реализация такой структуры будет основана па схеме динамического распределения памяти, и поля, называемые (окйег и шоййгг и приведенном выше примере, будут содерзкать ссылки, получаемые автоматически, ио скрытые от программиста.
Какие трудности встретятся прн реализации такой структуры» 4.2. Определите структуры данных, описанные в последнем параграфе равд. 4.2, в терминах записей и ссылок. Можно ля, кроме того, представить такую родственную совокупность с помошью рекурсивнык типов, предложенных в предыдущем упражнении? 4.3. Предположим, что очередь «первым вошел — первым вышел» О с элементами типа ?, реализована в виде связанного списка. Определите соответств)чошую структуру данных, процедуры включения и удаления элем«шта из !г и функцию, проверяюшую, пуста или нет очередь.
В процедурах должны иметься собственные средства для экономного псрецспользоыания памяти. 4.4. Предположим, по записи и связанном списке содержат ключеиое воле типа (л(гдгг. Напишите программу сортнровни списка в порядке возрастания значений ключей. Зат~ ч сформулируйте процедуру, формирующую список, в котором элементы расположены в обратном порядке. 4.б. Нпклические списки (см. рнс.
4.54) обычно формируютси с так называемым заголовком списка. Какой смысл имеет использование такого заголовка? Напишите процедуры включения, удаления и поиска элемента с заданным ключом, Сделайте это, как предполагая существование заголовка, так и без него. 315 Улрпасиеинл Рис. 4.54.
Круговой список. Рнс. 4.55. Двунаправленный список. 4.5. Двунаправленный список — зто список элементов, которые связаны с обеих сторон (см. рнс. 4.55). Обе связи исходят иэ заголовка. Аналогична предыдущему упражнению напишите пакет процедур длн поиска, включения и удаления элементов. 4.7. Будет ли программа 4.2 правильно работать, если некоторая пара (ц р) встретится ао входном файле более одного раэар 4,3. Сообщение «'ТН15 5ЕТ 15 ВОТ РАЯТ!АЕЬУОЯПЕЯЕО'» («ДАННОЕ МНОЖЕСТВО НЕ ЯВЛЯЕТС)1 ЧАСТИЧНО УПОРЯДОЧЕННЬ4М») в программе 4.2 зо многих случанх малоннформатнвно. Дополните программу, чтобы она ныданала последовательность элементов, кото.
рые образуют цикл, если оа имеется. 4.9. 'г!апншите программу, которая читает теист программ, находит нсе определении н вызови процедур подпрограмм н пытэетсн установить топологнческое упорядочепис па подпрограммах Пусть Р «' ,О выполняется,еслн Р вызывается в О. 4.10. Нарисуйте дерево, которое построит программа 4.3, если входной файл состоит из и + 1 чисел н, 1, 2, 3, ..., н.
4.1!. В каком порядке встречаются узлы прн обходе дерева на рнс. 4.23 сверху вниз, слева направо н снизу вверху 4.12. Найдите правило построения последовательности из и чисел, для ко- торой программа 4.4 сформирует идеально сбалансированное дерева. 4.13. Рассмотрим два порядка обхода бинарных деревьев: (.) (1) Обойти правое поддерево. (2) Посетить иорень. (3) Обойти левое поддерево. (Ь) (1) Посетить корень.
~) 2) Обойти правое поддерево. 3) Обойти левое поддерево. 316 4. )(пнпмнческие информационные структура! Нме1отся лп канне-либо простые соотношения мезкду последовательностями узлов, получаемыми при этих порядках обхода и теми, которые дают три порядна, определенные выше в тексте? 414. Определите структуру данных для представлении н-арных деревьев. Затем напишите процедуру, которая обходит и-арное дерево и формирует бинарное дерево, содержащее те же элементы.
Предположим, что ключ, расположенный в элементе, занимает й слов н наждая ссылка заниыает одно слово памяти. Какова будет экономия памяти при ис. пользовании бинарного дерева по сравнению с и-ариым? 4.15. Предположим, что дерево построено на основе следующего описания ренурсивной структуры данных (см. упр 4.1): гестуре (гее = гесогй х: ! н(ейегг !е)1, ссай(: ггее епд Сформулируйте процедуру, которая находит элемент с заданным ключом х и выполняет операцию Р с этим элементом. 4пб. В файловой системе каталог файлов организован в виде упорядоченного бинарного дерева.
Каждый узел обозначает файл н содерхснт нмя файла, а также среди прочего дату последнего обращения к нему. закодпрованную в виде целого числа. Напшсште прогрэмму, которая обходит дерево и удаляет все файлы, последнее обращение к которым происходило до определенной даты. 4.17. В некоторой древовидной структуре частота обращения к каждому элементу измеряется эмпирически — приписыванием каждому узлу счетчика обращений.
Через определенный интервал времени организация дерева изменяется при помощи обхода всего дерева и формиро. ваиия нового дерева с использованием программы 4.4, которая вставляет элементы в порядке убывания счетчиков частоты обращений. Напишите программу, которая выполняет эту реорганизацию. Будет ли средняя длина пути в этом дереве равна, хуже или намного хуже,чем в оптимальном дереве? ' 4.16. Метод анализа алгоритма включення в дерево, описанный в разя. 4.5, можно таклсе использовать для вычислеяии средних значений для числа сравнений С„ н числа пересылок (обменов) М„ которые выполняются с помощью алгоритма быстрой сортировки (программа 2.10) при обработке п элементов массива, считая, что все н! перестановок н ключей (1, 2, ..., и) равновероятны.
?!айднте аналогию и опреде. лите С, и Л(,, 4.19. Нарисуйте сбалансированное дерево с 12 узлами, имеющее маисимальную высоту среди всех сбалансированных деревьев с 12 узлами. В какой последовательности нужно включать узлы, чтобы процедура (4.63) сформировала зто дерево? 4,20. Найдите такую последовательность из и включаемых элементов, что.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
