Некоторые значения (а) перечислены в табл. 4.7. Резуль--таты, полученные даже цри худшем методе разрешения конф-ликтов, так высоки, что возникает соблазн рассматривать преобразования ключей (расстановку) как всеобщую панацею. Ведь эффективность этого метода даже выше, чем у са-ых утонченных методов организации деревьев, которые здесь рассматривались, во всяком случае, если сравнивать количество шагов, необходимых для поиска и включения. Поэтому важно отчетливо представлять себе некоторые недостатки метода расстановки, которые очевидны при беспристрастном изучении.

Таблица 4.7. Среднее значение числа проб при линейном опробировании

0,1 1,06

0,25 1,17

0,5 1.50

0,75 2,50

0,9 5,50

0,95 10,50

Разумеется, основной недостаток по сравнению с методами. Использующими динамическое размещение, состоит в том, что размер таблицы фиксирован и не может приспосабливаться к действительным потребностям. Поэтому необходимо достаточно хорошо оценить а priori количество классифицируемых элементов данных, если мы хотим избежать неэкономного-Использования памяти, а также низкой эффективности (или аже переполнения таблицы). Даже если число элементов

шШ Полученные числа действительно вызывают удивление; они Указывают чрезвычайно высокую эффективность метода пре-образования ключа. Даже если таблица заполнена на 90 %, ронадобится в среднем только 2,56 пробы, чтобы либо обнаружить местоположение ключа, либо найти свободное место! Особо отметим, что эта цифра не зависит от абсолютного числа имеющихся ключей, а зависит лищь от коэффициента

-да-йолиени-я...... -

Проведенный выше анализ основан на использовании метода разрешения конфликтов, который равномерно рассеивает ключи на оставшемся пространстве. Методы, применяемые 4на практике, несколько менее эффективны. Подробный анализ Шпинейного опробирования дает следующее (4.97) среднее значение числа проб [4.10]:

. В=1. (4.97)

-Бведоптонятие рекурсашюго типа

rectype Т = То

как объединения множества значений, определенных типом Jo с еднн-ственным значением попе ничто , т. е.

7 = Го и {попе}.

Определение типа ped [см (4.3)] можно, например, упростить до

rectype ped = record name: alfa;

father, mother: ped

Как располагается в памяти рекурсивная структура, соответствующая рис. 4.2?

Вероятно, реализация такой структуры будет основана на схеме динамического распределения памяти, и поля, называемые father и mother в приведенном выше примере, будут содержать ссылки, получаемые автоматически, но скрытые от программиста. Какие трудности встретятся при реализации такой структуры?

Определите структуры данных, описанные в последнем параграфе разд. 4.2, в терминах записей и ссылок. Можно ли, кроме того, представить такую родственную совокупность с помощью рекурсивных типов, предложенных- в предыдущем упражнении?

Предположим, что очередь первым вошел - первым вышел Q с элементами типа Т'о реализована в виде связанного списка. Определите соответствующую структуру данных, процедуры вмючения и удаления элемента из Q и функцию, проверяющую, пуста или нет очередь. В процедурах должны иметься собственные средства для экономного переиспользования памяти.

Предположим, что записи в связанном списке содержат ключевое поле типа Integer. Напишите программу сортировки списка в порядке возрастания значений ключей. Затем сформулируйте процедуру, формирующую список, в котором элементы расположены в обратном порядке.

Циклические списки (см. рис. 4.54) обычно формируются с так называемым заголовком списка. Какой смысл имеет использование такого заголовка? Напишите процедуры включения, удаления и поиска элемента с заданным ключом. Сделайте это, как предполагая суш^ ствование заголовка, так и без него.

ТОЧНО известно, что бывает крайне редко, для получения v рошей эффективности нужно, чтобы размер таблицы бы несколько больше (скажем, на 10 %).

Второй главный недостаток метода рассеянной памяти ста новится очевидным, если ключи надо не только вставлять и разыскивать, но и удалять, так как удаление из таблицы очень затруднено, если не используется прямое связывание в цепочку элементов из области переполнения. Итак, справец-ливость требует отметить, что древовидные структуры не теряют своей привлекательности и в самом деле предпочтительны, если объем данных сильно варьируется и временами даже уменьшается.

УПРАЖНЕНИЯ

Рис. 4.54. Круговой список.

Рис. 4.55. Двунаправленный список.

Двунаправленный список -это список элементов, которые связаны с обеих сторон (см. рис. 4.55). Обе связи исходят из заголовка. Аналогично предыдущему упражнению напишите пакет процедур для поиска, включения и удаления элементов.

Будет ли программа 4.2 правильно работать, если некоторая пара <х, уУ встретится во входном файле более одного раза?

W. Сообщение THIS SET IS NOT PARTIALLY ORDERED ( ДАННОЕ МНОЖЕСТВО HE ЯВЛЯЕТСЯ ЧАСТИЧНО УПОРЯДОЧЕННЫМ ) в программе 4.2 во .многих случаях малоинформативно. Дополните программу, чтобы она выдавала последовательность элементов, которые образуют цикл, если он имеется.

4.9. Напишите программу, которая читает текст программ, находит все определения и вызовы процедур подпрограмм и пытается установить топологическое упорядочение на подпрограммах. Пусть Р < Q выполняется ,если Р вызывается в Q.

10. Нарисуйте дерево, которое построит программа 4.3, если входной файл состоит из -f 1 чисел и, 1, 2, 3, .... п.

И. В каком порядке встречаются узлы при обходе дерева на рис 4.23 сверху вниз, слева направо и снизу вверх?

42. Найдите правило построения последовательности из п чисел, для которой программа 4.4 сформирует идеально сбалансированное дерево.

13. Рассмотрим два порядка обхода бинарных деревьев: Ка)

(1) Обойти правое поддерево.

(2) Посетить корень.

(3) Обойти левое поддерево.

,(1) Посетить корень.

(2) Обойти правое поддерево,

Кз) ОЗойти левое поддерево.