+ iNum*REHASH1% REHASH2)
% (HASH_MAX - HASH_MIN + 1) + HASH_MIN;
if (result < HASH_MIN)
result = HASH_MIN;
returnresult;
}
программа идентификатор произвольный
Рисунок 1. Блок-схема хэш-функции
Если при заполнении таблицы идентификаторов после прохождения идентификатора через хэш-функцию произойдет коллизия, программа пропустит тот же идентификатор через хэш-функцию, но при этом iNum будет увеличен на степень. Этот процесс не закончится, пока идентификатор не будет записан в таблицу идентификаторов.
Таблица идентификаторов реализована в виде статического массива размером (HASH_MAX-HASH_MIN).
При поиске идентификатора, идентификатор, который мы ищем, пройдет ту же процедуру, что при заполнении и при встрече точно такого же идентификатора программа выдаст положительный результат («Идентификатор найден»), иначе, при сравнении идентификатора с пустой строкой, программа выдаст отрицательный результат («Идентификатор не найден») и прекратит поиск.
Рисунок 2. Участок блок-схемы записи в таблицу идентификаторов методом рехэширования с помощью произведения
Рисунок 3. Участок блок-схемы поиска идентификатора методом рехэширования с помощью произведения
Метод бинарного дерева
При помещении идентификатора в таблицу, идентификатор сравнивается методом сравнения строк с идентификатором в текущем узле дерева. Если текущий идентификатор меньше идентификатора, который уже находится в дереве, то он кладётся в левую ветвь, иначе в правую, при условии, что они свободны, иначе, если эти ветви заняты, идет ниже по дереву.
Рисунок 4. Блок-схема функции записи в таблицу идентификаторов методом бинарное дерево
При поиске идентификатора идентификатор, который мы ищем, пройдет ту же процедуру, что при заполнении, и при встрече точно такого же идентификатора программа выдаст положительный результат («Идентификатор найден»), иначе при сравнении идентификатора с пустой строкой, программа выдаст отрицательный результат («Идентификатор не найден») и прекратит поиск.
Рисунок 5. Блок-схема функции поиска идентификатора методом бинарное дерево
Таблица 3. Таблица имен переменных
|
Имя переменной |
Тип переменной |
Значение переменной |
|
|
HASH_MIN |
int |
Минимальное значение хэш-функции |
|
|
HASH_MAX |
int |
Максимальное значение хэш-функции |
|
|
REHASH1 |
int |
Переменная для рехэширования |
|
|
REHASH2 |
int |
Переменная для рехэширования |
|
|
aMap |
struct |
Таблица идентификаторов метод рехэширование с помощью произведения |
|
|
bMap |
struct |
Таблица идентификаторов метода бинарное дерево |
|
|
aallCount |
int |
Всего сравнений метод рехэширование с помощью произведения |
|
|
ballCount |
int |
Всего сравнений метода бинарное дерево |
|
|
aMidCount |
int |
Среднее число сравнений метод рехэширование с помощью произведения |
|
|
bMidCount |
int |
Среднее число сравнений метода бинарное дерево |
|
|
vh |
int |
Результат хэш-функции |
|
|
ss |
string |
Исходные данные |
Организация интерфейса пользователя
Кроме перечисленных выше модулей необходим еше модуль, обеспечивающий интерфейс с пользователем. Этот модуль должен реализовать графическое окна - интерфейс в стиле Windowsна основе пакета QtCreator. Oн обеспечивает интерфейссредствами Graphical User Interface (GUI) в ОС типа Windows на основе стандартных органов управления из системных библиотек ОС.
Кроме описания интерфейсной формы и ее органов управления модуль организации пользовательского интерфейса содержит переменные (aallCount, ballCount, aMidCount, bMidCount), служащие для накопления статистических результатов по мере выполнения и поиска идентификаторов в таблицах, и также функцию для отображения накопленной статистической информации на экране.
Интерфейсная форма. описаниая в модуле, содержит следующие основные органы управления:
· поле ввода имени файла (EditFile),
· кнопка выбора имени файла из каталогов файловой системы (BtnFile),
· многострочное поле для отображения прочитанного файла (ListIdents);
· поле ввода имени искомого идентификатора (EditSearch),
· кнопка для поиска введенного идентификатора (BtnSearch), этой кнопкой однократно вызывается процедура поиска (SearchStr);
· кнопка автоматического поиска всех идентификаторов (BtnAHSearch) - этой кнопкой процедура поиска идентификаторов (SearchStr) вызывается циклически для всех считанных из файла идентификаторов (для всех, перечисленных в поле ListIdents);
· кнопкаa сброса накопленной статистической информации (BtnReset):
· поля для отображения статистической информации:
· кнопка завершения работы c программой (BtnExit).
Внешний вид этой формы приведен на рис. 6.
Рисунок 6. Интерфейсная форма программы
Литература
1. Системное программное обеспечение. Лабораторный практикум / Молчанов А.Ю. - СПБ.: Питер, 2005. - 284 с.:ил.
2. Алгоритмы: построение и анализ / Т. Кормен [и др.] - М.: Вильямс, 2005. -1296 с.