Организация таблиц идентификаторов

Программа №1 Организация таблиц идентификаторов (по книге Молчанова, которая прикреплена отдельным файлом)

Задание необходимо выполнить на C++ в Microsoft Visual Studio 2005, применяя MFC и технологию ООП.

Программа должна считывать идентификаторы из входного файла, размещать их в таблицы с помощью заданных методов (в данном варианте с помощью хэш-адресации) и

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

Для организации таблиц использовать простейшую хэш-функцию, которую разработчик программы должен выбрать самостоятельно (см. примечание ниже). Хэш-функция должна обеспечивать работу не менее, чем с 200 идентификаторами, максимальная длина идентификатора – 32 символа. Способы разрешения коллизий:

1. Рехэширование с использованием псевдослучайных чисел

2. Простое рехэширование

Внешний вид интерфейсной формы для лаб. раб. №1 аналогичен приведённому на стр.37

Разрешено использовать хэш-функцию, приведённую в книге на стр.30:

можно взять функцию, которая будет получать на входе строку, а в результате выдавать сумму кодов первого, среднего и последнего элементов строки. Если строка содержит менее 3-ёх символов, то один и тот же символ будет взят и в качестве первого, и в качестве среднего, и в качестве последнего.

По работе должен быть оформлен отчёт :

описание выбранной хэш-функции;

описание структур данных, используемых для заданных методов организации таблиц идентификаторов (см. стр.31 и первых 2 абзаца стр. 32);

схемы организации таблиц идентификаторов (см. стр. 34);

блок-схема алгритмов поиска в таблицах идентификаторов (описание алгоритма поиска приведено на стр.21-22) ;

текст программы;

анализ эффективности используемых методов организации таблиц идентификаторов и выводы по проделанной работе ( по аналогии с приведёнными на стр.37-38).

Программа №2 Проектирование лексического анализатора. Задание варианта 4 на стр.47; содержание отчета стр.46; внешний вид закладок интерфейсной формы стр.58

Так же, как и первую, работу необходимо выполнить на C++ в Microsoft Visual Studio 2005, применяя MFC и технологию ООП.

Первую работу надо выполнить к 12 мая, а вторую- к 19 мая.