Группа 1201. II семестр. Терминальное задание №4 (архивация, разбор выражений)
Для сдачи задания необходимо выполнить 2 задачи. Все задачи из этого раздела должны решаться за приемлемое время для тестов, что прилагаются к заданию. Тесты можно найти на странице http://ccfit. *****/~den Дополнительную информацию можно найти на странице http://iclub. *****/~andy/
4-1. Калькулятор
Необходимо написать калькулятор, позволяющий производить следующие арифметические действия:
- +,-,/,* () sin, cos, exp ^ (возведение в степень)
Программа должна получать на вход файл input. txt, содержащий набор арифметических выражений (каждое выражение на новой строке). На выходе программы выдает результат вычисления заданного арифметического выражения (вещественные числа - с точностью до 2-й цифры) и выражение, записанное в польской записи (через 3 пробела). Токены польской записи выводятся через пробел, все числа выводятся в вещественном формате (до 2-го знака).
Пример:
input. txt
2-3*3
4*(2-9)
sin(2)+2
output. txt
-7 2* -
00 - *
2sin 2.00 +
Если не задан входной файл, то программа переходи в консольный режим и позволяет вводить выражения из консоли. После ввода выражения и нажатия «Enter» программа показывает результат и выражение в формате обратной польской записи.
4-2. Телефонная база данных
Реализовать телефонную базу данных с операциями:
Вставки в БД. int Insert(Card _person); Удаления из БД. int Delete(char * _name) или int Delete(char * _phone) в зависимости от индекса. Поиск. Поиск осуществлять по ключу для конкретного значения (одно выходное значение), а также для значений в промежутке (несколько значений с возможностью последовательного выбора записей.Card Search(char * _name) или Card Search(char * _phone)
CardArray Search(char * _StartName, char * _StopName).
Здесь возможна реализация такой абстракции как курсоры:
Cursor Search(char * _name)
Cursor Search(char * _startName, char * _stopName);
с дополнительными функциями:
Cursor Next(Cursor _cursor)
Card GetValue(Cursor _cursor).
В данном задании необходимо учитывать, что добавление и поиск данных осуществляется прямо в файле, т. к. база должна сохранять большое кол-во записей (сотни тысяч). Нельзя вытаскивать всю базу в оперативную память и производить поиск внутри нее.
Для быстрого поиска необходимо корректно создавать и поддерживать файл (файлы) индексов, нельзя организовывать последовательный поиск данных в файле. Индексы создаются на основе B-tree или расширяемого хэширования (что давалось на лекции). Все записи имеют уникальные ключи (нельзя завести 2 человек с одинаковым именем или одинаковым номером телофона).
Реализация курсоров остается на усмотрение выполняющего задание.
Замечания:
Реализация страниц базы данных, очевидно через сегментированный файл, т. е. файл условно разделённый на странички. Желательна реализация операций чтения-записи-добавления страниц с возможностью кеширования. Желательна поддержка нескольких индексов (по именам и телефонам).4-3. Архивация по методу Хаффмана
Необходимо реализовать возможность архивации бинарных/текстовых данных по методу Хаффмана. Набор команд, обрабатываемых программой, перечислен в таблице:
Команда | Действие |
myarchiver. exe с myfile. txt | Заархивировать файл myfile. txt в файл myfile. txt. haf, созданный в текущей (рабочей) директории. Файл myfile. txt не удалять. |
myarchiver. exe с myfile1.txt myfile2.txt myfile3.txt | Заархивировать файлы myfile1.txt, myfile2.txt, myfile3.txt в файл myfile. txt. haf, созданный в текущей (рабочей) директории. Файл myfile. txt не удалять. Т. е. архиватор должен поддерживать возможность архивирования нескольких файлов. |
myarchiver. exe x myfile. txt. haf | Разархивировать файл myfile. txt. haf. Разархивированные файлы (файл) создавать в текущей (рабочей) директории. Файл myfile. txt. haf удалить. |
Необходимо добиться максимальной скорости сжатия, чтобы файлы в 2-5 мегабайт могли архивироваться/разархивироваться без задержек.
Дополнительную информацию о методе Хаффмана можно найти на странице: http://ccfit. *****/~den/help/other/Haffman. htm
