Дискретный анализ ← ЛабораторныеЛабораторная работа №2

Словарь

Необходимо создать программную библиотеку, реализующую указанную структуру данных, на основе которой разработать программу-словарь. В словаре каждому ключу, представляющему из себя регистронезависимую последовательность букв английского алфавита длиной не более 256 символов, поставлен в соответствие некоторый номер, от 0 до 264 - 1. Разным словам может быть поставлен в соответствие один и тот же номер.

Программа должна обрабатывать строки входного файла до его окончания. Каждая строка может иметь следующий формат:

  • + word 34 — добавить слово «word» с номером 34 в словарь. Программа должна вывести строку «OK», если операция прошла успешно, «Exist», если слово уже находится в словаре.
  • - word — удалить слово «word» из словаря. Программа должна вывести «OK», если слово существовало и было удалено, «NoSuchWord», если слово в словаре не было найдено.
  • word — найти в словаре слово «word». Программа должна вывести «OK: 34», если слово было найдено; число, которое следует за «OK:» — номер, присвоенный слову при добавлении. В случае, если слово в словаре не было обнаружено, нужно вывести строку «NoSuchWord».
  • ! Save /path/to/file — сохранить словарь в бинарном компактном представлении на диск в файл, указанный параметром команды. В случае успеха, программа должна вывести «OK», в случае неудачи выполнения операции, программа должна вывести описание ошибки (см. ниже).
  • ! Load /path/to/file — загрузить словарь из файла. Предполагается, что файл был ранее подготовлен при помощи команды Save. В случае успеха, программа должна вывести строку «OК», а загруженный словарь должен заменить текущий (с которым происходит работа); в случае неуспеха, должна быть выведена диагностика, а рабочий словарь должен остаться без изменений. Кроме системных ошибок, программа должна корректно обрабатывать случаи несовпадения формата указанного файла и представления данных словаря во внешнем файле.

Для всех операций, в случае возникновения системной ошибки (нехватка памяти, отсутствие прав на запись и т.п.), программа должна вывести строку, начинающуюуся с «ERROR:» и описывающую на английском языке возникшую ошибку.

Пример

Входной файл Выходной файл
+ a 1
+ A 2
+ aa 18446744073709551615
aa
A
- A
a
OK
Exist
OK
OK: 18446744073709551615
OK: 1
OK
NoSuchWord
Входной файл Выходной файл
+ abcd 21
abcd
bcde
! Save /dict
! Save dict
+ bcde 32
bcde
! Load dict
bcde
OK
OK: 21
NoSuchWord
ERROR: Couldn't create file
OK
OK
OK: 32
OK
NoSuchWord

Упрощенный вариант

Реализовать декартово дерево с возможностью поиска, добавления и удаления элементов.

Тип ключей и значений, а также формат входных и выходных данных такой же, как в обычных вариантах, команд !Save и !Load в тестах нет.

Библиотеку в упрощенном варианте делать необязательно, программа может состоять из одного исходника. Решение отправляется в письме с темой da:20

Варианты задания

Различия вариантов заключаются только в используемых структурах данных:

  1. АВЛ-дерево.
  2. Красно-чёрное дерево.
  3. PATRICIA.
  4. B-дерево.