Главная Промышленная автоматика.

4.3. Реализацию множеств посредством двоичных векторов можно использовать тогда, когда "универсальное множество" преобразовано в последовательность целых чисел от 1 до N. Опишите такое преобразование для следующих универсальных множеств:

а) множество целых чисел О, 1, 90;

б) множество целых чисел от и до т, где га < от;

в) множество целых чисел п, п + 2, п + 4, га -i- 2к для любых п и fe;

г) множество символов а, Ь, V;

д) массив двухсимвольных строк, каждый символ может быть любым символом из множества а, "Ь", V.

4.4. Напишите процедуры MAKENULL, UNION, INTERSECTION, MEMBER, MIN, INSERT и DELETE для множеств, представленных посредством списков, используя обобшенные операторы АТД сортированных списков. Отметим, что в листинге 4.3 используется специфическая реализация АТД списков.

4.5. Повторите упраяснение 4.4 для следующих реализаций множеств:

а) открытая хеш-таблица (используйте обобщенные операторы списков, работающие с сегментами);

б) закрытая хеш-таблица с линейной методикой разрешения коллизий;

в) несортированный список (используйте обобщенные операторы списков);

г) массив фиксированной длины и указатель на последнюю занятую позицию в массиве.

4.6. Для каждой реализации и каждого оператора из упражнений 4.4 и 4.5 найдите порядок времени выполнения операторов над множествами размера п.

4.7. Предположим, что для хеширования целых чисел в 7-сегментную хеш-таблицу используется хеш-функция Л(г) = i шос1 7.

а) приведите результирующую хеш-таблицу, если в нее вставляются точные кубы 1, 8 , 27 , 64, 125 , 216, 343;

б) повторите предыдущий пункт для закрытой хеш-таблицы с линейной методикой разрешения коллизий.

4.8. Предположим, что есть закрытая хеш-таблица с 5 сегментами, хеш-функцией h{i) = i mod 5 и линейной методикой разрешения коллизий. Покажите результат вставки в первоначально пустую хеш-таблицу последовательности чисел 23, 48, 35, 4, 10.

4.9. Приведите реализацию операторов АТД отобраясений с использованием открытой и закрытой хеш-таблиц.

4.10. Чтобы увеличить скорость выполнения операторов, мы хотим заменить открытую хеш-таблицу с В, сегментами, содержащую значительно больше чем Bi элементов, на другую хеш-таблицу с Вг сегментами. Напишите процедуру преобразования старой хеш-таблицы в новую, используя операторы АТД списков для заполнения каждого сегмента.

4.11. В разделе 4.8 мы обсуждали "случайные" хеш-функции, когда для проверки сегментов после возникновения г-й коллизии применяется функция h,(x) = (h(x) + di) mod В с использованием некоторой последовательности rf,, Й2.....dg 1- Мы также показали один способ вычисления этой последовательности, когда задается некоторая константа к, первое значение последовательности, обычно di > О, и применяется формула

i-i. если 2d,, < В,

l(2d, i - В) е ft, если 2d, i > В,



где г > 1, 5 является степенью 2, а знак е обозначает сложение по модулю 2. Для случая 5=16 найдите такое значение к, чтобы последовательность di, d, rfis включала все целые числа 1, 2, 15.

4.12. Нарисуйте частично упорядоченное дерево, полученное в результате вставки в пустое дерево целых чисел 5, 6, 4, 9,3, 1 и 7. Каков будет результат последовательного применения к этому дереву трех операторов DELETEMIN?

4.13. Предположим, что множество учебных курсов (см. пример из раздела 4.12) представлено в виде

а) связанного списка;

б) хеш-таблицы;

в) дерева двоичного поиска.

Измените объявление типов в листинге 4.14 для каждой из этих структур.

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

4.15. Предположим, что есть 20 ООО студентов, 1 ООО учебных курсов и что каждый студент записан в среднем на три учебных курса. Сравните структуру данных из листинга 4.14 с измененной структурой упражнения 4.14 по следующим показателям;

а) по требуемому пространству памяти;

б) по среднему времени выполнения процедуры printstudents;

в) по среднему времени выполнения процедуры печати названий курсов, аналогичной процедуре printstudents.

4.16. Для структуры данных из листинга 4.14 напишите процедуры вставки и удаления отношения "студент посещает курс с".

4.17. Каковы различия (если они есть) между структурой данных, представленной в листинге 4.14, и структурой, в которой множества С, и представлены списками указателей на соответствующие записи студентов и курсов.

4.18. Работники некой компании представлены в базе данных этой компании своими именами (предполагается, что все они уникальны), табельными номерами и номерами социального страхования. Основываясь на этих предположениях, предложите структуру данных, позволяющую найти повторяющиеся записи одного и того же работника. Как быстро (в среднем) можно выполнить такую операцию?

Библиографические примечания

Монография [67] является прекрасным источником дополнительной информации о хешировании. Методы хеширования начали развиваться с середины 50-х годов, и статья [85] - фундаментальная ранняя работа в этой области. Работы [73] и [77] содержат хорошие обзоры методов хеширования.

Мультисписки, как основная структура данных для сетевых распределенных баз данных, предложены в [22]. В работе [112] имеется дополнительная информация о применении таких структур в системах баз данных.

Реализация частично упорядоченных деревьев посредством куч - основная идея работы [119]. Очереди с приоритетами ранее рассматривались в книге [65].

В [89] обсуясдается вычислительная сложность основных операторов множеств. Техника анализа потоков данных, основанных на множествах, подробно рассмотрена в работах [5] и [18].



ГЛАВА 5

Специальные методы представления множеств

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

5.1. Деревья двоичного поиска

Начнем с деревьев двоичного поиска - основной структуры данных для представления множеств, чьи элементы упорядочены посредством некоторого отношения линейного порядка, которые, как обычно, обозначим символом "<". Эти структуры особенно полезны, когда исходное множество такое большое, что не рационально использовать его элементы непосредственно в качестве индексов массивов. Предполагается, что все элементы множеств являются элементами некоторого универсального множества - универсума, примером которого служит множество возможных идентификаторов в программе на языке Pascal. На деревьях двоичного поиска можно реализовать операторы INSERT, DELETE, MEMBER и MIN, причем время их выполнения в среднем имеет порядок O(logra) для множеств, состоящих из п элементов.

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

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

Пусть дерево двоичного поиска представляет некоторое множество элементов. Характеристическое свойство дерева двоичного поиска позволяет легко проверить принадлежность любого элемента исходному множеству. Для того чтобы определить, принадлекит ли элемент х исходному множеству, сначала сравним его с элементом г, находящимся в корне дерева. Если х = г, то вопрос о принадлекности элемента х множеству решен положительно. В случае х < г по характеристическому свойству дерева двоичного поиска





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 [44] 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0034