====== Вариант 5.1. Иерархическое файловое хранилище ======
[[:courses:algorithms_structures:cw_2026:grade5:start|Все варианты на «Отлично»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
Уровень: **Отлично**.
===== Постановка задачи =====
Каталоги объединяют файлы, text — содержимое текстового файла одним токеном. Права доступа и системные вызовы ОС не моделируются.
Разработайте модель иерархического хранилища в оперативной памяти. В нём есть каталоги и файлы с небольшим текстовым содержимым. Необходимо создавать, искать, удалять и перемещать объекты. Работа с настоящими файлами операционной системы не требуется.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
===== Данные и начальное состояние =====
* ''path'', ''src'', ''dst'' — абсолютные пути: ''/'' либо ''/name/.../name''. Компоненты соответствуют общему формату токена.
* Пустые компоненты, повторные разделители, завершающий разделитель (кроме корня), компоненты . и .. запрещены: ''Error: INPUT''.
* Длина пути в команде не более 1024 символов; глубина не более 64 компонентов. Превышение длины — INPUT, глубины — RANGE. Допустимые сценарии гарантируют, что после успешного перемещения полные пути всех объектов также остаются в этих пределах; отдельная ошибка для нарушения этой гарантии не требуется.
* ''text'' — непустой токен содержимого. Сумма длин имён и содержимого текущих объектов не более 10000000.
* Корневой каталог ''/'' существует с начала запуска. Других объектов первоначально нет. Общий предел числа объектов включает корень.
===== Операции =====
^ Команда ^ Действие ^ Ответ ^
| ''MKDIR path'' | Создать каталог по полному пути; родитель должен существовать и быть каталогом. | OK; занятый путь — Error: EXISTS |
| ''PUT path text'' | Создать файл либо заменить содержимое файла. Родитель должен существовать и быть каталогом. | OK; если по пути каталог, Error: STATE |
| ''GET path'' | Прочитать файл. | VALUE text; объект отсутствует — NONE; это каталог — Error: STATE |
| ''LS path'' | Получить непосредственных детей каталога по возрастанию их имён. | ITEMS k, затем строки D name для каталогов или F name для файлов; файл — Error: STATE |
| ''RM path'' | Удалить объект и всё его содержимое, включая вложенные каталоги. | OK |
| ''MV src dst'' | Переместить объект src по новому полному пути dst, в том числе переименовать. Родитель dst должен существовать; dst должен быть свободен. | OK; занятый dst — Error: EXISTS |
| ''FIND name'' | Найти все файлы и каталоги с точным именем name во всём хранилище, кроме корня. | ITEMS k, затем полные пути лексикографически |
===== Правила выполнения и ошибки =====
Для LS/RM/MV отсутствие обязательного объекта либо родителя возвращает NOT_FOUND; для MKDIR/PUT — отсутствие родителя также NOT_FOUND. Если путь проходит через файл, а не каталог, возвращается STATE; GET для такого пути возвращает STATE, а не NONE. GET возвращает NONE только если при корректном проходе недостаёт компонента.
RM и MV корня возвращают STATE. Перемещение каталога в самого себя или своего потомка запрещено. При ''MV /a /a'' существующий dst даёт EXISTS; для свободного dst внутри src — STATE. Предварительно проверяются src и родитель dst слева направо, затем занятость dst, затем запрет перемещения внутрь себя. Корень является своим существующим родителем только для проверки PUT/MKDIR по пути /; MKDIR / даёт EXISTS, PUT / text — STATE.
LS упорядочивает файлы и каталоги вместе по ASCII-именам, без группировки по типу; сам запрошенный каталог не выводится. FIND сравнивает точное имя последнего компонента пути, а не подстроку полного пути.
Файлы и каталоги одного родителя не могут иметь одинаковые имена. FIND и LS не изменяют данные. Содержимое и потомки при MV сохраняются. Неудачное перемещение ничего не меняет.
Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.
===== Требования к эффективности =====
Пусть h — число компонентов пути, s — максимальное число детей одного каталога, L — максимальная длина компоненты. Поиск по пути, MKDIR, PUT и GET — не хуже O(h·L·log(s+2)); LS допускает дополнительно O(k·L·log(k+2)) для вывода. Для MV допускается O(h·L·log(s+2) + rL), где r — число перемещаемых объектов; RM — O(h·L·log(s+2) + rL). FIND допускает полный просмотр и сортировку найденных путей. Память пропорциональна числу объектов и суммарной длине их данных; все полные пути можно формировать при выводе. Решение не должно при обычном поиске пути перебирать всё хранилище.
В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.
===== Формат ввода и вывода =====
Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:
Course work for option 5.1, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
===== Примеры =====
==== Пример 1. Создание, перенос и поиск ====
Ввод:
1
7
MKDIR /a
PUT /a/x hello
MKDIR /b
MV /a/x /b/y
LS /b
GET /b/y
FIND y
Вывод:
Course work for option 5.1, created by Ivan Ivanov.
OK
OK
OK
OK
ITEMS 1
F y
VALUE hello
ITEMS 1
/b/y
==== Пример 2. Рекурсивное удаление ====
Ввод:
1
6
MKDIR /a
MKDIR /a/b
PUT /a/b/x data
RM /a
LS /
GET /a/b/x
Вывод:
Course work for option 5.1, created by Ivan Ivanov.
OK
OK
OK
OK
ITEMS 0
NONE
==== Пример 3. Неудачное перемещение сохраняет объекты ====
Ввод:
1
6
MKDIR /a
PUT /a/x data
MV /a /a/sub
GET /a/x
RM /
LS /a
Вывод:
Course work for option 5.1, created by Ivan Ivanov.
OK
OK
Error: STATE
VALUE data
Error: STATE
ITEMS 1
F x