Структуры данных и алгоритмы (1021739), страница 36
Текст из файла (страница 36)
Отметим, что влистинге 4.3 используется специфическая реализация АТД списков.4.5.Повторите упражнение 4.4 для следующих реализаций множеств:а) открытая хеш-таблица (используйте обобщенные операторы списков, работающие с сегментами);б) закрытая хеш-таблица с линейной методикой разрешения коллизий;в) несортированный список (используйте обобщенные операторы списков);г) массив фиксированной длины и указатель на последнюю занятую позициюв массиве.4.6. Для каждой реализации и каждого оператора из упражнений 4.4 и 4.5 найдите порядок времени выполнения операторов над множествами размера п.4.7. Предположим, что для хеширования целых чисел в 7-сегментную хеш-таблицуиспользуется хеш-функция h(i) = i mod 7.а) приведите результирующую хеш-таблицу, если в нее вставляются точныекубы 1, 8, 27, 64, 125, 216, 343;б) повторите предыдущий пункт для закрытой хеш-таблицы с линейной методикой разрешения коллизий.4.8.
Предположим, что есть закрытая хеш-таблица с 5 сегментами, хешфункцией A(i) = i mod 5 и линейной методикой разрешения коллизий. Покажите результат вставки в первоначально пустую хеш-таблицу последовательности чисел 23, 48, 35, 4, 10.4.9. Приведите реализацию операторов АТД отображений с использованием открытой и закрытой хеш-таблиц.4.10. Чтобы увеличить скорость выполнения операторов, мы хотим заменить открытую хеш-таблицу с Вг сегментами, содержащую значительно больше чем Вгэлементов, на другую хеш-таблицу с В2 сегментами.
Напишите процедуру преобразования старой хеш-таблицы в новую, используя операторы АТД списковдля заполнения каждого сегмента.4.11. В разделе 4.8 мы обсуждали "случайные" хеш-функции, когда для проверки сегментов после возникновения i-й коллизии применяется функцияht(x) = (h(x) + dt) mod В с использованием некоторой последовательности d 1?dz,...,dB-i.
Мы также показали один способ вычисления этой последовательности, когда задается некоторая константа k, первое значение последовательности, обычно di > 0, и применяется формула_144i_ltесли 2^_! < В,[(2d,_t - В) Ф ft, если 2d,_! > В,ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВ4.12.4.13.4.14.4.15.4.16.4.17.4.18.где i > 1, В является степенью 2, а знак Ф обозначает сложение по модулю 2.Для случая В = 16 найдите такое значение k, чтобы последовательность dlt d2, ...,die включала все целые числа 1, 2, ..., 15.Нарисуйте частично упорядоченное дерево, полученное в результате вставки впустое дерево целых чисел 5, 6, 4, 9, 3, 1 и 7. Каков будет результат последовательного применения к этому дереву трех операторов DELETEMIN?Предположим, что множество учебных курсов (см. пример из раздела 4.12)представлено в видеа) связанного списка;б) хеш-таблицы;в) дерева двоичного поиска.Измените объявление типов в листинге 4.14 для каждой из этих структур.Измените структуру данных в листинге 4.14 так, чтобы каждая регистрационная запись непосредственно указывала на своих собственников среди записей остудентах и учебных курсах.
Перепишите процедуру printstudents излистинга 4.14 для этой структуры данных.Предположим, что есть 20 000 студентов, 1 000 учебных курсов и что каждыйстудент записан в среднем на три учебных курса. Сравните структуру данныхиз листинга 4.14 с измененной структурой упражнения 4.14 по следующимпоказателям:а) по требуемому пространству памяти;б) по среднему времени выполнения процедуры printstudents;в) по среднему времени выполнения процедуры печати названий курсов, аналогичной процедуре printstudents.Для структуры данных из листинга 4.14 напишите процедуры вставки и удаления отношения "студент s посещает курс с".Каковы различия (если они есть) между структурой данных, представленной влистинге 4.14, и структурой, в которой множества С, и Sc представлены списками указателей на соответствующие записи студентов и курсов.Работники некой компании представлены в базе данных этой компании своими именами (предполагается, что все они уникальны), табельными номерами иномерами социального страхования.
Основываясь на этих предположениях,предложите структуру данных, позволяющую найти повторяющиеся записиодного и того же работника. Как быстро (в среднем) можно выполнить такуюоперацию?Библиографические примечанияМонография [67] является прекрасным источником дополнительной информациио хешировании. Методы хеширования начали развиваться с середины 50-х годов, истатья [85] — фундаментальная ранняя работа в этой области. Работы [73] и [77] содержат хорошие обзоры методов хеширования.Мультисписки, как основная структура данных для сетевых распределенных базданных, предложены в [22]. В работе [112] имеется дополнительная информация оприменении таких структур в системах баз данных.Реализация частично упорядоченных деревьев посредством куч — основная идеяработы [119].
Очереди с приоритетами ранее рассматривались в книге [65].В [89] обсуждается вычислительная сложность основных операторов множеств.Техника анализа потоков данных, основанных на множествах, подробно рассмотренав работах [5] и [18].УПРАЖНЕНИЯ145ГЛАВА 5СпециальныеметодыпредставлениямножествВ этой главе мы рассмотрим структуры данных для представления множеств, которые позволяют более эффективно реализовать общий набор операторов, выполняемыхнад множествами, чем это описано в предыдущих главах. Однако эти структуры значительно сложнее и чаще всего применяются только для больших множеств. Все ониоснованы на различного рода деревьях, таких как деревья двоичного поиска, нагруженные и сбалансированные деревья.5.1.
Деревья двоичного поискаНачнем с деревьев двоичного поиска — основной структуры данных для представления множеств, чьи элементы упорядочены посредством некоторого отношения линейного порядка, которые, как обычно, обозначим символом "<". Этиструктуры особенно полезны, когда исходное множество такое большое, что не рационально использовать его элементы непосредственно в качестве индексов массивов. Предполагается, что все элементы множеств являются элементами некоторогоуниверсального множества — универсума, примером которого служит множествовозможных идентификаторов в программе на языке Pascal. На деревьях двоичногопоиска можно реализовать операторы INSERT, DELETE, MEMBER и MIN, причемвремя их выполнения в среднем имеет порядок O(logn) для множеств, состоящихиз п элементов.Дерево двоичного поиска — это двоичное дерево, узлы которого помечены элементами множеств (мы также будем говорить, что узлы дерева содержат или хранятэлементы множества).
Определяющее свойство дерева двоичного поиска заключаетсяв том, что все элементы, хранящиеся в узлах левого поддерева любого узла ж, меньше элемента, содержащегося в узле х, а все элементы, хранящиеся в узлах правогоподдерева узла х, больше элемента, содержащегося в узле х. Это свойство называетсяхарактеристическим свойством дерева двоичного поиска и выполняется для любогоузла дерева двоичного поиска, включая его корень.На рис. 5.1 показаны два дерева двоичного поиска, представляющие одно и то жемножество целых чисел. Отметим интересное свойство деревьев двоичного поиска:если составить список узлов этого дерева, обходя его во внутреннем (симметричном)порядке, то полученный список будет отсортирован в порядке возрастания (в соответствии с заданным на множестве отношением линейного порядка).Пусть дерево двоичного поиска представляет некоторое множество элементов.
Характеристическое свойство дерева двоичного поиска позволяет легко проверить принадлежность любого элемента исходному множеству. Для того чтобы определить, принадлежитли элемент х исходному множеству, сначала сравним его с элементом г, находящимся вкорне дерева. Если х = г, то вопрос о принадлежности элемента х множеству решен положительно. В случае х < г по характеристическому свойству дерева двоичного поиска1элемент х может быть потомком только левого сына корня дерева . Аналогично, еслих > г, то элемент х может быть потомком только Правого сына корня дерева.1071218/15аРис.
5.1. Два дерева двоичного поискабНапишем простую рекурсивную функцию МЕМВЕЩ*, А), реализующую тест напринадлежность элемента множеству. Предположим, что элементы множества имеютпока не определенный тип данных, который назовем elementtype. Будем считать, чтодля этого типа данных определены отношения "<" и "=". Если это не так, то необходимо написать функции LT(a, Ь) и EQ(a, b) такие, что для любых элементов а и Ь типа elementtype функция LT(a, b) будет принимать значение true тогда и только тогда,когда а "меньше" Ъ, а функция EQ(a.
Ь) — когда а "равно или больше" Ь.Тип данных nodetype узлов дерева, содержащих поле element для элементов множества и два поля leftchild и rightchild указателей на левого и правого сыновей, определим с помощью следующего объявления:typenodetype = recordе!елгел t: elementtype ;leftchild, rightchild:end;tnodetypeДалее определим тип SET (Множество) как указатель на узел, который будет корнем дерева двоичного поиска при представлении множества:typeSET: tnodetype;Теперь можно написать полный код функции MEMBER (листинг 5.1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
