1. Алгоритм работы метода цепочек.

1. Во все ячейки хеш-таблицы поместить пустое значение, таблица идентификаторов пуста, переменная FreePtr (указатель первой свободной ячейки) указывает на начало таблицы идентификаторов; i:=1.

2. Вычислить значение хеш-функции n_i для нового элемента A_i. Если ячейка хеш-таблицы по адресу n_i пустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе – перейти к шагу 3.

3. j:=1, выбрать из хеш-таблицы адрес ячейки таблицы идентификаторов m_j и перейти к шагу 4.

4. Для ячейки таблицы идентификаторов по адресу m_j проверить значение поля ссылки. Если оно пустое, то записать в него адрес из переменной FreePtr и перейти к шагу 5; иначе – j:=j+1, выбрать из поля ссылки адрес m_j и повторить шаг 4.

5. Добавить в таблицу идентификаторов новую ячейку, записать в нее информацию для элемента A_i (поле ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки. Если больше нет идентификаторов, которые надо разместить в таблице, то выполнение алгоритма закончено, иначе – i:=i+1 и перейти к шагу 2.

2. Алгоритм поиска элемента в таблице идентификаторов.

1. Вычислить значение хеш-функции n для искомого элемента A. Если ячейка хеш-таблицы по адресу n пустая, то элемент не найден и алгоритм завершен, иначе – j:=1, выбрать из хеш-таблицы адрес ячейки таблицы идентификаторов m_j.

2. Сравнить имя элемента в ячейке таблицы идентификаторов по адресу m_j с именем искомого элемента A. Если они совпадают, то искомый элемент найден и алгоритм завершен, иначе – перейти к шагу 3.

3. Проверить значение поля ссылки в ячейке таблицы идентификаторов по адресу m_j. Если оно пустое, то искомый элемент не найден и алгоритм завершен; иначе –j:=j+1, выбрать из поля ссылки адрес m_j и перейти к шагу 2.

4. Обработка ошибок

Функция обработки ошибок считает ошибки, пишет сообщение об ошибке и возвращает управление обратно.

5. Драйвер

Драйвер – это управляющая программа, которая необходима для инициализации и запуска всех функций калькулятора.

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

1. Что такое рекурсивная подпрограмма?

2. Какие существуют рекурсивные структуры данных?

3. В чем заключается задача поиска данных в таблице?

4. Что такое таблица идентификаторов?

5. В чем заключается алгоритм Кнута, Мориса и Пратта (КМП-поиск)?

6. В чем заключается алгоритм Боуера и Мура (БМ-поиск)?

7. В чем заключается бинарный поиск?

8. Что представляют собой абстрактные структуры данных и для чего они предназначены?

9. Что такое АТД-cловарь и для чего он используется?

10. Что такое хеширование и хеш-таблица?

11. Что такое хеш-адресация?

12. Что такое коллизия, и в каких случаях происходят коллизии?

13. Какие существуют методы разрешения коллизий?

14. В чем заключается метод цепочек?

15. В чем заключается метод открытой адресации?

16. В чем заключается метод построения таблиц, имеющих форму бинарного дерева?

17. Принципы работы хеш-функций.

18. Что такое рехеширование, и в чем заключается этот метод?

19. Из каких основных частей состоит калькулятор?

20. Что представляет собой программа синтаксического разбора?

21. В чем заключается задача функций ввода и обработки ошибок? Что представляет собой драйвер?