Индексно — последовательный поиск в упорядоченной таблице
Этот метод заключается в создании дополнительной таблицы, хранящей некоторые «опорные» элементы основной таблицы – как правило, равноотстоящие друг от друга.
Задачи на поиск.
Поиск в циклическом списке
Предположим, что упорядоченная таблица хранится в виде некоторого циклического списка с двумя внешними указателями — table и other. Указатель table всегда указывает на узел, содержащий запись с наименьшим ключом. Указатель other первоначально равен указателю table, но каждый раз, когда выполняется поиск, он переустанавливается так, чтобы указывать на запись, которая извлечена. Если поиск был неудачным, то указатель other переустанавливается так, что он указывает на table. Напишите программу, которая принимает входную информацию TABLE, OTHER и KEY, реализует этот метод, переустанавливает переменную OTHER, как было описано, и устанавливает переменную SEARCH так, чтобы указывать на извлеченную запись или на некоторый пустой указатель, если поиск был неудачным.
Поиск в двусвязном списке
Рассмотрим некоторую упорядоченную таблицу, представленную как массив или как список с двумя связями, так что поиск в данной таблице может быть осуществлен последовательно вперед или назад. Предположим, что некоторый указатель р указывает на последнюю, успешно извлеченную запись. Поиск всегда начинается с записи, на которую указывает р, но он может продолжаться в любом направлении. Напишите подпрограмму для извлечения записи с ключом key и соответствующей модификации р для массива и для списка с двумя связями. Сравните число сравнений ключа для случаев успешного и неудачного поиска с методами из упражнения 4, где таблица может просматриваться только в одном направлении, но процесс просмотра может начинаться в одной из двух точек.
Хеширование таблиц и способы разрешения коллизий
Разрешение коллизий хеширования методом открытой адресации
Напишите программу, реализующую данный метод.
Разрешение коллизий хеширования методом цепочек
Напишите программу, реализующую данный метод.
Метод перемещения в начало для массива
Напишите программу, реализующую данный метод.
Метод перемещения в начало для списка
Напишите программу, реализующую данный метод.
Метод транспозиций для массива
Напишите программу, реализующую данный метод.
Метод накопления группы запросов
Напишите программу, реализующую данный метод.
3.1.3.5.10. Индексно – последовательный поиск
Напишите программу, реализующую данный метод.
Задачи на деревьях
Представление предметного указателя
Предметный указатель учебника состоит из упорядоченных по алфавиту основных терминов, каждый из которых сопровождается множеством номеров страниц и множеством подтерминов. Подтермины печатаются на следующих за основным термином строках: они упорядочены по алфавиту внутри основного термина. Каждый подтермин сопровождается множеством номеров страниц.
Удаление из дерева бинарного поиска
Приведем теперь алгоритм, который удаляет узел с ключом key из дерева бинарного поиска, после чего это дерево остается опять же деревом бинарного поиска. Всего возможны три случая. Если удаляемый узел не имеет потомков, то он может быть удален без перестройки дерева (рис. 3.13, а)
Задачи на множествах
Выбор двух точек для наименьшего отличия подмножеств
Из заданного множества точек на плоскости выбрать две различные точки так, чтобы количества точек, лежащих по разные стороны прямой, проходящей через эти две точки, различались наименьшим образом.
Окружность с наибольшим числом точек заданного на плоскости множества
Определить радиус и центр окружности, на которой лежит наибольшее число точек заданного на плоскости множества точек.