ООП ← ЛабораторныеЛабораторная работа

Шаблоны C++

Задание

Реализовать стуктуру данных согласно варианту и написать простой интерпретатор команд работы с этой стуктурой.

Формат входных данных

Каждая строка содержит одну команду, которая представляет собой однобуквенный код операции и, через табуляцию, аргументы.

Элемент структуры — пара ключ-значение. Структуры должны храниться в стеке. Все операции оперируют структурой с вершины стека.

Тип значения — строка.

Команды:

  • c — создать пустую структуру,
  • k — удалить последнюю созданную структуру,
  • j — слить две последние созданные структуры в одну,
  • a <ключ> <значение> — добавить пару ключ-значение,
  • d <ключ> — удалить по ключу,
  • r — удалить минимальный элемент,
  • t — распечатать минимальный элемент,
  • m <ключ> — изменить ключ у минимального элемента,
  • p — распечатать список пар ключ-значение, содержащихся в последней созданной стуктуре.

Входные данные корректные.

Выходные данные

Программа не должна выводить ничего, кроме того, что указано в задании. Элементы выводятся по одному на строку, значение отделяется от ключа одним символом табуляции.

Ограничения

STL можно пользоваться только для ввода-вывода.

Варианты структуры данных

В скобках указаны операции, которые необходимо реализовать.

  1. Двоичное несбаллансированное дерево (все, кроме r и m).
  2. Биномиальная куча (все, кроме d).
  3. Пирамида на динамическом массиве (все, кроме d).
  4. Леонардова куча (все, кроме d).
  5. Очередь с операцией нахождения минимального элемента (все, кроме d, r и m).

Варианты типов ключей

  1. Целое число со знаком (int).
  2. Строка, не содержащая символов \n и \t.
  3. Неотрицательно число с фиксированной точкой. Целая и дробная часть вмещаются в uint32_t. Примеры: 3.5, 44., .5, 0.0, 0.7.

Варианты:

НомерИмяВариант
1Акмаева Валентина1-1
2Антиох Григорий2-2
3Баерсдорф Иван3-3
4Блохин Андрей4-1
5Каракашов Рустам5-2
6Круглов Владислав1-3
7Монжелес Александр2-1
8Рыжов Александр3-2
9Сныткин Максим4-3
10Стороженко Ярослав5-1
11Сущенко Павел1-2
12Таран Николай2-3
13Шабанов Дмитрий3-1
14Шпарварт Илья4-2
15Штанов Александр5-3
16Герасин Борис1-1
17Данилычев Иван2-2
18Дорожкин Алексей3-3
19Иванов Алексей4-1
20Ильвохин Дмитрий5-2
21Исаев Антон1-3
22Коломейцев Николай2-1
23Кошелевская Александра3-2
24Крайнов Александр4-3
25Муслаев Илья5-1
26Пархоменко Евгений1-2
27Пономарева Алина2-3
28Торцев Александр3-1
29Фролов Александр4-2
30Чеглаков Иван5-3
31Чекмарев Антон1-1
32Аверина Анастасия1-1
33Бондарев Владислав2-2
34Злаказов Андрей3-3
35Зотов Сергей4-1
36Логачёва Елизавета5-2
37Платонов Михаил1-3
38Раца Иван2-1
39Сарычева Анастасия3-2
40Скоблова Анастасия4-3
41Сосулин Егор5-1
42Сухарев Андрей1-2
43Богословский Никита1-1
44Борисова Анна2-2
45Булыгин Андрей3-3
46Горюнов Никита4-1
47Заболотний Евгений5-2
48Каменчук Валерия1-3
49Капустин Николай2-1
50Коренев Александр3-2
51Лунёва Маргарита4-3
52Морозов Илья5-1
53Прохоренко Владимир1-2
54Тимофеев Владислав2-3
55Чистяков Максим3-1
56Калинина Мария1-1
57Дорофеев Артем1-2
58Крайнова Анастасия2-3
59Кучерина Ольга3-1
60Середин Сергей4-2