В данной программе применяется хеш-функция, составленная из двух первых букв исходного английского слова.
Программная реализация алгоритмов: процедуры и функции.
Конструктор объекта TWordList
constructor Create (FileName: string);
осуществляет загрузку из файла dict. txt базы словаря. В каждой строке этого текстового файла находится английское слово, за которым следует пробел, а далее до конца строки. При загрузке осуществляется сортировка элементов массива и построение хеш-таблицы.
Деструктор объекта
destructor Done;
осуществляет освобождение зарезервированной памяти и закрытие файла dict. txt, если он был успешно открыт ранее.
Процедура
procedure SortWords;
реализует сортировку элементов в массиве слов с переводами по значению исходного английского слова.
Процедура
procedure CreateIndex;
осуществляет формирование хеш-таблицы. В качестве хеш-функции выступают значения двух первых букв исходного английского слова.
Функция
function GetTranslation (s: string): string;
осуществляет поиск в массиве элемента с ключом s, используя при этом хеш-таблицу. Блок-схема функции приведена в приложении.
Функция
function TestTranslation (s: string): Integer;
осуществляет поиск элемента в массиве по ключу без использования хеш-таблицы и предназначена для оценки времени работы программы.
Интерфейс пользователя.
Программа имеет текстовый интерфейс. После запуска программы появляется строка подсказки, предлагающая найти перевод слова, замерить быстродействие программы или покинуть программу.
При вводе пользователем слова будет осуществлен его поиск в базе словаря и, в случае успеха, на экран будет напечатан перевод. Если же слово не будет обнаружено в базе словаря, то об этом также будет выведено сообщение.
При нажатии на кнопку «Enter» непосредственно после появления строки подсказки происходит выход из программы.
При вводе символа «*» в ответ на запрос пользовательского слова будет выполнено тестирование быстродействия программы и на экран будет выдано время работы основных этапов алгоритма обработки пользовательского запроса.
Ограничения по памяти.
Выбранные структуры представления данных и компилятор Турбо Паскаль 7.0 налагают следующие ограничения на количество вводимых слов, длину исходных английских слов и их переводов. Для длины слова установлена верхняя граница в 20 символов, для длины перевода — в 200 символов. Так как размеры наибольшего динамически выделяемого блока в куче в среде Турбо Паскаль 7.
0. составляют не более 655 360 байт, в словарь можно добавить не более 2950 слов.
Заключение
.
В данной работе осуществлена программная реализация электронного англо-русского толкового словаря. Программа разработана на основе широко применяемой для решения подобных задач методики поиска в массиве отсортированных элементов с использованием хеширования. Выбранные алгоритмы и структуры описания типов данных позволяют достичь, с одной стороны, эффективности программной реализации, а с другой стороны, наглядности и простоты программного кода.
Н. Вирт. Алгоритмы и структуры данных. С.-Петербург: Невский диалект, 2001.
И.Ф. Бабалова. Язык Турбо-Паскаль. Учебное пособие. М.: МИФИ, 1991
В. Г. Давыдов. Программирование и основы алгоритмизации. «Высшая школа», 2003.
О. Козлов, Ю. Аляев. Алгоритмизация и языки программирования Pascal, C++, Visual Basic, «Финансы и статистика» · 2002 г.
Д. Э. Кнут. Искусство программирования. Т. 2. — 3-е изд. М.: Вильямс, 2002;2004.
В.И. Грызлов, Т. П. Грызлова. Турбо Паскаль 7.
0. М.: «ДМК», 1999.
Приложение 1. Блок-схема программы.
Приложение 2. Блок-схема алгоритма поиска слова в массиве: функция GetTranslation.
Выбор пользователя
Ввод новой информации пользователем
Обработка введенных данных
Добавление введенных данных к хранимой информации
Пользовательский запрос на выдачу информации
Поиск требуемой информации в хранимых данных
Выдача результатов обработки запроса
Искомое слово: word
i := Index[word[1], word[2]]
word = WordArray[i]. source?
word < WordArray[i]. source?
i := i + 1
Результат функции:
WordArray[i].
Translation
Результат функции:
пустая строка Да
Да
Нет
Нет
Начало
Ввод слова пользователем
Вывод приглашения на ввод
Введено пустое слово?
Поиск перевода в словаре
Перевод найден?
Выдача перевода
Выдача сообщения об отсутствии слова в словаре
Выход
да
нет
нет
да
Формирование индексирующего массива
Считывание и сортировка словаря
