Методические указания алгоритмы и структуры данных. Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606

• Название: Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606
• Анкор: Методические указания алгоритмы и структуры данных
• Дата: 03.10.2019
• Размер: 429.85 Kb.
• Имя файла: task_180930.docx
• Тип: Методические указания; #88422
• страница: 6 из 8

5. ПОДДЕРЖКА ОБРАБОТКИ ИСКЛЮЧИТЕЛЬНЫХ СИТУАЦИЙ

Механизм исключительных ситуаций предоставляет пользователю возможность контроля за ходом выполнения программы и механизм нейтрализации возможных ошибок. Главное в этом механизме — поддержка действий по нейтрализации последствий события, препятствующего продолжению нормальной работы. Очень часто исключительная ситуация — это не ошибка, а просто исчерпание какого-то ресурса, например, доступной памяти или времени ожидания сигнала или даже один из предусмотренных вариантов завершения процесса. Механизм используется, если ситуация не может быть разрешена в той точке, где была выявлена, и требует перехода на более высокий уровень, с завершением каких-то активных функций и освобождением ресурсов.

Для задействования механизма особых ситуаций в программе нужно проделать следующее:

— обнаружив в программе место, где особая ситуация может возникнуть, надо придумать для неё уникальное название, например My_Error, и объявить соответствующий класс ошибок, возможно, пустой:

class My_Error {};

— в точке программы, в которой обнаружена особая ситуация, поместить утверждение

throw My_Error( );

Это утверждение создаёт объект класса My_Error. Если в объекте предусмотрены поля для данных, через них можно передать информацию обработчику ошибок: аргумент утверждения throw — это конструктор объекта;

— точку вызова функции, которая может создать исключения, нужно поместить в блок контроля, за которым следуют обработчики особых ситуаций:

try{ //начало блока контроля;

вызов функции, которая может создать особую ситуацию

(содержит утверждения throw My_Error);

}

catch (My_Error)

{ обработка особой ситуации }

Предложение catch размещается на том уровне, где обработка ситуации My_Error возможна. Если нужно обрабатывать несколько различных ошибок, после блока try последовательно размещаются соответствующие обработчики. При возникновении любой особой ситуации в блоке try его работа прерывается: происходит принудительный выход из всех функций, которые были активны в точке особой ситуации, и вызов деструкторов для всех созданных при этом объектов, как это происходит при выходе из блока (области видимости). Этот процесс называется раскруткой стека: стек возвращается в состояние, в котором он был при входе в блок try.

Далее просматриваются блоки catch в том порядке, в каком они объявлены. Как только обнаруживается блок обработки ошибок нужного типа, управление передаётся ему. Остальные блоки catch не используются.

Если же выполнение блока try завершилось успешно, все блоки catch после него игнорируются.

Если для некоторого типа ошибки не обнаружено соответствующего блока catch, программа завершается аварийно. Чтобы этого избежать, последним в цепочке можно разместить блок catch(…), перехватывающий ошибки любого типа.

Как только подходящий блок catch будет вызван, особая ситуация будет считаться обработанной, даже если этот блок пуст. Однако чаще всего в него помещают выдачу на экран или в специальный файл (журнал) содержательного сообщения об ошибке. Возможно также одно из следующих действий:

— устранение причины ошибки (уменьшение запроса на выделение памяти, отказ от обработки несуществующего или испорченного файла и т. п.);

— аварийное завершение программы (вызов abort( ));

— перевозбуждение особой ситуации для передачи на следующий уровень иерархии (вызов throw без аргумента).

Подробнее об особых ситуациях и их обработке см. [6, с. 232–256], [7, с. 222–230], [8, с. 399–414].

Правильный выбор уровня для размещения блока контроля позволяет сделать программу безопасной в смысле исключений (см. [14, с. 105–174]). Так, в учебном примере имеется следующая цепочка вызовов функций:

main( ) → screen_refresh( ) → myshape ∷ draw( ) → rectangle ∷ draw ( ) → put_line(a, b) → put_point(x, y) → on_screen(x, y).

Выход точки за пределы буферного массива SCREEN (экрана) выявляется функцией on_screen( ). Блок контроля вокруг вызова этой функции (или вызывающей её put_point) не имеет смысла: на этом уровне ничего, кроме выдачи сообщения об ошибке, сделать нельзя, а такое сообщение можно выдать непосредственно, не прибегая к механизму throw — cath. На уровне main( ) или screen_refresh( ) обрабатывать ошибку поздно, можно только прервать выполнение программы, содержательное сообщение о месте ошибки получить нельзя. В то же время блок контроля внутри функции myshape ∷ draw( ) позволит локализовать ошибку при выводе прямоугольника — контура фигуры myshape и, возможно, попробовать изменить его размер. В общем случае проектирование реакции программной системы на ошибки должно выполняться одновременно с проектированием её самой. Так, в программе, рассмотренной в учебном примере, можно снабдить каждую фигуру автоматически формируемым порядковым номером, значение которого можно выводить как часть сообщения об ошибке «выход за пределы экрана».

Если ошибка выявлена в конструкторе фигуры, фигура не создаётся. Для правильной обработки такой ситуации нужно дополнить библиотеку деструктором для класса shape. Вариант: заменить ошибочную фигуру специальным значком «ошибка», выводимым на картинку.

5.1. Практикум по теме

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

— непопадание точки на экран;

— некорректные параметры при формировании фигуры;

— нехватка места на экране для размещения фигуры.

Можно использовать в качестве базы исключений стандартное исключение exception. Aргумент его конструктора — строка сообщения об ошибке. В блоке catch эта строка может быть получена вызовом функции-члена what( ).

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

Протестировать исключительные ситуации, результаты эксперимента поместить в отчёт.

5.2. Требования к отчёту

В отчёте по теме обоснуйте набор и вид классов для фиксации особых ситуаций, место расположения операторов throw и блоков контроля с целью получения безопасного кода.

5.3. Контрольные вопросы

1. Что такое исключительная ситуация при выполнении программы?

2. Как можно выявить исключительную ситуацию?

3. Что можно предпринять в случае, когда исключительная ситуация выявлена?

4. Могут ли в одной программе появляться исключительные ситуации разных типов и если «да», то как их можно различить?

5. В каком месте программы следует поместить обработчик особых ситуаций?

6. Как можно вызвать обработчик особых ситуаций?

7. Можно ли передать в обработчик особых ситуаций какую-либо информацию о произошедшем событии?

8. Можно ли обработать неизвестную особую ситуацию?

9. Можно ли сделать обработчик ситуации пустым?

10. Что можно предпринять, если выяснилось, что для корректной обработки ситуации в данном месте программы у обработчика оказалось недостаточно данных?

11. Если требуется несколько обработчиков особых ситуаций, в каком порядке их следует размещать в программе?

12. Как действуют обработчики в случае, когда никакой особой ситуации не произошло?

13. Как следует размещать блоки контроля, чтобы получить безопасный программный код?

6. ИСПОЛЬЗОВАНИЕ СТАНДАРТНОЙ БИБЛИОТЕКИ ШАБЛОНОВ

Стандартная библиотека шаблонов (STL) поддерживает большинство типовых операций со структурами данных.

В первую очередь понадобятся последовательные контейнеры vector, list и deque и их производные (адаптеры) stack и queue, а также ассоциативные контейнеры map, set, multimap, multiset — для деревьев двоичного поиска и unordered_map, unordered_set, unordered_multimap, unordered_multiset — для хеш-таблиц. Для обработки данных следует использовать возможности библиотеки алгоритмов (algorithm).

Каждому контейнеру соответствует заголовочный файл, который нужно подключать директивой #include.

Контейнеры map и set хранят множества в виде дерева двоичного поиска с автобалансировкой (красно-чёрное дерево). Контейнер set хранит множество ключей, а map — пары <ключ, значение>, причём все ключи в них уникальны. Для множеств с повторениями используются контейнеры multimap и multiset. При просмотре всех этих контейнеров их содержимое выдаётся в виде упорядоченной последовательности (внутренний обход дерева двоичного поиска).

При просмотре unordered контейнеров будет выдана неупорядоченная последовательность ключей.

Возможно много вариантов приспособления контейнеров для работы с последовательностями: использование map (или multimap) вместо set, чтобы хранить вместе с ключами их порядковые номера, комбинирование контейнера для множеств с контейнером последовательностей (vector или forward_list), хранящим итераторы, и т. п.

Конструкторы контейнеров позволяют уже при их объявлении сформировать множество заданной мощности. Для этого достаточно в качестве инициализатора содержимого контейнера использовать датчик случайных чисел.

Всё необходимое для операций с контейнерами можно найти в библиотеке алгоритмов (algorithm). В частности, в ней имеются функции set_union, set_intersection и set_difference, выполняющие объединение, пересечение и вычитание множеств. Функции принимают в качестве аргументов отрезки из двух контейнеров и формируют новый контейнер с результатом. В них реализуется схема слияния, поэтому входные отрезки должны быть упорядочены. Это справедливо по умолчанию для контейнеров set, map и аналогичных. Для unordered_set аналогичные результаты даёт одновременный просмотр двух контейнеров с применением функций проверки наличия и вставки элемента множества в результат. В библиотеке STL имеются функции для выполнения любых операций с последовательностями.

Подробнее см. [7, с. 295–368], [8, с. 623–702], [10, с. 835–962]. Полезно также посмотреть библиотечные файлы в каталоге include компилятора C++: только там содержится исчерпывающая информация о том, какие на самом деле объявляются классы и какие функции-члены они содержат. Информация в литературных источниках, как правило, запаздывает и содержит неточности. Важно и то, что в сообщениях компилятора об ошибках обычно присутствует информация из текстов каталога include, поскольку эти тексты компилируются вместе с программой пользователя. Требуется также знакомство с механизмом шаблонов языка С++.

6.1. Практикум по теме

Переделать программу, составленную при выполнении темы «Последовательности», под использование контейнеров из стандартной библиотеки шаблонов. Для хранения множеств выбрать контейнер подходящего типа (set или unordered_set и т. п.) и доработать его для поддержки операций с последовательностями. Для реализации операций с контейнерами использовать возможности библиотеки алгоритмов. Программа должна реализовывать цепочку операций над множествами в соответствии с заданием по теме 1 (2) и операций с последовательностями — по теме 3. Результат каждого шага цепочки операций выводится на экран.

6.2. Требования к отчёту

В отчёте по теме опишите набор подходящих контейнеров и функции STL, использованные для работы с ними. Приведите результат выполнения цепочки операций для случайного набора данных заданной мощности. Оцените предполагаемую временную сложность выполнения цепочки операций.

6.3. Контрольные вопросы

1. Что такое стандартный контейнер библиотеки STL? Чем он отличается от обычного объекта?

2. Какой стандартный контейнер можно считать наиболее подходящим для работы с множествами?

3. Можно ли использовать стандартные контейнеры для множеств, на которых не определено отношение полного порядка?

4. Существуют ли ограничения на применение стандартных алгоритмов двуместных операций над множествами в контейнерах?

5. Можно ли реализовать двуместную операцию над множествами в контейнерах без применения стандартного алгоритма?

6. Можно ли выполнять операции над последовательностями для множеств, хранящихся в стандартном контейнере?

7. Можно ли обеспечить поддержку произвольных последовательностей в контейнере для множеств?

8. Какова ожидаемая временная сложность при выполнении стандартным алгоритмом операции объединения двух множеств в стандартных контейнерах set?