Лабораторная работа №3
Цель работы:
-
Изучить функции создания хеш-таблиц;
-
Изучить специальные методы сортировки;
Теоретические сведения:
Используйте материалы лекций за первый семестр изучения языка С++ и любую дополнительную литературу.
Лабораторное задание:
Решите следующие задачи:
Задача №1: Реализуйте множество лексем языка с помощью открытой хеш-таблицы, рассмотрите по крайней мере две реализации хеш-функции.
Задача №2: Предподложим, что для хеширования целых чисел в 7-ми сегментную хеш-таблицу используется функция h(i)=i mod 7:
а) выведите результирующую таблицу при использовании открытого хеширования;
б) выведите результирующую таблицу при использовании закрытого хеширования, если при коллизиях применялась линейная методика разрешения.
Задача №3: Напишите функцию карманной сортировки по номеру паспорта структур вида: фам, имя, отч, год рожд, №паспорта.
в номере паспорта 6 цифр.
Задача №4 Есть сортированный массив строк. Напишите программу поиска строки в массиве. Какова зависимость времени выполнения от кол-ва строк и от их длинны.