Алгоритмы и структуры данных

Алгоритмы и структуры данных. Часть 2. Установочная лекция В осеннем семестре предстоит изучение более сложных вопросов, связанных с пользовательскими структурам данных и их применением в алгоритмах. Мы установили, что пользовательскую структуру данных выгодно оформлять как данные особого типа, т.е. объявлять соответствующий класс. Это позволяет решать задачу на более высоком уровне — уровне абстракций, на котором формулируются алгоритмы. Пользовательский тип данных снабжается набором инструментов для манипуляций с ним, соответствующих его природе и препятствующих недопустимым манипуляциям с данными. Более того, на уровне интерфейса, обеспеченного набором функций-членов, скрыта низкоуровневая реализация данных, и можно использовать разные варианты такой реализации, выбирая из них те, которые более всего отвечают специфике задачи. Пример класса с настройкой на предметную область — шаблонный класс. Мы рассматривали примеры шаблонного класса для стека и очереди. Стандартный набор манипуляций с данными шаблонного класса настраивается на заданный пользователем тип, от которого требуется некоторый ограниченный набор свойств, позволяющий такие манипуляции: наличие конструктора по умолчанию, допустимость копирования и т.п. Другой пример рассмотренного взаимодействия классов — дружба. Так, класс «список» объявлялся другом класса «элемент», и все функции-члены класса «список» получали доступ к закрытой части класса «элемент», такой же, как и функции-члены класса «элемент». Отметим, что такой же эффект достигается объявлением типа элемента списка как struct, но внутри определения класса «список». В более сложных проектах приходится объявлять несколько классов, которые часто бывают похожи. Например, проект «база данных деканата» может включать типы «студент», «аспирант», «абитуриент», «стажёр», «иностранец» и т. п. Обработка таких данных может быть сильно упрощена, если выделить во всех классах общие части и собрать их вместе для единообразной обработки. Эта задача решается с помощью иерархии классов. Так, общее свойство всех перечисленных категорий — все они — это личность, имеющая имя. Поэтому создаём общий класс «личность»: class person{ //Личность public: person( ) { } explicit person(const string& name) : name(name) { } void set_name(const string& n) { name = n; } string get_name( ) const { return name; } void info ( ) const { cout ≪ "[person] Имя: " ≪ name ≪ endl; } private: string name; //Имя }; Отметим, что функции вида get/set для закрытых полей — ПЛОХАЯ практика! Если такой доступ нужен, проще сделать поле открытым, например, объявлять person не как class, а как struct. class student : public person { public: student(const string & name, const string & passed) : person(name), passed(passed) { } void info ( ) const { cout ≪ "[Student]Имя: " ≪ get_name ( ) ≪ endl; cout ≪ " сдал курсы: " ≪ passed ≪ endl; } private: string passed; //Перечень курсов }; Производный класс ВИДИТ все члены базового класса, кроме закрытых. Совпадающие имена (info) — СКРЫТЫ в производном классе. Но доступ к последним возможен — через уточнение person ∷ info( ). Скрыто ИМЯ функции, а не сигнатура: скрыты ВСЕ перегруженные функции. Использование: int main( ) { person mark(«Марк»); mark.info( ); student tom(«Том», «Физика, Анализ»); tom.info( ); person p(tom); person& pr = tom; //ссылка на person; варианты инициализации: pr(tom), pr{tom} person* pp = &tom; //указатель на person; варианты: pp(&tom), pp{&tom} p.info( ); //Вызовы функций через ссылку или указатель pr.info( ); pp->info( ); } Результат выполнения кода: [person] Имя: Марк [student] Имя: Том сдал курсы: Физика, Анализ [person] Имя: Том [person] Имя: Том [person] Имя: Том Если student обрабатывается как person, информация о студенте ОТСУТСТВУЕТ. Тем не менее, мы можем: — копировать student в person; — обращаться к student, как к person; — передавать student в функцию, как аргумент person. ВЕЗДЕ, где требуется базовый класс, принимаются его производные классы. Форма наследования: public, protected, private (по умолчанию). Форма наследования модифицирует соответствующим образом имена public базового класса с точки зрения производного. При наследовании public модификаторы доступа базового класса будут такими же и в производном (закрыта только часть private). При наследовании private данные public и protected базового класса становятся private в производном классе. При наследовании protected данные public становятся protected. Конструкторы НЕ наследуются. Производный класс должен иметь свой конструктор. Как видно в примере, он запускает в своём конструкторе конструктор базового класса. Если этого не делать, для базового класса выполнится конструктор по умолчанию. Вариант: сделать доступным специально. using person ∷ person; в классе student. Станет возможным объявление student tom(«Том») в функции main( ). Тот же приём — для скрытых функций, чтобы обеспечить их перегрузку. Виртуальные функции и полиморфные классы class person{ public: //… virtual void info ( ) const { cout ≪ "[person] Имя: " ≪ name ≪ endl; } //… }; class student : public person { public: … void info ( ) const //Если функция виртуальна, вызов зависит от типа объекта { person ∷ info( ); //ф-член д.б. доступна! cout ≪ " сдал курсы: " ≪ passed ≪ endl; } … }; Теперь результат выполнения кода: [person] Имя: Марк [student] Имя: Том сдал курсы: Физика, Анализ [person] Имя: Том [student] Имя: Том сдал курсы: Физика, Анализ [student] Имя: Том сдал курсы: Физика, Анализ Здесь p.info( ); //Производный объект превращается в базовый — СРЕЗКА pp.info( ); //Ссылка на базовый фактически ссылается на производный pp->info( ); //То же — указатель СЛЕДСТВИЕ: один код для базовых и производных классов, реализация СКРЫТА. Явное перекрытие class person{ public: … virtual void info ( ) const { cout ≪ "[person] Имя: " ≪ name ≪ endl; } … }; class student : public person { public: //… virtual void info ( ) //Убрали const, виртуальная функция скрыта { person ∷ info( ); //ф-член д.б. доступна! cout ≪ " сдал курсы: " ≪ passed ≪ endl; } //… }; int main( ) { student tom(«Том», «Физика, Анализ»); person& pr = tom; // варианты: pr(tom). pr{tom} pr.info( ); //Вызывается person∷info( ) } Виртуальности НЕТ из-за несовпадения сигнатур. Спасение: class student : public person { public: … virtual void info ( ) override {…} }; Если сигнатуры не совпадают, компилятор фиксирует ошибку. ВАРИАНТ: final. Это означает, что функция больше не будет перекрыта. Компилятор может оптимизировать её вызов: прямой вместо косвенного. Можно объявить final целый класс, чтобы запретить наследование. override и final — КОНТЕКСТНЫЕ ключевые слова. Контрольная работа 1. Библиотека фигур Рассмотрим аналогичную задачу из области геометрии — составление картинок из геометрических фигур: линий, квадратов, прямоугольников, треугольников и т. п. Фигуры объединяются в картинку совмещением крайних точек (северная точка одной фигуры с южной — другой) и включаются в общий список фигур, используемый для рисования всей картинки. Каждая фигура — это особый пользовательский тип данных, для которого должны быть определены функции рисования, перемещения и выдачи крайних точек, необходимых для сборки. Но для обеспечения единообразия фигур необходимо сделать их производными от класса «фигура», обладающего всем набором необходимых свойств. Проблема в том, что можно нарисовать линию или прямоугольник, но нельзя нарисовать фигуру вообще. Задача решается с помощью чисто виртуальных функций (без тела), смысл которых – задать общую сигнатуру и перекрываться единообразным способом в производных классах. Единственное действие, доступное для выполнения на уровне класса «фигура» — это включение фигуры в список для рисования, которое обеспечивает конструктор класса «фигура». struct shape { // Виртуальный базовый класс "фигура" static list shapes;// Список фигур (один на все фигуры!) shape( ) { shapes.push_back(this); } //Фигура присоединяется к списку virtual point north( ) const = 0; //Точки для привязки — северная virtual point south( ) const = 0; // южная virtual point east( ) const = 0; // восточная virtual point west( ) const = 0; // западная virtual point neast( ) const = 0; // северо-восточная virtual point seast( ) const = 0; // юго-восточная virtual point nwest( ) const = 0; // северо-западная virtual point swest( ) const = 0; // юго-западная virtual void draw( ) = 0; //Рисование virtual void move(int, int) = 0; //Перемещение virtual void resize(int) = 0; //Изменение размера }; Класс с чисто виртуальными функциями является абстрактным классом. Невозможно создавать данные этого типа, но можно использовать класс как базовый для создания конкретных типов, в которых все чистые виртуальные функции должны быть перекрыты. Использование единого интерфейса позволяет реализовать следующую функцию рисования картинки: void shape_refresh( ) // Перерисовка всех фигур на экране { screen_clear( ); for (auto p : shape :: shapes) p->draw( ); //Динамическое связывание!!! screen_refresh( ); } Функция просматривает список фигур shapes, состоящий из указателей на имеющиеся фигуры, и для каждой из них вызывает свою функцию рисования. Указатель на базовый класс фактически указывает на какой-то из производных, и именно для последнего вызывается функция рисования — для каждого своя. Этот процесс называется поздним, или динамическим связыванием. Он выполняется не при компиляции, а при выполнении программы. Аналогичный механизм работает при присоединении одной фигуры к другой: void up(shape& p, const shape& q) // поместить p над q { //Это ОБЫЧНАЯ функция, не член класса! Динамическое связывание!! point n = q.north( ); point s = p.south( ); p.move(n.x - s.x, n.y - s.y + 1); } Фигура p помещается над фигурой q. Для фигуры p вычисляется северная точка, для q — южная, после чего для фигуры p вызывается функция move, перемещающая её на разность координат вычисленных точек, тем самым совмещая их. Дополнительная единица добавляется к разности ординат, чтобы фигуры примыкали, а не накладывались. Некоторые фигуры перед размещением в картинке можно поворачивать вправо или влево, другие – отражать относительно горизонтальной или вертикальной оси. Для единообразия этих действий такие фигуры делаются производными от классов «отражаемая» — reflectable, или «вращаемая» — rotatable. Эти два промежуточных класса наследуют класс shape виртуально (virtual). Это означает, что обе ветви наследования приводят к одному и тому же экземпляру класса shape, т.е. фигура будет включена в список для рисования только один раз. Индивидуальное задание предусматривает разработку класса для включаемой в картинку дополнительной фигуры. Для этой фигуры следует найти место в имеющейся иерархии классов. Самым привлекательным является вариант наследования от прямоугольника — реального класса с полным комплектом функций-членов. Производный класс должен переопределить только те из них, которые не подходят: рисование, некоторые крайние точки и т.п. Например, для прямоугольника с крестом необходимо перекрыть только функцию draw(), добавив в неё рисование ещё двух линий, соединяющих крайние точки прямоугольника. Обратите внимание на то, что конструкторы линии и прямоугольника всегда обеспечивают корректный результат, независимо от соотношения исходных данных. В некотором смысле это избыточность, но о ней не следует забывать для пользовательской фигуры. Например, квадрат — частный случай прямоугольника. Можно ли его определить следующим образом? class square : public regtangle { public: square(point a, point b) : regtangle(a, b) {} }; Очевидно, что нет. Квадрат будет получаться, если пользователь сам подберёт соответствующие координаты точек. Вместо этого следует задавать квадрат точкой и размером. Тоже самое можно утверждать для прямоугольного треугольника , ромба, трапеции и т.д. Опорные точки для базового прямоугольника, если нужны, должны вычисляться. При базировании от shape (напрямую или через reflectable/rotatable) нужно переопределить все чистые виртуальные функции. Некоторые (ненужные) достаточно просто объявить. Попытка вызова объявленных, но не определённых функций обнаруживается только на этапе сборки приложения. Для сборки рисунка с расположением новой фигуры в заданных позициях может понадобиться написание соответствующих функций присоединения, аналогичных рассмотренной выше функции up. Такие функции будут отличаться только выбором пар крайних точек, которые нужно совместить. Альтернативой присоединению является включение. Таким способом в фигуру myshape включены линии, образующие глаза и рот. Размеры и место расположения этих добавок на фоне myshape обеспечивает конструктор myshape. Функция move для myshape обеспечивает перемещение всех добавок. А функция draw рисует только прямоугольник-контур и точку-нос, которая в myshape вообще не включена. «Глаза» и «рот» рисуются самостоятельно, потому что они являются фигурами и включаются в список для рисования обычным порядком. В базовый проект из Методички включён пример пользовательской фигуры «полукруг», присоединяемый в позицию «борода». Его следует заменить пользовательской фигурой. Алгоритм рисования круга можно использовать, если необходимо. Рисуется только четверть круга, остальные добавляются симметрично. При повороте или отражении включаются одни сектора и выключаются другие. Круг вписан в прямоугольник, определяющий его крайние точки. Контрольная работа 2. Исключения В работе 2 предыдущий проект модифицируется добавлением в него механизма обработки исключений. Цель этого механизма — сохранить программный проект работоспособным при любых неожиданностях, могущих возникнуть при реальной работе с данными. Обработка ошибок в стиле Си: — возврат функцией кода ошибки; — установка значения переменной errno. Эти способы требуют, чтобы в программном коде были соответствующие проверки. ИДЕЯ: выявление ошибки нужно свести к минимальным возможным последствиям. Механизм: throw Error; //Оператор для возбуждения исключительной ситуации + блок контроля try { //Проблемный код } catch(Error) { //Обработка ошибки } Общие принципы: вход в блок catch сопровождается выравниванием стека. Стек приводится в состояние, в котором он был при входе в блок контроля try: автоматически вызываются деструкторы для всех созданных к моменту сбоя объектов и т.д. Корректность результатов этого процесса обеспечивается гарантиями устойчивости алгоритма относительно исключений. — в результате входа в блок catch исключение считается обработанным; варианты действий в блоке catch: — ничего не делать, — выдать сообщение, — запросить/осуществить изменение; + возбудить новое исключение или + перевозбудить старое: throw; Error — это пользовательский класс ошибки, который может быть вообще пустым (класс-понятие): struct Error{}; или class Error{}; Оператор throw Error; создаёт пустой объект соответствующего типа, который сам по себе является информацией о произошедшем событии. Но возможна и передача дополнительной информации через исключение. Для этого достаточно, чтобы класс Error имел память, инициализируемую конструктором – аргументом оператора throw. struct Error { point a; Error (point a) : a(a) { } }; Возбуждение: throw Error(point(x, y)); Перехват: catch(Error &e) { cout ≪ «ошибка в точке» ≪ e.f.x ≪ « » ≪ e.a.y; } — похоже на вызов функции. ОТЛИЧИЯ: — передаваемый объект ВСЕГДА временная копия. Принять можно: указатель, объект, ссылку. Указатель должен указывать на не уничтожаемый объект. Перехват указателя эквивалентен перехвату catch (const void *). Объект будет лишний раз копироваться. Ссылка — лучше всего, только одна копия. Указывать const не обязательно, в случае исключений работает и так. Отличие от вызова функции: никакого преобразования типов; никакого подбора лучшего соответствия, срабатывает первый подходящий catch. Исключение — для иерархии классов: базовый класс перехватывает производный. Последний перехват — catch(. . .) — перехват любого исключения. Исключение в конструкторе — объект не создаётся. Исключения в деструкторе недопустимы или по крайней мере не должны покидать деструктор! Тем самым гарантируется, что деструктор выполнится до конца и не будет вызвано terminate(). Библиотечные исключительные ситуации: bad_alloc, bad_cast и т. п. Иерархия стандартных исключений (подключаются через #include ) exception — logic_error — — domain_error, invalid_argument, length_error, out_of_range; — runtime_error — — range_error, underflow_error, overflow_error — bad_cast — ошибка dynamic_cast — bad_typeid <=> ошибка typeid(0) — bad_exception — неожиданное исключение unexpected( ) — bad_alloc — bad_weak_ptr — bad_function_call — ошибка обёртки для функции СОВЕТ: class MyError : public std∷exception { MyError (char * s) : std∷exception(s) { } }; throw MyError(«Плохо!»); catch(MyError & e) { cout ≪ e.what( ); } Таким образом: - используется готовый механизм передачи сообщения из точки ошибки; - пользовательское исключение вписывается в общую систему контроля ошибок и может быть перехвачено системой с выдачей понятного заготовленного пользователем сообщения. Класс exception содержит определение виртуальной функции: virtual const char* exception∷what( ) const noexcept; Спецификация исключений у библиотечных функций: отменены новым стандартом, как вызывающие проблемы; оставлено только noexcept. К упражнению № 2 Определение рационального уровня перехвата исключений на примере цепочки вызовов в программе screen: main( ) → shape_refresh( ) → draw( ) → put_line( ) → put_point( ) → on_screen( ) Перехват осуществляется на том уровне, где возможна содержательная обработка ошибки, а последствия сбоя минимальны. Использование механизма throw/catch внутри функции, где обнаружена ошибка — бессмысленно. Ошибку можно просто обработать на месте (выдать сообщение, исправить или игнорировать, как это делалось в исходном проекте при срабатывании on_screen()), СОВЕТ: — разделить ошибки по категориям серьёзности. — базироваться от exception; — серьёзные ошибки (в конструкторе) — не перехватывать вообще. Вариант: конструктор с возможной ошибкой использовать не для создания объекта, а для инициализации указателя на объект. Содержание такого указателя будет несложно подменить указателем на специальный объект-ошибку, заменяющий сбойный объект на картинке. Если могут быть ошибки в конструкторах, класс shape должен иметь виртуальный деструктор, исключающий объект из списка на рисование. Требование к коду с исключениями: ИДИОМА захват ресурса есть инициализация Кривое программирование на Си: void file_work(char * fn, char * mode) { FILE * f = fopen(fn, mode); if ( f ) { //работаем с файлом //… close( f ); } } ВАРИАНТ (для тех, кто что-то понял): void file_work(char * fn, char * mode) { FILE * f = fopen(fn, mode); if ( f ) try { //работаем с файлом //… if(error) throw “ОШИБКА”; close( f ); } catch(char * e) { cerr << e; if( f ) fclose(f); } } ПРАВИЛЬНО: class MyFile { public: FILE * f; MyFile(char * fn, const char * mode = “r”) { f(fopen(fn, mode)) }; ~MyFile( ) { if(f) close( f ); } } void file_work(char * fn, char * mode) { MyFile file (fn, mode); if ( file.f ) { //работаем с файлом //… } } //ВЫХОД – файл закрыт ЕЩЁ БОЛЕЕ ПРАВИЛЬНО: int main() { ifstream f("text.txt"); string s; f >> s; //Работаем с файлом и данными } КОНСТРУКТОРЫ: — исключение — единственный способ сообщить о проблеме при создании объекта. — реакция на исключение в подобъекте — транслировать его дальше. — при исключении в конструкторе объект НЕ создаётся, созданные подобъекты автоматически уничтожаются. ДЕСТРУКТОРЫ: не должны генерировать исключений. Контрольная работа 3. STL и пользовательский контейнер В этой работе мы возвращаемся к работе с множествами, но в более реальном варианте — с использованием структур данных, оптимизированных не только под двуместные операции, но и под примитивы — проверку принадлежности + вставку/удаление. Добавляется дополнительное условие: структура данных должна обеспечивать операции и для множества, и для последовательности, для чего она хранит в каком-то варианте отображение элементов множества на натуральный ряд чисел. Для построения пользовательской структуры данных применяются возможности стандартной библиотеки шаблонов — STL. Конечной целью является создание пользовательского контейнера, пригодного для работы совместно с алгоритмами STL. Промежуточная цель — создание пользовательской структуры данных, комбинирующей для поставленной цели контейнеры STL — set, unordered_set, vector, list и т.п. Пример программы, комбинирующей контейнеры STL для пользовательской структуры данных, имеется в 4-м разделе Методички. В силу универсальности эта программа не является оптимальной для всех вариантов заданий, зато она сохранит работоспособность при замене set на unordered_set и обеспечивает расширенные гарантии устойчивости относительно исключений. Желающие делать свой контейнер на основе одного из вариантов дерева двоичного поиска могут запросить у меня учебный пример-заготовку для превращения его в свой вариант индивидуального задания. Итоговая аттестация По результатам трёх контрольных работ выводится оценка за итоговый экзамен по дисциплине. Курсовая работа — измерение фактической временной сложности в эксперименте на ЭВМ — учебным планом не предусмотрена. Желающие могут выполнить её, чтобы проверить априорные оценки временной сложности — за поощрительный балл (если будет куда).