Решение задач «3 задачи»,
Программирование в Нижнем Новгороде

Тема 1 Двоичные деревья поиска Задание 1 Обработка упорядоченных данных с использованием двоичных деревьев поиска. Построение и обработка двоичных деревьев поиска. Реализовать программу, выполняющую следующий набор операций с деревьями поиска: поиск вершины с заданным значением ключа с выводом счетчика числа появлений данного ключа добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений построчный вывод дерева в наглядном виде на основе процедур обхода: - в симметричном порядке; - в обратно-симметричном порядке. Рекомендации: 1) Объявить и реализовать подпрограмму поиска. Поиск начинается с корня дерева и в цикле для каждой вершины сравнивается ее ключ с заданным значением. При совпадении ключей, поиск заканчивается с выводом значения счетчика числа появлений данного ключа. При несовпадении поиск продолжается в левом или правом поддереве текущей вершины. 2) Объявить и реализовать рекурсивную подпрограмму добавления новой вершины в дерево. Подпрограмма использует один параметр-переменную, определяющую адрес текущей вершины. Если при очередном вызове подпрограммы этот адрес равен nil, то производится добавление нового элемента с установкой всех необходимых полей. В противном случае продолжается поиск подходящего места для новой вершины за счет рекурсивного вызова подпрограммы с адресом левого или правого поддерева. При совпадении ключей надо просто увеличить значение счетчика появлений. 3) Объявить и реализовать рекурсивные подпрограммы для построчного вывода дерева в симметричном и обратно-симметричном порядке: Все процедуры обхода должны выводить вершины с числом отступов, пропорциональным уровню вершины: корень дерева не имеет отступов, вершины первого уровня выводятся на 5 отступов правее, вершины 2-го уровня – еще на 5 отступов правее и т.д. Для этого в рекурсивные подпрограммы обхода надо ввести второй формальный параметр - уровень этой вершины. Все процедуры обхода имеют похожую структуру. Например, процедура обхода в прямом направлении должна: проверить пустоту очередного поддерева вывести в цикле необходимое число пробелов в соответствии с уровнем вершины вывести информационную часть текущей вершины вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1 вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1 Сравнение рассмотренных правил вывода двоичного дерева поиска приводится в следующей таблице (Таблица в файле) Главная программа должна предоставлять следующие возможности: создание дерева с заданным числом вершин со случайными ключами добавление в дерево одной вершины с заданным пользователем значением ключа поиск в дереве вершины с заданным ключом построчный вывод дерева в наглядном виде Тема 2 Организация поиска в массиве данных при помощи специальных методов поиска. Задание. Реализовать программно метод хеш-поиска с разрешением конфликтов методом цепочек. Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа этот ключ добавляется в конец вспомогательного списка. Это требует включения в каждую ячейку хеш-таблицы двух указателей на начало и конец вспомогательного списка. Программа должна выполнять следующие действия: добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений вывод текущего состояния таблицы на экран удаление заданного ключа из таблицы Алгоритм удаления: вычислить хеш-функцию и организовать поиск удаляемого элемента в таблице если удаляемый элемент найден в ячейке таблицы, то эта ячейка либо становится пустой (если связанный с ней список пуст), либо в нее записывается значение из первого элемента списка с соответствующим изменением указателей если удаляемый элемент найден в списке, то производится его удаление с изменением указателей После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 20 ключей и разместить их поочередно в таблице размерности 9, 17 и 23. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии размерности таблицы на эффективность поиска. Задание 3 в файле.