ПК 2102. ПК(2102). П. Г. Колинько пользовательские контейнеры
 Скачать 0.78 Mb.
|
3.6. Практикум по гл. 3Реализовать индивидуальное задание темы «Множества + последовательности» в виде программы, используя свой контейнер для заданной структуры данных (хеш-таблицы или одного из вариантов ДДП), и доработать его для поддержки операций с последовательностями. Для операций с контейнером рекомендуется использовать возможности библиотеки алгоритмов. Программа должна реализовывать цепочку операций над множествами, имеющимися в выражении, взятом по номеру варианта задания из табл. 3.1 с базовым контейнером и операциями с последовательностью из табл. 3.2. Результат каждого шага цепочки операций выводится на экран. Реализация каждой операции должна обеспечивать расширенные гарантии устойчивости к исключениям. 3.6.1. Дополнительные требования к отчетуВ отчете опишите свой контейнер и функции STL, использованные для работы с ними. Приведите результат выполнения цепочки операций для случайного набора данных заданной мощности. Оцените предполагаемую временную сложность выполнения цепочки операций. 3.6.2. Контрольные вопросы1. Что такое стандартный контейнер библиотеки STL? Чем он отличается от обычного объекта? 2. Какой стандартный контейнер можно считать наиболее подходящим для работы с множествами? 3. Можно ли использовать стандартные контейнеры для множеств, на которых не определено отношение полного порядка? 4. Существуют ли ограничения на применение стандартных алгоритмов двуместных операций над множествами в контейнерах? 5. Можно ли реализовать двуместную операцию над множествами в контейнерах без применения стандартного алгоритма? 6. Можно ли выполнять операции над последовательностями для множеств, хранящихся в стандартном контейнере? 7. Можно ли обеспечить поддержку произвольных последовательностей в контейнере для множеств? 8. Какова ожидаемая временная сложность при выполнении стандартным алгоритмом операции объединения двух множеств в стандартных контейнерах set? 9. С какой целью может понадобиться оформить пользовательскую структуру данных как стандартный контейнер? 10. Каков минимально необходимый набор средств для превращения пользовательской структуры данных в полноценный контейнер? 11. Зачем нужны гарантии устойчивости алгоритмов относительно исключений? 12. Почему базовых гарантий устойчивости алгоритма к исключениям может быть недостаточно? 13. В чём заключаются расширенные гарантии устойчивости алгоритма к исключениям и как их можно обеспечить? Таблица 3.1Индивидуальные задания к практикуму по гл. 3.. Операции над множествами
Таблица 3.2 Индивидуальные задания к практикуму по гл. 3. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| № вари- анта | Базовая СД | Дополнительные операции | № вари- анта | Базовая СД | Дополнительные операции |
| 1 | ДДПв | MERGE, EXCL, CHANGE | 18 | АВЛд | CONCAT, EXCL, SUBST |
| 2 | АВЛд | CONCAT, EXCL, MUL | 19 | К-ч-д | MERGE, EXCL, SUBST |
| 3 | 1-2д | EXCL, SUBST, MUL | 20 | ДДПм | CONCAT, SUBST, CHANGE |
| 4 | 2-3д | MERGE, ERASE, SUBST | 21 | 1-2д | MERGE, CONCAT, CHANGE |
| 5 | ДДПм | MERGE, CONCAT, SUBST | 22 | 2-3д | MERGE, CONCAT, MUL |
| 6 | К-ч-д | MERGE, EXCL, SUBST | 23 | ДДП | EXCL, SUBST, CHANGE |
| 7 | ДДП | CONCAT, EXCL, SUBST | 24 | ХТ | ERASE, EXCL, MUL |
| 8 | ХТ | MERGE, ERASE, EXCL | 25 | ДДПв | MERGE, CONCAT, SUBST |
| 9 | ДДП | MERGE, CONCAT, EXCL | 26 | АВЛд | ERASE, EXCL, CHANGE |
| 10 | ДДПм | CONCAT, ERASE, CHANGE | 27 | 1-2д | CONCAT, ERASE, EXCL |
| 11 | 1-2д | CONCAT, SUBST, CHANGE | 28 | ДДПм | EXCL, SUBST, MUL |
| 12 | 2-3д | ERASE, EXCL, SUBST | 29 | ХТ | CONCAT, EXCL, CHANGE |
| 13 | АВЛд | CONCAT, EXCL, SUBST | 30 | К-ч-д | MERGE, CONCAT, EXCL |
| 14 | ХТ | CONCAT, EXCL, CHANGE | 31 | 2-3д | MERGE, EXCL, CHANGE |
| 15 | К-ч-д | MERGE, CONCAT, MUL | 32 | ДДП | CONCAT, EXCL, MUL |
| 16 | ДДПв | ERASE, SUBST, CHANGE | 33 | ХТ | MERGE, CONCAT, ERASE |
| 17 | АВЛд | MERGE, SUBST, MUL | 34 | ДДП | CONCAT, EXCL, SUBST |
Окончание табл. 3.2
| № вари- анта | Базовая СД | Дополнительные операции | № вари- анта | Базовая СД | Дополнительные операции |
| 35 | ДДПв | MERGE, SUBST, CHANGE | 43 | 2-3д | ERASE, EXCL, SUBST |
| 36 | ХТ | CONCAT, ERASE, EXCL | 44 | АВЛд | CONCAT, ERASE, CHANGE |
| 37 | 2-3д | MERGE, CONCAT, CHANGE | 45 | ДДПм | MERGE, ERASE, SUBST |
| 38 | ДДПм | EXCL, SUBST, CHANGE | 46 | ДДПв | MERGE, SUBST, MUL |
| 39 | ДДП | ERASE, EXCL, CHANGE | 47 | 1-2д | MERGE, ERASE, CHANGE |
| 40 | 1-2д | MERGE, CONCAT, ERASE | 48 | К-ч-д | MERGE, SUBST, CHANGE |
| 41 | К-ч-д | ERASE, EXCL, MUL | 49 | ДДП | ERASE, SUBST, CHANGE |
| 42 | ДДПв | MERGE, ERASE, CHANGE | 50 | К-ч-д | MERGE, ERASE, EXCL |
| Примечание: В таблице использованы следующие обозначения: ХТ — хеш-таблица; ДДП — дерево двоичного поиска (без автобалансировки); ДДПв — то же, с хранением в каждом узле высоты поддерева; ДДПм — то же, с хранением мощности поддерева; АВЛд — АВЛ-дерево (с автобалансировкой); К-ч-д — красно-черное дерево (с автобалансировкой); 2–3д — 2–3-дерево (всегда сбалансированное); 1-2д — 1-2-дерево. | |||||
Итератор чтения для просмотра структуры данных или ее части можно реализовать для всех перечисленных выше структур данных. Итератор вставки, обеспечивающий добавление ключей в множество, может без проблем быть реализован только для хеш-таблицы. Указание места вставки для нее игнорируется как совершенно излишнее. Для ДДП вставка без указания места начала поиска может быть выполнена только за логарифмическое время, поскольку корректный поиск места вставки в общем случае должен начинаться от корня дерева. Вставка за константное время возможна, только если итератор вставки укажет для начала поиска места вставки на ключ, вставленный последним. В случае вставки произвольного ключа такое указание приведет к хаосу. Оно допустимо и целесообразно только для вставки упорядоченной последовательности ключей в пустое дерево, как это происходит в двуместных операциях с множествами по схеме слияния. Чтобы форма ДДП такими вставками не искажалась, оно должно быть автобалансирующимся. Чтобы обеспечить двуместную операцию за линейное время с обычным ДДП — без автобалансировки, необходимо помещать результат операции в промежуточный буфер (вектор) и затем восстанавливать дерево из него.
ДДП с хранением в узлах высоты работает аналогично самобалансирующемуся АВЛ-дереву: балансы вычисляются динамически сравнением высот поддеревьев.
Для деревьев с автобалансировкой итератор вставки обеспечивает в качестве точки начала очередного поиска узел, на котором балансировка закончилась. Для этого в нем хранится стек с путем от корня к точке вставки.
ДДП с хранением в узлах мощности поддеревьев само по себе не имеет преимуществ перед обычным ДДП при случайных вставках. Но для такого дерева существует алгоритм вставки в корень. После создания, как обычно, нового узла — листа он с помощью серии вращений пар отец-сын перемешается в корень дерева. При двуместных операциях итератор вставки может выполнять вставку нового узла сразу в корень (за константное время). Дерево получается вырожденным, но по завершении двуместной операции может быть сбалансировано за линейное время, как и обычное ДДП, но без использования дополнительной памяти.
Для 2–3-дерева возможна как схема с автобалансировкой после каждой вставки, так и получение промежуточного списка упорядоченных узлов, из которого по завершении двуместной операции дерево восстанавливается за линейное время без использования дополнительной памяти. Узлы дерева при балансировке не перемещаются, и итераторы на них остаются действительны.
Оптимальный способ дополнения дерева двоичного поиска для обеспечения операций с последовательностями зависит от реализуемого набора таких операций. Например, если требуется доступ к порядковому номеру по значению ключа, оптимальным является хранение номеров в узлах дерева вместе с ключами. Но это означает, что ДДП должно обеспечивать хранение дубликатов ключей, которые могут появиться как результат операции с последовательностью. Снять проблему дубликатов можно присоединением номеров к ключам в операции сравнения. Но такой подход сделает невозможным оперативную замену номеров: ключ со старым номером придется удалять и вставлять заново с новым — за логарифмическое время.
Реализация последовательности в виде вектора итераторов на узлы дерева обеспечивает доступ к ключу по порядковому номеру в последовательности за константное время, а обратную операцию — за линейное. Обход дерева даёт упорядоченную последовательность ключей, а обход вектора — произвольную, что позволяет работать со структурой данных и как с множеством, и как с последовательностью.
Способ обхода выбирается таким образом, чтобы временная сложность двуместной операции получалась линейной. Это легко сделать для хеш-таблицы. Для дерева двоичного поиска следует избегать последовательности случайных вставок с поиском места вставки от корня дерева, поскольку сложность такой последовательности будет O(n log n).