СТА: Лабораторная работа №3 - Хэш-таблицы и деревья

Версия 2.0, 13 октября 2013г.

(С) 2012-2013, Зайченко Сергей Александрович, к.т.н, ХНУРЭ, доцент кафедры АПВТ

Правила выполнения лабораторной работы

1. Лабораторная работа выполняется либо бригадой из 2 человек, либо индивидуально. Если студент претендует на оценку “отлично”, работа должна выполняться полностью индивидуально.

2. В работе на выбор студента предлагаются варианты трех уровней сложности:

• Базовый уровень - оценка в интервале 15-20 баллов.
• Углубленный уровень - оценка в интервале 21-25 баллов.
• Амбициозный уровень - оценка не менее 25 баллов + бонусные баллы на усмотрение преподавателя.

3. Реализовывать задачи необходимо исключительно на языке программирования С++.

4. Работа оценивается не только по корректности функционирования решений задач, но и по культуре оформления исходного кода в читабельном виде, адекватности разбиения решения на модули и функции.

5. Поскольку одной из основных целей данного курса является изучение способов построения классических структур данных, при реализации задач запрещается использовать готовые библиотечные реализации этих структур.

6. Защита работы:

• устная и короткая без отчета в случае защиты в день лабораторной работы;
• с полноценным печатным отчетом и ответами на теоретические вопросы в случае защиты в другие дни.

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

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

Литература к лабораторной работе

1. Р. Седжвик “Алгоритмы на С++”:
• Глава 5 “Рекурсия и деревья”.
• Глава 12 “Таблицы символов и деревья бинарного поиска” (подразделы 12.5-12.9).
• Глава 14 “Хэширование”.
2. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн “Алгоритмы. Построение и анализ”, 2 издание:
• Глава 11 “Элементарные структуры данных (подраздел 11.4).
• Глава 12 “Хэш-таблицы”.
• Глава 13 “Двоичные деревья поиска”.
3. А. Ахо, Д. Хопкрофт, Д. Ульман “Структуры данных и алгоритмы”:
• Глава 3 “Деревья”.
• Глава 4 “Основные операторы множеств” (подразделы 4.7-4.9)
• Глава 5 “Специальные методы представления множеств” (подразделы 5.1-5.3).
4. Д. Кнут “Искусство программирования”:
• Том 1, глава 2, раздел 2.3 “Деревья”.
• Том 3, глава 6, раздел 6.2 “Поиск путем сравнения ключей”.
• Том 3, глава 6, раздел 6.4 “Хэширование”

Исходные данные

При решении задач лабораторной работы по желанию можно использовать готовые реализации изложенные в материалах лекций. Перечисленные ниже файлы прилагаются к данным методическим указаниям:

• Хэш-таблицы (hash_table.hpp, hash_table_open_impl.cpp, hash_table_closed_impl.cpp).
• N-арные деревья с фиксированным количеством узлов (tree_static.hpp, tree_parent_indices.cpp, tree_child_index_lists.cpp).
• N-арные деревья с динамическим количеством узлов (tree_dynamic.hpp, tree_dynamic.cpp)
• Классические бинарные деревья поиска (bstree.hpp, bstree.cpp).
• Красно-черные деревья (rbtree.hpp, rbtree.cpp).

Эти реализации можно использовать непосредственно как готовую библиотеку, либо использовать как начальную точку для собственного решения.

Выдавать данные файлы за собственные решения настоятельно не рекомендуется :)

Варианты базового уровня

Вариант №1:

Используя базовую структуру в виде массива меток и массива родительских индексов, реализуйте основные операции АТД “дерево” с метками в виде строк. Реализация должна содержать типовые операции создания, уничтожения, ROOT, NODE_LABEL, PARENT, LEFTMOST_CHILD, RIGHT_SIBLING, а также прямой, обратный и симметричный обход. Строки должны копироваться в дерево при вставке и корректно уничтожаться. Создайте тестовую программу, активизирующую реализацию всех операций.

Вариант №2:

Используя в качестве базы динамическую структуру узлов дерева с указателями на родителя, левый дочерний узел и правый братский узел, реализуйте основные операции АТД “дерево” с метками в виде строк. Реализация должна содержать типовые операции создания, уничтожения, ROOT, NODE_LABEL, PARENT, LEFTMOST_CHILD, RIGHT_SIBLING, а также прямой, обратный и симметричный обход. Строки должны копироваться в дерево при вставке и корректно уничтожаться. Создайте тестовую программу, активизирующую реализацию всех операций.

Вариант №3:

Используя базовую структуру в виде на основе массива меток и списков дочерних узлов, реализуйте основные операции АТД “дерево” с метками в виде строк. Реализация должна содержать типовые операции создания, уничтожения, ROOT, NODE_LABEL, PARENT, LEFTMOST_CHILD, RIGHT_SIBLING, а также прямой, обратный и симметричный обход. Строки должны копироваться в дерево при вставке и корректно уничтожаться. Создайте тестовую программу, активизирующую реализацию всех операций.

Вариант №4:

Пользуясь информацией с сайта cist.kture.kharkov.ua, создайте дерево на основе любой из базовых структур, хранящее информацию об устройстве университета: университет, факультеты, кафедры. Реализуйте прямой обход данного дерева, при котором структура университета распечатывается на консоли в удобном для чтения виде с отступами для каждого из уровней.

Вариант №5:

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

Вариант №6:

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

Вариант №7:

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

Произвольно выберите достаточно сложную функцию, содержащую различные тригонометрические, логарифмические функции в сочетании с различными алгебраическими операциями. Для упрощения, положим, что аргумент-ключ может быть только целым числом.

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

Вариант №8:

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

Вариант №9:

Воспользовавшись журналом группы, создайте BST в котором в качестве ключей будут выступать фамилии студентов, а в качестве значений - количество защищенных лабораторных работ. Далее в цикле:

• если пользователь вводит число 0, программа завершается;
• если пользователь вводит число 1, распечатайте список студентов на консоли в алфавитном порядке фамилий;
• если пользователь вводит число 2, затем должна быть введена фамилия студента, а программа должна распечатать количество защищенных им лабораторных работ, а если такого студента в дереве нет, напечатать сообщение об ошибке.

Вариант №10:

Напишите программу по простейшему управлению учетными записями пользователей. Если пользователь вводит число 1, программа ожидает ввод двух строк - логин и пароль нового пользователя. Если пользователь вводит число 2, программа также ожидает ввод двух строк - логин и пароль пользователя: если такой логин и пароль уже зарегистрированы, программа выдает на экран приветствующее сообщение (например, “Hello <login>”), если такого логина нет либо пароль неправильный, программа выдает сообщение об ошибке. Если пользователь вводит число 3, программа завершается. При следующем запуске пароли не сохраняются. Важным требованием является отказ от хранения паролей в памяти программы в явном виде, следует сохранить результат хэш-функции на строке-пароле, а не сам пароль. Реализация хранения учетных записей должна быть основана на хэш-таблица любого вида.

Варианты углубленного уровня

Вариант №11:

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

• Большой файл с произвольным осмысленным текстом
• Большой файл уже отсортированный по алфавиту (можно взять результат работы программы на первом варианте).

Объясните причину диспропорции времени выполнения на первом файле и втором файле.

Вариант №12:

Имеется текстовый файл, содержащих оценки студентов по предметам со следующим форматом:

Petrov 90 85 82

Ivanov 75 90 82

Sidorov 60 60 60

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

myprogram.exe input.txt output1.txt output2.txt output3.txt

должен вывести в output1.txt:

Petrov 90

Ivanov 75

Sidorov 60

в output2.txt:

Ivanov 90

Petrov 85

Sidorov 60

в output3.txt:

Ivanov 82

Petrov 82

Sidorov 60

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

Вариант №13:

В любом языке программирования имеется набор ключевых слов. В языке C зарезервированы следующие ключевые слова:

auto break case char const continue default

do double else enum extern float for

goto if inline int long register restrict

return short signed sizeof static struct switch

typedef union unsigned void volatile while

Язык С++ в стандарте 1998г. дополняет эти ключевые слова следующими:

bool catch class const_cast delete dynamic_cast explicit

export false friend inline mutable namespace new

operator private protected public reinterpret_cast static_cast template

this throw true try typeid typename using

virtual wchar_t

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

• Сколько обнаружено использований ключевых слов, относящихся только к языку C++.
• Сколько обнаружено ключевых слов, относящихся как к С, так и к С++.
• Сколько из прочитанных слов не являются ключевыми ни для C, ни для C++.

В качестве тестового файла удобно использовать исходный код самой программы.

Вариант №14:

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

John Smith: +1-254-705-10-58: USA, New York, Wall str. 10, ap. 125

Nickolay Ivanov: +7-095-283-11-90: Russia, Moscow, Tverskaya str. 12, ap. 62.

Semen Kravchuk: +38-044-205-12-40: Ukraine, Kiev, Bogdana Hmelnickogo str. 115, ap. 23.

Tomasz Kowalski: +48-032-44-27-13: Poland, Katowice, Chorzowska str. 50, ap. 105.

Тестовая программа должна иметь следующий интерфейс командной строки:

• Первый аргумент командной сроки является обязательным и задает имя файла, из которого нужно прочитать исходные данные. Если указан несуществующий файл и содержимое справочника будет меняться по ходу теста, то этот файл нужно будет автоматически создать.
• Если в качестве второго аргумента командной строки указан ключ “-add”, то третий, четвертый и пятый аргументы командной строки задают ФИО человека, номер телефона и адрес соответственно, запись о котором следует добавить в словарь. Никакие другие дополнительные аргументы не допускаются. После завершения программы запись о новом человеке должна появиться в исходном файле.
• Если в качестве второго аргумента командной строки указать ключ “-remove”, то третий аргумент должен задавать ФИО человека, запись о котором следует удалить из словаря. Никакие другие дополнительные аргументы не допускаются. После завершения программы запись о таком человеке не должна присутствовать в исходном файле. Если ФИО такого человека не найдено, следует напечатать на экране сообщение об ошибке.
• Если в качестве второго аргумента командной строки ни один из перечисленных выше ключей не указан, второй и последующие аргументы командной строки задают ФИО, телефон и адрес которых необходимо вывести на экран.

Вариант №15:

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

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

Программа должна поддерживать следующий интерфейс командной строки:

• Первый аргумент – имя входного текстового файла для анализа.
• Второй аргумент – имя файла для результатов.
• Третий аргумент (необязательный) - равен “-i” - означает игнорирование регистра символов при сравнении.

Варианты амбициозного уровня

Вариант №16:

Реализуйте структуру-множество целых чисел на основе 2-3 дерева. Для упрощения задачи разрешается опустить операцию удаления узлов. 2-3 дерево – дерево с двумя типами узлов:

• листья, хранящие конкретные значения;
• внутренние узлы, содержащие 3 связи с дочерними узлами и минимальные значения, хранящиеся во втором и третьем поддереве.

Внутренние узлы могут содержать как 2, так и 3 поддерева. Если остается только 1 поддерево, узел уничтожается и заменяется поддеревом. Если требуется 4 поддерева, узел разрывается пополам и вводится еще один уровень глубины.

Проведите измерения производительности операции вставки и максимальной высоты в создаваемом дереве на достаточно больших множествах для:

• последовательности элементов в случайном порядке;
• последовательности элементов, отсортированной по возрастанию;
• последовательности элементов, отсортированной по убыванию.

Подробнее о данной структуре можно прочесть по следующей ссылке:

• Р. Седжвик, глава 13 “Сбалансированные деревья”, раздел 13.3 “Нисходящие 2-3-4 деревья”

Вариант №17:

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

• последовательности элементов в случайном порядке;
• последовательности элементов, отсортированной по возрастанию;
• последовательности элементов, отсортированной по убыванию.

Подробнее о данной структуре можно прочитать по следующей ссылке:

• Р. Седжвик, глава 13 “Сбалансированные деревья”, раздел 13.1 “Рандомизированные BST-деревья”.

Вариант №18:

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

• Функцию создания матрицы, принимающую число строк и чисто столбцов. Изначально матрица должна предполагать, что все хранимые коэффициенты равны 0.
• Функцию уничтожения матрицы.
• Функции доступа и модификации конкретной ячейки матрицы по индексам.
• Функцию печати матрицы в поток – на стандартный поток вывода по умолчанию.
• Функции сложения, вычитания и умножения матриц.
• Функцию транспонирования матрицы.

Контрольные вопросы

1. Понятие хэш-функции. Основные требования к хэш-функциям. Понятие коллизии.
2. Разрешение коллизий в хэш-таблицах в случае открытого хэширования.
3. Разрешение коллизий в хэш-таблицах в случае закрытого хэширования.
4. АТД “Дерево”. Виды узлов в дереве. Высота дерева. Полное и неполное дерево. Арность дерева. Обход деревьев.
5. АТД “Дерево”: описание реализации на основе массива индексов родительских узлов.
6. АТД “Дерево”: описание реализации на основе списков дочерних узлов.
7. АТД “Дерево”: описание реализации на основе динамической структуры узлов.
8. Бинарное дерево поиска. Характеристическое свойство. Вычислительная сложность всех операций. Сбалансированное и несбалансированное дерево.
9. Операция вращения узлов в BST. Свойства, принцип реализации.
10. Основные принципы организации красно-черных BST-деревьев. Дополнительные свойства-ограничения. Примеры корректирующих действий.